TOP

Fast calculation of massive high-dimensionalvector similarity
2017-03-22 14:00:26 来源: 作者: 【 】 浏览:598

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:

ID

 Vector

1

a1, a2,  ...., a1024                    

2

b1,  b2, ...., b1024

....

.........

N

n1,  n2, ...., n1024

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 metrics

No

Other Requirements

No

 

关键字: 责任编辑:cnsoft
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到QQ空间
分享到: 
上一篇Enterprise InformationMap Analy.. 下一篇Safety helmet extraction and an..

相关栏目