Database Paper Browser

Back to papers

Optimal Multi-Step k-Nearest Neighbor Search

Summary: Two-stage kNN search for high-dimensional, adaptable similarity functions. Novel multi-step algorithm guarantees the minimum candidate set, outperforming Korn et al. 1996 with up to 120× fewer candidates and 48× faster runtime. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3011
Venue
SIGMOD
Year
1998
Pagerank
0.00016484637
Overall Rank
798 | 94.46%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
243 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00031052437
391 Query Processing in Spatial Network Databases 2003 VLDB 0.00024560891
597 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019450818
696 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00017991162
802 Evaluating Top-k Selection Queries 1999 VLDB 0.00016440813
1,060 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00014359912
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
2,577 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5066436e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
3,427 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD 7.1016046e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
4,330 An Efficient Index Structure for String Databases 2001 VLDB 6.2745131e-05
4,370 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.2392118e-05
5,883 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2865165e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
6,575 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 4.9993797e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9237313e-05
8,140 Anticipatory DTW for Efficient Similarity Search in Time Series Databases 2009 VLDB 4.5726407e-05
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
9,120 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 4.3881453e-05
12,235 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1905499e-05
12,631 A Shrinking-Based Approach for Multi-Dimensional Data Analysis 2003 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
65 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00061977022
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032141918
362 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00025758421
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022348285
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018437125
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010661725
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
8,128 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 4.5757206e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,099 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5429949e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
2,002 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 9.8258191e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
710 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00017727016
6,173 Similarity Search: A Matching Based Approach 2006 VLDB 5.1684255e-05
4,035 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.5111577e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05