Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases

Summary: tau-monotonic graph (tau-MG) for ANN in multi-dimensional databases; exploits a tau-monotonic property to guarantee exact NN when dist(q,NN) ≤ tau and to beat existing PG-based search times. Approximate tau-monotonic neighborhood graph (tau-MNG) lowers construction cost by restricting monotonicity to neighborhoods and adds a distance-reduction optimization; experiments on real datasets show gains over prior PG-based ANN methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hde821a969747bbf0
Venue: SIGMOD
Year: 2023
Pagerank: 0.0001172922
Overall Rank: 1,166 | 92.17%
DOI: 10.1145/3588908

Incoming Non-self Citations Over Time

Authors

1. Yun Peng (Guangdong University of Technology; Hong Kong Baptist University)
2. Byron Choi (Hong Kong Baptist University)
3. Tsz Nam Chan (Hong Kong Baptist University)
4. Jianye Yang (Guangdong University of Technology)
5. Jianliang Xu (Hong Kong Baptist University)

BibTeX Citation

@inproceedings{peng_sigmod23,
        title = {{Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases}},
        author = {Peng, Yun and Choi, Byron and Chan, Tsz Nam and Yang, Jianye and Xu, Jianliang},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588908},
        url = {https://dl.acm.org/doi/10.1145/3588908},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
803	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013838349
2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	8.0204877e-05
3,378	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.3542798e-05
3,882	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.9477043e-05
4,051	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8266649e-05
4,600	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5055567e-05
5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0907372e-05
6,230	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.842393e-05
6,244	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8355024e-05
6,921	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.641565e-05
7,006	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6212001e-05
7,267	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5677188e-05
7,337	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.5472184e-05
7,594	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4865404e-05
7,706	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	5.4724414e-05
8,350	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3481387e-05
8,416	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.3341916e-05
8,651	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.2929907e-05
10,094	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0783086e-05
10,231	CoTra: Towards Efficient and Scalable Distributed Vector Search with RDMA	2026	SIGMOD	5.0547568e-05
10,328	PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs	2026	SIGMOD	5.0322912e-05
10,330	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.0322912e-05
10,331	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0322912e-05
10,332	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.0322912e-05
10,333	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.0322912e-05
10,407	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.9769913e-05
10,429	Balancing Global and Local: Representative Sampling for Large-Scale Vector Data	2026	SIGMOD	4.9769913e-05
10,468	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	2026	SIGMOD	4.9769913e-05
10,502	PathSeer: Adaptive Neighbor Handling for Efficient Filtered ANN Search	2026	SIGMOD	4.9769913e-05
10,522	Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]	2026	SIGMOD	4.9769913e-05
10,551	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.9769913e-05
10,558	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD	4.9769913e-05
10,574	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.9769913e-05
10,646	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD	4.9769913e-05
10,653	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.9769913e-05
10,688	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	4.9769913e-05
10,691	Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views: [Experiments & Analysis]	2026	SIGMOD	4.9769913e-05
10,719	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9769913e-05
10,736	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.9769913e-05
10,755	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.9769913e-05
10,844	ConANN: Conformal Approximate Nearest Neighbor Search	2026	VLDB	4.9769913e-05
10,877	CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data	2026	VLDB	4.9769913e-05
10,919	TEngineDB-V: An OLAP-Native Vector Search System for Large-k Workloads at Tencent	2026	VLDB	4.9769913e-05
10,922	RED-ANNS: An RDMA-Enabled Distributed Framework for Graph-Based Approximate Nearest Neighbor Search	2026	VLDB	4.9769913e-05
11,037	Advances of Query Processing in Vector Databases	2026	VLDB	4.9769913e-05
11,057	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9769913e-05
11,600	DARKER: Efficient Transformer with Data-driven Attention Mechanism for Time Series	2024	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037145866
344	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020455839
838	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.0001355054
1,527	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010350688

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,407	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS
2	10,839	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
3	10,083	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
4	1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
5	10,837	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
6	10,574	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
7	4,051	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
8	344	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
9	74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
10	10,333	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD