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: 11399
Venue: VLDB
Year: 2016
Pagerank: 0.00020920444
Overall Rank: 332 | 97.73%
DOI: 10.14778/2850469.2850470

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 68 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00019194947
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
1,430	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.0001080902
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
1,735	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.9004924e-05
1,760	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.8157819e-05
1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.4561907e-05
2,010	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.3085202e-05
2,303	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.7783079e-05
2,534	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.4561875e-05
2,572	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.4027322e-05
3,108	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.7499741e-05
3,240	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.6071649e-05
3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.5711218e-05
3,286	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	7.5596483e-05
3,335	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	7.5098031e-05
3,799	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.114484e-05
3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.067591e-05
4,116	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.892012e-05
4,712	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.5506649e-05
5,121	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.3577317e-05
5,223	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.3102417e-05
5,653	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.1332953e-05
5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0850924e-05
6,079	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.9850223e-05
6,093	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.978635e-05
6,148	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	5.9593368e-05
6,334	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.9093559e-05
6,404	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	5.8859287e-05
6,615	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	5.8214312e-05
6,691	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	5.8011086e-05
6,765	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.7808599e-05
6,956	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.7303405e-05
7,145	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6908957e-05
7,166	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6846045e-05
7,426	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.6211019e-05
7,745	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.5534781e-05
7,761	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.550467e-05
8,798	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.3698781e-05
9,236	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.3016261e-05
9,360	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.2819088e-05
9,377	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	5.2755515e-05
9,407	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	5.2751121e-05
9,889	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.1997534e-05
9,892	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	5.1997534e-05
10,036	VStream: A Distributed Streaming Vector Search System	2025	VLDB	5.173224e-05
10,209	CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation	2026	SIGMOD	5.093636e-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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934
990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00012796562

Semantically Similar Papers

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