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: 3072
Venue: SIGMOD
Year: 1998
Pagerank: 0.00013932561
Overall Rank: 796 | 94.55%
DOI: 10.1145/276304.276319

Incoming Non-self Citations Over Time

Authors

1. Thomas Seidl (University of Munich)
2. Hans-Peter Kriegel (University of Munich)

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
190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00026105472
449	Query Processing in Spatial Network Databases	2003	VLDB	0.0001826404
601	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015870156
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00015167291
1,046	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00012440091
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
2,387	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.6482009e-05
3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.8155543e-05
3,353	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.492706e-05
3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	7.4808966e-05
3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.2873782e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
4,776	An Efficient Index Structure for String Databases	2001	VLDB	6.513844e-05
5,592	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	6.1552372e-05
5,838	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	6.0702428e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05
6,756	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	5.7829178e-05
6,887	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.7457967e-05
8,107	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB	5.4851245e-05
8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	5.3910353e-05
9,262	Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects	2003	SIGMOD	5.2968259e-05
12,422	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	5.093636e-05
12,815	A Shrinking-Based Approach for Multi-Dimensional Data Analysis	2003	VLDB	5.093636e-05

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.00052102434
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
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
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019869565
483	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017756569
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00012027131
1,776	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	9.7853414e-05
3,866	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	7.061829e-05
8,392	S3: Similarity Search in CAD Database Systems	1997	SIGMOD	5.4356884e-05

Semantically Similar Papers

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