DBScholar

Back to papers

Indexing the Distance: An Efficient Method to KNN Processing

Summary: iDistance transforms high-dimensional KNN search into 1D range queries by partitioning data around reference points and indexing distance keys with a B+-tree. Flexible partition/reference selection adapts the index to data distribution, outperforming fixed metric indexes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
8957
Venue
VLDB
Year
2001
Pagerank
7.8984588e-05
Overall Rank
2,979 | 79.57%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{yu_vldb01,
        title = {{Indexing the Distance: An Efficient Method to KNN Processing}},
        author = {Yu, Cui and Ooi, Beng Chin and Tan, Kian-Lee and Jagadish, H. V.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
1,281 Continuous Nearest Neighbor Search 2002 VLDB 0.00011349245
2,020 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.2983514e-05
2,137 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 9.110238e-05
2,673 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.2730112e-05
2,886 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.9957585e-05
3,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,581 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.2873782e-05
3,766 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 7.1430942e-05
4,618 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.6036373e-05
4,927 Neighbor-Sensitive Hashing 2016 VLDB 6.4426453e-05
5,162 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.339805e-05
5,405 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.2291247e-05
8,033 TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets 2011 SIGMOD 5.5039566e-05
8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.3766157e-05
12,422 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 5.093636e-05
12,677 Peer-to-Peer Similarity Search in Metric Spaces 2007 VLDB 5.093636e-05
12,704 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 5.093636e-05
12,756 Database-Inspired Search 2005 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0020210012
31 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00050347119
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
351 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00020424271
592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00016029789
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
1,602 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010239526
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
3,282 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.5667715e-05
6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.744549e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS
2 592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
3 3,710 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
4 1,612 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB
5 7,708 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB
6 11,751 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS
7 6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
8 3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
9 705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
10 8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD