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

摘要

在高维向量检索中,距离计算是很耗时的操作,当前科研趋势是采用分治法来减少距离计算。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次,远小于其他算法,运行时间也相应减少。