联系我们:010-88559646

  老师群

170086145

  学生群

179326524

209318323

215410234

客服电话:010-88559646

Fast calculation of massive high-dimensionalvector similarity

时间:2017-03-22        来 源:中国软件杯

Topic: Fast calculation of massive high-dimensionalvector similarity

Group (A): Undergraduates or above

Topicintroduction: Explaining the whole idea and requirements of the topic

Assumethat the following dataset D has N vectors of 1024 dimensions, wherein N isequal to ten million, and data on each dimension of the vector is 32-bitfloating point number:

Definethe distance from Vector x to Vector y as Euclidean distance, so

d(x,y) = 

 

Definethe nearest neighbor of Vector x in the dataset D is the vector nearest to x inD, so

Nearest Neighbor(x) = 


WhereM is equal to 100,000 vectors of 1024 dimensions ({M1, M2,..., M100000}), design a program to find out ID corresponding to thenearest neighbor of each vector in the dataset D.

eva luationstandard: program execution time, with the shortest time winning.


Topicscenarios: Describing the business scenarios of related real companies, and simplifyingor extracting proper competition scenariosfrom the real ones

We always need to search images similar to thedesignated one during image analysis and video monitoring. For instance, intypical face recognition application, each face is represented as ahigh-dimensional vector (such as a vector of 1024 dimensions) after a series ofimage preprocessing, and for recognizing the identity corresponding to certainface, we search the face feature vector corresponding to known identity, mostsimilar to the feature vector of certain face, in a face feature database. Inpractical application, we need to design a rapid search algorithm since theface feature database is generally of an extremely large scale (>10,000,000).

Functional requirements

For given 100,000 vectors to inquire, look up thenearest neighbor of each vector in the database, and for certain vector toinquire, output one of vectors the distance from which to the certain one isequal and the smallest.

Non-functional requirements

Focus on program execution speed, with the highestspeed winning.

Other restrictions:Development environment, test platform, development language, database,complier, etc. (as explicit as possible)

Machine running memory < 16G
Test data or platform: Testenvironment and data provided to competitors (electronic documents areacceptable)Provided separately
Instructions aboutdevelopment equipment and equipment metricsNo
Other RequirementsNo


主办单位

工业和信息化部

教育部

江苏省人民政府

承办单位

中国电子信息产业发展研究院

江苏省工业和信息化厅

江苏省教育厅

教育部高等学校计算机类专业教学指导委员会

信息技术新工科产学研联盟

执行单位

中国信息化周报

南京江北新区产业技术研创园

江苏软件产业人才发展基金会

南京市软件和信息服务集群发展促进机构

南京航空航天大学

关于我们

客服电话:010-88559646

邮编:100048

联系地址:北京市海淀区紫竹院路66号赛迪大厦18层

网站备案/许可证号:京ICP备05039896号-10     京公网安备 11010802020860号