iDistance: An adaptive B+-tree based indexing method for nearest neighbor search
AuthorJagadish, HV; Ooi, BC; Tan, KL; Yu, C; Zhang, R
Source TitleACM Transactions on Database Systems
PublisherASSOC COMPUTING MACHINERY
University of Melbourne Author/sZhang, Rui
AffiliationComputer Science and Software Engineering
Document TypeJournal Article
CitationsJagadish, H. V., Ooi, B. C., Tan, K. L., Yu, C. & Zhang, R. (2005). iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM TRANSACTIONS ON DATABASE SYSTEMS, 30 (2), pp.364-397. https://doi.org/10.1145/1071610.1071612.
Access StatusThis item is currently not available from this repository
In this article, we present an efficient B + -tree based indexing method, called iDistance, for K-nearest neighbor (KNN) search in a high-dimensional metric space. iDistance partitions the data based on a space- or data-partitioning strategy, and selects a reference point for each partition. The data points in each partition are transformed into a single dimensional value based on their similarity with respect to the reference point. This allows the points to be indexed using a B + -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.
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References