Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces

Summary: LSH-APG combines lightweight LSH with proximity graphs to cut ANN index construction cost while preserving high-quality greedy search. Incremental insertion and cardinality-insensitive maintenance address graph-index evolution, outperforming existing graph methods empirically. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hacf8b9bca2facac7
Venue: VLDB
Year: 2023
Pagerank: 0.00010053127
Overall Rank: 1,618 | 89.13%
DOI: 10.14778/3594512.3594527
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Xi Zhao (Hong Kong University of Science and Technology)
2. Yao Tian (Hong Kong University of Science and Technology)
3. Kai Huang (Hong Kong University of Science and Technology)
4. Bolong Zheng (Huazhong University of Science and Technology)
5. Xiaofang Zhou (Hong Kong University of Science and Technology)

BibTeX Citation

@article{zhao_vldb23,
        title = {{Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces}},
        author = {Zhao, Xi and Tian, Yao and Huang, Kai and Zheng, Bolong and Zhou, Xiaofang},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {8},
        pages = {1979--1991},
        doi = {10.14778/3594512.3594527},
        url = {https://doi.org/10.14778/3594512.3594527},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 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
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
5,886	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.955484e-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,562	RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference	2026	VLDB	5.7454973e-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,308	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	5.5559693e-05
7,594	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4865404e-05
8,350	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3481387e-05
8,821	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	5.2697314e-05
10,083	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	5.0806786e-05
10,094	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0783086e-05
10,168	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.0658661e-05
10,209	Blocker and Matcher Can Mutually Benefit: A Co-Learning Framework for Low-Resource Entity Resolution	2024	VLDB	5.0586032e-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,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,437	CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation	2026	SIGMOD	4.9769913e-05
10,460	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD	4.9769913e-05
10,472	GEM: A Native Graph-based Index for Multi-Vector Retrieval	2026	SIGMOD	4.9769913e-05
10,520	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor 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,574	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.9769913e-05
10,635	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	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,825	CRAFT: Corpus Relatedness Analysis Using Fourier Transforms	2026	VLDB	4.9769913e-05
10,846	HEXA: A Disjoint-Subgraph-Based Indexing Framework for Approximate Nearest Neighbor Search at Billion Scale	2026	VLDB	4.9769913e-05
10,860	GAS: A Lightweight Framework for Filtered Search over Wide-table Vectors	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
11,037	Advances of Query Processing in Vector Databases	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00045027197
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040363819
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037145866
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
344	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020455839
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016118297
927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013028642
1,325	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011016872
1,481	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010535847
11,984	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,798	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
2	4,051	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
3	562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
4	10,333	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
5	5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
6	1,527	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD
7	297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
8	576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
9	1,481	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
10	927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB