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.00020063233
Overall Rank: 368 | 97.45%
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
114	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00032660283
476	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00017896807
723	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014720507
957	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013044785
1,551	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010436352
1,559	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.0001040748
1,601	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010322689
1,985	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.4487363e-05
2,091	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.254357e-05
2,179	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.0778698e-05
2,199	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.0284127e-05
2,751	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.2307473e-05
2,766	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.2159054e-05
2,778	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.1962724e-05
3,678	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.2688557e-05
3,779	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.1851123e-05
3,787	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	7.1790151e-05
3,799	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.1682127e-05
3,880	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.1067854e-05
4,247	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	6.8706347e-05
4,520	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	6.7182526e-05
4,560	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.6961568e-05
4,890	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.5242948e-05
5,066	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.444669e-05
5,190	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.3923371e-05
5,809	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.1420277e-05
6,300	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.9827236e-05
6,658	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	5.870738e-05
6,660	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.8703922e-05
6,741	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	5.8440692e-05
6,833	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.8190903e-05
6,834	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.8190903e-05
6,950	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	5.8013545e-05
7,182	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	5.7376349e-05
7,231	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	5.721049e-05
7,504	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6637827e-05
7,619	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.6394887e-05
8,181	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.5389119e-05
8,193	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.5370767e-05
8,259	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.521179e-05
8,532	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.4767909e-05
8,680	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.4530452e-05
9,219	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.3637135e-05
9,243	LeaFi: Data Series Indexes on Steroids with Learned Filters	2025	SIGMOD	5.3572577e-05
9,880	VStream: A Distributed Streaming Vector Search System	2025	VLDB	5.2533454e-05
9,910	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	5.2443653e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	5.1725247e-05
10,068	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1725247e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.1725247e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.1725247e-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
23	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00055560094
392	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019447635
615	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015854124
705	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00014912921
1,018	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00012687864

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	5.1725247e-05
3,880	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.1067854e-05
592	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.0001605665
615	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015854124
1,018	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00012687864
5,809	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.1420277e-05
1,601	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010322689
2,199	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.0284127e-05
3,678	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.2688557e-05
392	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019447635