Abstract:

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 $\frac{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.

Key words: distance computation, more fine-grained, iDistance, range query