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.0001004502
Overall Rank: 1,625 | 89.08%
DOI: 10.14778/3594512.3594527

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
804	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013832333
2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	8.0242863e-05
3,385	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.3548612e-05
4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8298981e-05
4,598	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5086378e-05
5,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0936219e-05
5,886	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.9583046e-05
6,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8382662e-05
6,560	RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference	2026	VLDB	5.7482184e-05
6,895	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6536466e-05
6,919	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.644237e-05
7,004	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6238624e-05
7,264	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5703557e-05
7,305	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	5.5586007e-05
7,587	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4891389e-05
9,551	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1591583e-05
10,078	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	5.0830849e-05
10,089	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	5.0807138e-05
10,090	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0807138e-05
10,163	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.0682654e-05
10,210	Blocker and Matcher Can Mutually Benefit: A Co-Learning Framework for Low-Resource Entity Resolution	2024	VLDB	5.0596605e-05
10,321	PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs	2026	SIGMOD	5.0346745e-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,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.0346745e-05
10,395	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.9793485e-05
10,425	CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation	2026	SIGMOD	4.9793485e-05
10,449	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD	4.9793485e-05
10,461	GEM: A Native Graph-based Index for Multi-Vector Retrieval	2026	SIGMOD	4.9793485e-05
10,509	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9793485e-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,563	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.9793485e-05
10,624	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	4.9793485e-05
10,635	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD	4.9793485e-05
10,815	CRAFT: Corpus Relatedness Analysis Using Fourier Transforms	2026	VLDB	4.9793485e-05
10,836	HEXA: A Disjoint-Subgraph-Based Indexing Framework for Approximate Nearest Neighbor Search at Billion Scale	2026	VLDB	4.9793485e-05
10,851	GAS: A Lightweight Framework for Filtered Search over Wide-table Vectors	2026	VLDB	4.9793485e-05
10,868	CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data	2026	VLDB	4.9793485e-05
11,028	Advances of Query Processing in Vector Databases	2026	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
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
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
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
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013025904
1,328	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011003106
1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010523759
11,978	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
2	562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
3	4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
4	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
5	5,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
6	1,530	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD
7	298	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,485	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