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

Summary: Proposes QALSH, a query-aware LSH for c-ANN in external memory that uses the query as an anchor to partition buckets, removing the need for a random shift. It supports any c>1, provides theoretical query guarantees, and empirically outperforms C2LSH and LSB-Forest, especially in high dimensions with c<2. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11212
Venue: VLDB
Year: 2016
Pagerank: 0.00019455943
Overall Rank: 596 | 95.86%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 65 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,347	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00012463441
1,934	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010047294
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,287	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.1004806e-05
2,434	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	8.8225986e-05
2,692	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.2857267e-05
2,772	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.1491893e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,403	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	7.1338786e-05
3,552	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	6.9765275e-05
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.0864316e-05
4,598	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	6.053944e-05
4,600	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0528015e-05
4,622	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	6.0356382e-05
4,869	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	5.8588434e-05
5,028	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	5.7447815e-05
5,186	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6352814e-05
5,236	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6077913e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
5,690	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	5.3699421e-05
6,000	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2365238e-05
6,001	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.2365238e-05
6,359	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.0912204e-05
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
6,970	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	4.8740302e-05
7,090	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	4.8318862e-05
7,198	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.79852e-05
7,307	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	4.7623207e-05
7,542	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	4.7103816e-05
7,612	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	4.6919232e-05
7,698	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	4.6699546e-05
7,848	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6323445e-05
8,239	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5471319e-05
8,430	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	4.508568e-05
8,495	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	4.4938255e-05
8,654	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	4.4694763e-05
8,780	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	4.4485568e-05
9,233	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	4.3648789e-05
9,296	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	4.3577746e-05
9,880	VStream: A Distributed Streaming Vector Search System	2025	VLDB	4.2602815e-05
9,913	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	4.2520778e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1905499e-05
10,068	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	4.1905499e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	4.1905499e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1905499e-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
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,539	MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1	2021	VLDB	4.1905499e-05
4,598	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	6.053944e-05
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328