LBD:Exploring Local Bit-code Difference for KNN Search in High-dimensional Spaces
LBD：基于局部位码比较的高维空间KNN搜索算法

Recent advances in research fields like multimedia and bioinformatics have brought about a new generation of high-dimensional databases. To support efficient querying and retrieval on such databases, we propose a methodology exploring Local Bit-code Difference (LBD)which can support k-nearest neighbors (KNN)queries on high-dimensional databases and yet co-exist with ubiquitous indices, such as B -trees. On clustering the data space into a number of partitions, LBD extracts a distance and a simple bitmap representation called Bit Code (BC)for each point in the database with respect to the corresponding reference point. Pruning during KNN search is performed by dynamically selecting only a subset of the bits from the BC based on which subsequent comparisons are performed. In doing so, expensive operations involved in computing L-norm distance functions between high-dimensional data can be avoided. Extensive experiments are conducted to show that our methodology offers significant performance advantages over other existing indexing methods on both real life and synthetic high-dimensional spaces.