iDistance: An adaptive B+-tree based indexing method for nearest neighbor search Rui Zhang, Cui Yu, Kian-Lee Tan, Beng Chin Ooi, and H. V. Jagadish   View Paper (PDF)   Return to June 2005, Volume 30, Issue 2 Abstract plus;-tree structure and KNN search to be performed using one-dimensional range search. The choice of partition and reference points adapts the index structure to the data distribution.We conducted extensive experiments to evaluate the iDistance technique, and report results demonstrating its effectiveness. We also present a cost model for iDistance KNN search, which can be exploited in query optimization. ©2006 Association for Computing Machinery