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: h2ffb630bdf3dd48f
Venue: SIGMOD
Year: 2006
Pagerank: 5.2700772e-05
Overall Rank: 8,818 | 40.72%
DOI: 10.1145/1142473.1142532

Incoming Non-self Citations Over Time

Authors

1. Khanh Vu (University of Central Florida)
2. Kien A. Hua (University of Central Florida)
3. Hao Cheng (University of Central Florida)
4. Sheau-Dong Lang (University of Central Florida)

BibTeX Citation

@inproceedings{vu_sigmod06,
        title = {{A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases}},
        author = {Vu, Khanh and Hua, Kien A. and Cheng, Hao and Lang, Sheau-Dong},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142532},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142532},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,532	Moirae: History-Enhanced Monitoring	2007	CIDR	5.7544926e-05
12,763	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	4.9793485e-05
12,862	Constrained Locally Weighted Clustering	2008	VLDB	4.9793485e-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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00025648171
478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017631293
811	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013745617
826	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.0001363793
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001325914
3,332	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	7.4163853e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,731	Indexable PLA for Efficient Similarity Search	2007	VLDB
2	14,079	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB
3	2,060	Similarity search in the blink of an eye with compressed indices	2023	VLDB
4	1,634	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB
5	8,566	Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation	2001	VLDB
6	45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB
7	193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD
8	6,740	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS
9	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
10	811	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD