A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases

Summary: Proposes a non-linear dimensionality-reduction scheme that extracts two parameters to bound the search volume around the query sphere, independent of dimensionality. Uses a workspace-mapping mechanism to derive tight bounds and enable distance lower-bounding for fast, index-based similarity search with empirical gains over state of the art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3779
Venue: SIGMOD
Year: 2006
Pagerank: 4.4768766e-05
Overall Rank: 8,647 | 39.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,654	Moirae: History-Enhanced Monitoring	2007	CIDR	4.9733876e-05
12,277	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	4.1945683e-05
12,379	Constrained Locally Weighted Clustering	2008	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00062029383
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031074984
539	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020666392
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
931	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00015238406
2,661	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	8.3575285e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,041	Indexable PLA for Efficient Similarity Search	2007	VLDB	9.6992894e-05
13,568	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB	-
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
1,806	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010490769
8,123	Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation	2001	VLDB	4.5801104e-05
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031074984
6,325	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.1105081e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517