Exploring bit-di®erence for approximate KNN search in high-dimensional databases

In this paper, we develop a novel index structure to support e±cient approximate k-nearest neighbor (KNN) query in high-dimensional databases. In high-dimensional spaces, the computational cost of the distance (e.g., Euclidean distance) between two points contributes a dominant portion of the overall query response time for memory processing. To reduce the distance computation, werst propose a structure (BID) using BIt-Di®erence to answer approximate KNN query. The BID employs one bit to represent each feature vector of point and the number of bit-di®erence is used to prune the further points. To facilitate real dataset which is typically skewed, we enhance the BID mechanism with clus-tering, cluster adapted bitcoder and dimensional weight, named the BID+. Extensive experiments are conducted to show that our proposed method yields significant performance advantages over the existing index structures on both real life and synthetic high-dimensional datasets