Exploring bit-difference for approximate KNN search in high-dimensional databases

• Main Authors: Cui, Bin, Shen, Heng Tao, SHEN, Jialie, Tan, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2005
• Subjects: High-dimensional index structure; approximate KNN query; memory processing; bit difference; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/1298; https://ink.library.smu.edu.sg/context/sis_research/article/2297/viewcontent/CRPITV39CuiShen.pdf
• Institution: Singapore Management University

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 overa...