Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search

Summary: Isolates and accelerates the Distance Comparison Operation (DCO) in high-dimensional AKNN by proposing DADE, a data-aware, unbiased lower-dimensional distance estimator with an optimized formulation. Adds a hypothesis-testing scheme to adaptively pick minimal projection dimensions and plugs into IVF/HNSW to cut DCO-dominated latency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdd75f8c383a9d1ed
Venue: VLDB
Year: 2025
Pagerank: 5.8382662e-05
Overall Rank: 6,239 | 58.06%
DOI: 10.14778/3712221.3712244

Incoming Non-self Citations Over Time

Authors

1. Liwei Deng (University of Electronic Science and Technology of China)
2. Penghao Chen (University of Electronic Science and Technology of China)
3. Ximu Zeng (University of Electronic Science and Technology of China)
4. Tianfu Wang (University of Science and Technology Beijing)
5. Yan Zhao (Shenzhen University)
6. Kai Zheng (Shenzhen University)

BibTeX Citation

@article{deng_vldb25,
        title = {{Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search}},
        author = {Deng, Liwei and Chen, Penghao and Zeng, Ximu and Wang, Tianfu and Zhao, Yan and Zheng, Kai},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {3},
        pages = {812--821},
        doi = {10.14778/3712221.3712244},
        url = {https://doi.org/10.14778/3712221.3712244},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,526	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.166074e-05
10,163	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.0682654e-05
10,323	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.0346745e-05
10,324	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0346745e-05
10,511	Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]	2026	SIGMOD	4.9793485e-05
10,540	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.9793485e-05
10,709	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9793485e-05
10,726	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020445545
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015149775
804	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013832333
839	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013547412
1,170	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.0001171991
1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010523759
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010103316
1,613	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010072237
1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.0001004502
1,684	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	9.8801753e-05
2,265	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.7238222e-05
2,503	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	8.3786151e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
2	345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
3	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
4	2,113	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
5	650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
6	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
7	9,329	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
8	10,540	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD
9	1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
10	1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD