Please use this identifier to cite or link to this item: https://doi.org/10.1145/1071610.1071612
Title: IDistance: An adaptive B +-tree based indexing method for nearest neighbor search
Authors: Jagadish, H.V.
Ooi, B.C. 
Tan, K.-L. 
Yu, C.
Zhang, R.
Keywords: Additional Key Words and Phrases: Indexing
KNN
Nearest neighbor queries
Issue Date: 2005
Source: Jagadish, 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) : 364-397. ScholarBank@NUS Repository. https://doi.org/10.1145/1071610.1071612
Abstract: 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. © 2005 ACM.
Source Title: ACM Transactions on Database Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/42315
ISSN: 03625915
DOI: 10.1145/1071610.1071612
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

344
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

220
checked on Oct 31, 2017

Page view(s)

86
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.