Efficient k-NN Search on Vertically Decomposed Data

Summary: Proposes vertical data decomposition and a BnB variant that trims high-dimensional space to a small k-NN candidate set. Applied to two image-similarity metrics, it outlines relational-DB implementation and reports speedups on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3422
Venue: SIGMOD
Year: 2002
Pagerank: 7.4808966e-05
Overall Rank: 3,363 | 76.93%
DOI: 10.1145/564691.564729

Incoming Non-self Citations Over Time

Authors

1. Arjen P. de Vries (Centrum Wiskunde & Informatica)
2. Nikos Mamoulis (University of Hong Kong)
3. Niels Nes (Centrum Wiskunde & Informatica)
4. Martin Kersten (Centrum Wiskunde & Informatica)

BibTeX Citation

@inproceedings{vries_sigmod02,
        title = {{Efficient k-NN Search on Vertically Decomposed Data}},
        author = {de Vries, Arjen P. and Mamoulis, Nikos and Nes, Niels and Kersten, Martin},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564729},
        url = {https://dl.acm.org/doi/10.1145/564691.564729},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
2,938	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	7.942728e-05
3,209	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.6357297e-05
4,867	Indexing Large Human-Motion Databases	2004	VLDB	6.4720439e-05
7,720	PDX: A Data Layout for Vector Similarity Search	2025	SIGMOD	5.559007e-05
10,336	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
108	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00033228866
115	A Decomposition Storage Model	1985	SIGMOD	0.00032338948
402	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00019072958
483	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017756569
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.7769047e-05
1,862	MindReader: Querying databases through multiple examples	1998	VLDB	9.5951515e-05
2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.0622995e-05
9,035	Indexing Images in Oracle8i	2000	SIGMOD	5.327414e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	784	Near Neighbor Search in Large Metric Spaces	1995	VLDB
2	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
3	3,866	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
4	12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
5	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
6	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
7	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
8	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
9	796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
10	6,483	Similarity Search: A Matching Based Approach	2006	VLDB