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: 3780
Venue: SIGMOD
Year: 2006
Pagerank: 4.4725847e-05
Overall Rank: 8,645 | 39.92%
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,657	Moirae: History-Enhanced Monitoring	2007	CIDR	4.9686214e-05
12,285	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	4.1905499e-05
12,387	Constrained Locally Weighted Clustering	2008	VLDB	4.1905499e-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.0016113151
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031052437
537	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020650291
798	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016484637
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579
929	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001523035
2,666	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	8.3498373e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,045	Indexable PLA for Efficient Similarity Search	2007	VLDB	9.6950855e-05
13,581	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB	-
3,541	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9910982e-05
1,802	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001048177
8,127	Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation	2001	VLDB	4.5757206e-05
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031052437
6,316	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.1098143e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579