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: 4552
Venue: SIGMOD
Year: 2012
Pagerank: 0.000193396
Overall Rank: 605 | 95.80%
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
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
1,269	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00012930432
1,757	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010660932
1,971	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.893198e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
2,324	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.0326444e-05
2,435	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	8.8252237e-05
2,811	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.0806307e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
3,056	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.6432146e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,510	Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources	2013	SIGMOD	7.0258619e-05
3,624	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	6.9056e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.092287e-05
4,598	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0586236e-05
4,609	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	6.0528541e-05
4,751	ODIN: Automated Drift Detection and Recovery in Video Analytics	2020	VLDB	5.9485403e-05
5,129	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	5.6755204e-05
5,184	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6406991e-05
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05
5,233	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6131833e-05
5,456	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	5.4976692e-05
5,469	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4898192e-05
5,569	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.4290942e-05
5,996	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2415551e-05
6,074	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.2242306e-05
6,107	Continuously Adaptive Similarity Search	2020	SIGMOD	5.2066612e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
7,204	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.8015761e-05
7,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.792836e-05
7,301	Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search	2018	SIGMOD	4.768971e-05
7,316	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	4.7640297e-05
7,700	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	4.6744372e-05
7,843	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6367909e-05
8,209	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5581054e-05
8,245	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5514956e-05
8,497	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	4.4981377e-05
8,656	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	4.4737647e-05
9,303	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.358026e-05
9,822	DIDS: Double Indices and Double Summarizations for Fast Similarity Search	2024	VLDB	4.2757088e-05
9,881	VStream: A Distributed Streaming Vector Search System	2025	VLDB	4.2643674e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1945683e-05
10,068	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	4.1945683e-05
10,110	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	4.1945683e-05
10,224	SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search	2026	VLDB	4.1945683e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1945683e-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.0032169493
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
2,024	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.7519678e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,303	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.358026e-05
3,938	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	6.6155909e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
3,056	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.6432146e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752