Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting

Summary: Collision Counting LSH (C2LSH): dynamic compound LSH from m single LSHs; a point o is a candidate for q if its collision count with q exceeds l. m independent of dimensionality; C2LSH offers guarantees on query quality and outperforms LSB-forest in high-D. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4553
Venue: SIGMOD
Year: 2012
Pagerank: 0.0001982328
Overall Rank: 579 | 95.98%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 55 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109
1,252	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013023834
1,934	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010047294
1,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
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,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,019	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.699097e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,515	Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources	2013	SIGMOD	7.0191008e-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,749	ODIN: Automated Drift Detection and Recovery in Video Analytics	2020	VLDB	5.9428569e-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,218	Neighbor-Sensitive Hashing	2016	VLDB	5.6204105e-05
5,236	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6077913e-05
5,477	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4856699e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
6,000	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2365238e-05
6,080	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.219249e-05
6,111	Continuously Adaptive Similarity Search	2020	SIGMOD	5.2016636e-05
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
7,198	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.79852e-05
7,235	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.7882389e-05
7,255	Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search	2018	SIGMOD	4.7821026e-05
7,307	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	4.7623207e-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,208	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5537353e-05
8,239	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5471319e-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
9,267	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.3647353e-05
9,821	DIDS: Double Indices and Double Summarizations for Fast Similarity Search	2024	VLDB	4.2716118e-05
9,880	VStream: A Distributed Streaming Vector Search System	2025	VLDB	4.2602815e-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,224	SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search	2026	VLDB	4.1905499e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
399	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00024359304
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
2,012	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.8007613e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,267	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.3647353e-05
3,933	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	6.6164676e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
3,019	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.699097e-05
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
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943