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: 3841
Venue: SIGMOD
Year: 2006
Pagerank: 5.3910353e-05
Overall Rank: 8,655 | 40.62%
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,400	Moirae: History-Enhanced Monitoring	2007	CIDR	5.8864351e-05
12,472	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	5.093636e-05
12,572	Constrained Locally Weighted Clustering	2008	VLDB	5.093636e-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.001157935
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00026105472
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
797	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013927251
864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013522522
3,264	WALRUS: A Similarity Retrieval Algorithm for Image Databases	1999	SIGMOD	7.5841142e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,722	Indexable PLA for Efficient Similarity Search	2007	VLDB
2	13,768	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB
3	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
4	1,602	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB
5	8,391	Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation	2001	VLDB
6	46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB
7	190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD
8	6,646	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS
9	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
10	797	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD