Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search

Summary: Introduces query-aware bucket partitioning for LSH, anchoring random-projection buckets to each query rather than precomputing query-oblivious shifts. QALSH supports external-memory c-ANN for any c>1, improving quality and performance over C2LSH and LSB-Forest, especially in high dimensions. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h1cdf5bff75ef6c2d
Venue: VLDB
Year: 2016
Pagerank: 0.00021849337
Overall Rank: 297 | 98.01%
DOI: 10.14778/2850469.2850470
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Qiang Huang (Sun Yat-Sen University)
2. Jianlin Feng (Sun Yat-Sen University)
3. Yikai Zhang (Sun Yat-Sen University)
4. Qiong Fang (South China University of Technology)
5. Wilfred Ng (Hong Kong University of Science and Technology)

BibTeX Citation

@article{huang_vldb16,
        title = {{Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search}},
        author = {Huang, Qiang and Feng, Jianlin and Zhang, Yikai and Fang, Qiong and Ng, Wilfred},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {1},
        doi = {10.14778/2850469.2850470},
        url = {https://doi.org/10.14778/2850469.2850470},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 72 citing papers.

Rank	Citing 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
648	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015156941
803	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013838349
838	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.0001355054
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
1,600	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010111099
1,603	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010100279
1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.00010053127
1,894	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.4129766e-05
1,958	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3118048e-05
2,264	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.7286407e-05
2,444	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.4556406e-05
2,717	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	8.0953706e-05
2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	8.0204877e-05
2,821	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.9674226e-05
2,872	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.9191725e-05
2,955	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8111585e-05
3,378	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.3542798e-05
3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.209991e-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,347	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6457039e-05
4,600	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5055567e-05
5,222	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.2205593e-05
5,274	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.1985959e-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,620	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	6.0596841e-05
5,886	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.955484e-05
5,903	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	5.9512758e-05
6,132	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.8755887e-05
6,184	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.8567387e-05
6,208	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.8479648e-05
6,612	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	5.732933e-05
6,873	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.6572631e-05
7,006	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6212001e-05
7,098	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.5991152e-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,337	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.5472184e-05
7,600	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.4854217e-05
7,910	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.426303e-05
8,859	VStream: A Distributed Streaming Vector Search System	2025	VLDB	5.2621314e-05
8,972	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.2469075e-05
9,146	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.2199557e-05
9,535	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.1636285e-05
9,568	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	5.154741e-05
9,571	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	5.154741e-05
9,912	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1079647e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016350316
674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00014886449
927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013028642

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,041	MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1	2021	VLDB
2	3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
3	576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
4	562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
5	927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
6	5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
7	1,481	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
8	1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
9	2,955	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
10	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD