FGBC-iDistance:fine-grained bit-code filter based high-dimensional index - Xin-pan YUAN; Can-fei WANG; Jun LONG; Cheng-yuan ZHANG; Jun-feng MAN (Tongxin xuebao)
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 computation times of FGBC-iDistance can be reduced to 1 2 2d of 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.