DBScholar

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
h751cabf5bc18a722
Venue
SIGMOD
Year
1998
Pagerank
0.0001363793
Overall Rank
826 | 94.45%
DOI
10.1145/276304.276319

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{seidl_sigmod98,
        title = {{Optimal Multi-Step k-Nearest Neighbor Search}},
        author = {Seidl, Thomas and Kriegel, Hans-Peter},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276319},
        url = {https://dl.acm.org/doi/10.1145/276304.276319},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
193 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025648171
458 Query Processing in Spatial Network Databases 2003 VLDB 0.00017868943
613 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015570505
643 Evaluating Top-k Selection Queries 1999 VLDB 0.00015217076
677 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00014843441
1,070 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012174775
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011104243
2,412 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5101348e-05
3,108 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.640323e-05
3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4271038e-05
3,413 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD 7.3250313e-05
3,658 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1243855e-05
4,196 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.7421052e-05
4,889 An Efficient Index Structure for String Databases 2001 VLDB 6.3682428e-05
5,722 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.0183253e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-05
6,540 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7523628e-05
6,890 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 5.6544825e-05
7,023 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6186604e-05
8,286 Anticipatory DTW for Efficient Similarity Search in Time Series Databases 2009 VLDB 5.3620578e-05
8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2700772e-05
9,436 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 5.1780501e-05
12,713 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9793485e-05
13,105 A Shrinking-Based Approach for Multi-Dimensional Data Analysis 2003 VLDB 4.9793485e-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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045773967
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020019939
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.0001946565
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011774968
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
8,567 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.3137327e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,113 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
2 20 Similarity Search in High Dimensions via Hashing 1999 VLDB
3 1,170 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD
4 10,299 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB
5 1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
6 674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD
7 6,610 Similarity Search: A Matching Based Approach 2006 VLDB
8 3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
9 5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB
10 3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD