TOP

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

第七届大赛--A组赛题


作品提交内容:源代码、可执行文件、相关文档、演示视频(格式不限,时间尽量控制在7分钟以内)等。

有两个小要求:

a. 学生在检索函数前后加上时间戳,以便评测老师评估,
b. 检索得到的ID,以文件方式保存、格式为:检索得到的ID。

评审要点:优先考虑正确率,高于正确率阈值的结果方可纳入时间计算,阈值高低视所有参赛选手结果而定,参赛选手的检索时间为均时间。


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

组类: 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万),因此需要设计快速的查找算法。

功能性需求

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

非功能性需求

此题主要考察程序执行速度,在保证一定的准确率的前提下,越快越好,最快者获胜。

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

运行机器内存 < 16G

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

(可提供电子档)

另行提供

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

其他要求


word版赛题下载

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




测试数据6.12 

base_vector.fea下载链接:链接:https://pan.baidu.com/s/1zVs_yiX7du2MM__6WwwYdA 密码:jcjb

verify_vector.fea下载链接:链接:https://pan.baidu.com/s/1cHNqQ1nfGB1zO4z33Aq9tQ 密码:028x

将base_vector.fea的向量数目由1000万降低至100万,该100万为原1000万向量的前100万个向量,可以自行截取或者重新下载。

verify_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



【补充说明】6.12

机器配置:

CPU:i7    

内存:4G

操作系统要求:

windows 7或windows 10 操作系统

ubuntu 14.04 desktop 14.04 或者 ubuntu 16.04 desktop


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

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



答疑汇总 

海量高维向量相似度快速计算答疑汇总.doc


答疑老师联系方式:

yangfan871213@126.com  杨帆  

答疑qq群:717202297(学生自发组建,答疑老师已进群)






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

相关栏目