FGBC-iDistance:细粒度位码过滤的高维索引  

FGBC-iDistance: fine-grained bit-code filter based high-dimensional index

作　　者：袁鑫攀 汪灿飞 龙军[2] 章成源 满君丰 

机构地区：[1]湖南工业大学计算机学院智能信息感知及处理技术湖南省重点实验室,湖南株洲412007 [2]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《通信学报》2017年第A01期127-134,共8页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61402165;No.S1651002);湖南省重点研发计划基金资助项目(No.2016JC2018);2016年湖南工业大学研究生校级创新基金资助项目(No.CX1606)~~

摘　　要：在高维向量检索中,距离计算是很耗时的操作,当前科研趋势是采用分治法来减少距离计算。iDistance通过锚点将向量空间划分为聚类子空间,BC-iDistance通过BC码将聚类子空间每维划分成2个区域。提出一种更加细粒度的区域划分方法和索引结构,每个区域对应一个细粒度位码FGBC(fine grained bit code),通过FGBC码实现了对候选集更精准的过滤。FGBC-iDistance的距离计算次数最好能减少到iDistance的2/12d,在距离计算次数上,有FGBC-iDistance≤BC-iDistance≤iDistance。实验结果表明当范围查询半径为0.08时,FGBC-iDistance的距离计算次数约为20 000次,远小于其他算法,运行时间也相应减少。In the high-dimensional vector retrieval, distance computation is a very time-consuming operation, the current research trend is to reduce the distance computation using divide and conquer algorithm. iDistance algorithm divides the vector space into subspace of clustering by pivot, BC-iDistance algorithm divides the subspace into 2 partitions in each dimension. A more fine-grained partition algorithm and index structure was proposed, each part corresponded with a unique FGBC code （fine-grained bit code）, which realized the candidate sets filtered more precisely. The distance com-putation times of FGBC-iDistance can be reduced to 212 dof iDistance. The distance computation frequency comparison： FGBC-iDistance≤BC-iDistance≤iDistance. The experiment results show that when the scope radius of the range query is 0.08, FGBC-iDistance distance computation times is about 20,000, which is far less than other algorithms, the running time is also reduced.

关 键 词：距离计算 细粒度 iDistance 范围查询 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]