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: 3360
Venue: SIGMOD
Year: 2002
Pagerank: 6.9502303e-05
Overall Rank: 3,579 | 75.11%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
2,989	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.7733083e-05
3,044	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.6640252e-05
3,726	Indexing Large Human-Motion Databases	2004	VLDB	6.8148202e-05
3,772	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7761705e-05
7,879	PDX: A Data Layout for Vector Similarity Search	2025	SIGMOD	4.6292417e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1945683e-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.0032169493
17	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00096067547
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045447517
123	A Decomposition Storage Model	1985	SIGMOD	0.00045255007
169	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038895438
471	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00022364776
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018451109
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
1,608	MindReader: Querying databases through multiple examples	1998	VLDB	0.00011151257
1,925	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010073407
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
8,814	Indexing Images in Oracle8i	2000	SIGMOD	4.4435503e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
708	Near Neighbor Search in Large Metric Spaces	1995	VLDB	0.00017772684
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
3,555	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9772546e-05
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-05
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
6,164	Similarity Search: A Matching Based Approach	2006	VLDB	5.1733919e-05