In this paper, we develop a novel index structure to support effcient 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, we first propose a structure (BID) using BIt-Difference to answer approximate KNN query. The BID employs one bit to represent each feature vector of point and the number of bit-difference is used to prune the further points. To facilitate real dataset which is typically skewed, we enhance the BID mechanism with clustering, cluster adapted bitcoder and dimensional weight, named the BID+. Extensive experiments are conducted to show that our proposed method yields signifcant performance advantages over the existing index structures on both real life and synthetic high-dimensional datasets.
High-dimensional index structure, approximate KNN query, memory processing, bit difference
Databases and Information Systems
Data Management and Analytics
Proceedings of the 21st ACM International Conference on Multimedia
City or Country
Cui, Bin; Shen, Heng Tao; SHEN, Jialie; and Tan, Kian-Lee.
Exploring bit-difference for approximate KNN search in high-dimensional databases. (2005). Proceedings of the 21st ACM International Conference on Multimedia. 947-956. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1298
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.