TOP

海量高维向量相似度快速计算
2018-03-16 18:42:19 来源: 作者: 【 】 浏览:4876

第七届大赛--A组赛题


赛题名称: 海量高维向量相似度快速计算

组类: A 本科及以上    

赛题简介:介绍整个赛题的思路和整体要求

假设如下数据集D里有N个1024维的向量, N=1千万,向量中各个维度上的数据都是32位浮点数:

ID

 Vector

1

a1,    a2, ...., a1024   

2

b1, b2, ...., b1024

....

.........

N

n1, n2, ...., n1024

定义向量x与向量y之间的距离为欧几里得距离,即:

d(x,y)  =  


定义向量x在数据集D上的最近邻为D中与x距离最小的向量,即

NearestNeighbor(x)  = 


现有M=10万个1024维向量{M1,  M2, ..., M100000}, 请设计程序在数据集D中分别找到其最近邻对应的ID。

评价标准:程序的执行时间越短越好。

 

赛题业务场景:描述赛题相关的真实企业业务背景。从真实场景中,适当简化或者提炼出适合比赛的赛题场景

在图像分析和视频监控中,经常需要搜索与指定的图像相类似的其他图像。例如典型的人脸识别应用,经过一系列的前期图像处理操作后,每张人脸表征为一个高维向量(例如1024维),识别某张人脸对应的身份,实际上就是在人脸特征数据库中查找与其特征向量最相似的已知身份的人脸特征向量。在现实业务场景,由于人脸数据库通常规模很大(>1000万),因此需要设计快速的查找算法。

功能性需求

对于给定的10万个查询向量,在数据库中查找得到每个查询向量的最近邻。若对某个查询向量,数据库中存在大于一个的向量与其距离相等并且是最小的,那么输出一个即可。

非功能性需求

此题主要考察程序执行速度,越快越好,最快者获胜。

其他限制条件:开发环境、实验平台、开发语言、数据库、编译器等限制条件(请尽量明确)

运行机器内存 < 16G

测试数据或平台:提供给参赛者的测试环境和测试数据。

(可提供电子档)

另行提供

开发所需设备及设备指标需求说明

其他要求


word版赛题下载

海量高维向量相似度快速计算.doc




测试数据  链接:https://pan.baidu.com/s/1erxa48sU2zeZXERCRBbYRA  密码:yp74


说明:

分包压缩,共有5个压缩文件,使用hdss_cnsoft2018.zip进行解压,解压完有两个个文件:base_vector.fea, verify_vector.fea,


数据说明:

base_vector.fea,包含1000万个1024维的数据以及一位ID,ID从0~9999999,作为待查询数据集,如下,

Id1, v1,1, v1,2, ...... v1,1024

Id2, v2,1, v2,2, ...... v2,1024

.....

verity_vector.fea,包含100个1024维的数据以及一位ID,用于参赛者验证算法的性能,其中Id1为用(v1,1, v1,2, ...... v1,1024)在base_vector.fea中查询欧式距离最近时得到的ID 

Id1,v1,1, v1,2, ...... v1,1024

Id2,v2,1, v2,2, ...... v2,1024



补充说明:

机器配置为,Intel i7-7700, 内存小于16GB,无GPU支持

比赛结果将会综合考虑检索结果的准确性与速度

参赛者提供的程序需直接可以运行,所有使用到的库请包含在程序结构中。



答疑老师联系方式:

yang.fan310@zte.com.cn 杨帆





关键字: 责任编辑:cnsoft
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到QQ空间
分享到: 
上一篇企业信息族谱分析 下一篇基于人工智能及机器视觉的安全帽..

相关栏目