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.00021833987
Overall Rank: 298 | 98.00%
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 72 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020445545
650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015149775
804	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013832333
839	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013547412
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
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010103316
1,613	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010072237
1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.0001004502
1,897	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.4092345e-05
1,957	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3159589e-05
2,265	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.7238222e-05
2,448	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.4494625e-05
2,726	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	8.0904995e-05
2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	8.0242863e-05
2,821	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.9711961e-05
2,871	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.9229231e-05
2,969	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8000797e-05
3,385	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.3548612e-05
3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.2123214e-05
3,881	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.9509289e-05
4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8298981e-05
4,346	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6488514e-05
4,598	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5086378e-05
5,238	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.2169207e-05
5,268	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.2015316e-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,619	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	6.062554e-05
5,886	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.9583046e-05
5,920	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	5.9475097e-05
6,181	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.8595125e-05
6,203	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.8507344e-05
6,609	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	5.7354155e-05
6,768	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.686858e-05
6,867	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.6599424e-05
7,004	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6238624e-05
7,096	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.601767e-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,593	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.4880197e-05
7,906	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.428873e-05
8,306	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.3583322e-05
8,849	VStream: A Distributed Streaming Vector Search System	2025	VLDB	5.2646236e-05
8,962	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.2493925e-05
9,136	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.2224279e-05
9,526	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.166074e-05
9,560	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	5.1571823e-05
9,563	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	5.1571823e-05
9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1103839e-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.00057568153
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00014886692
927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013025904

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,035	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,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
7	1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
8	1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
9	2,969	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