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
hc2214f9a4c108c80
Venue
VLDB
Year
2001
Pagerank
7.7214661e-05
Overall Rank
3,025 | 79.73%
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
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
2,076 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.0622765e-05
2,183 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.8973287e-05
2,501 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.359489e-05
2,952 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8061763e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,629 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 7.1286458e-05
3,666 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.0975312e-05
4,734 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.4311188e-05
4,873 Neighbor-Sensitive Hashing 2016 VLDB 6.3580715e-05
5,292 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.1783225e-05
5,547 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0715188e-05
8,215 TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets 2011 SIGMOD 5.3601329e-05
8,955 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2361195e-05
12,762 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9605343e-05
13,015 Peer-to-Peer Similarity Search in Metric Spaces 2007 VLDB 4.9605343e-05
13,042 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.9605343e-05
13,094 Database-Inspired Search 2005 VLDB 4.9605343e-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.0019892478
32 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00049559562
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044967652
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
364 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019916561
598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015711108
889 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013212387
1,642 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 9.9812004e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
3,332 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.4057218e-05
6,962 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6181217e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
2 598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
3 3,784 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
4 1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB
5 7,876 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB
6 12,104 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS
7 6,256 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
8 3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
9 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
10 8,955 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD