Bayesian Locality Sensitive Hashing for Fast Similarity Search

Summary: BayesLSH prunes false positives and refines similarity after LSH. BayesLSH-Lite computes exact similarities; offers probabilistic accuracy/recall guarantees, tunable output without fixed hash counts, and 2x-20x speedups versus AllPairs/LSH. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1f03ea3a460e22ca
Venue: VLDB
Year: 2012
Pagerank: 0.00012646771
Overall Rank: 992 | 93.34%
DOI: 10.14778/2140436.2140440

Incoming Non-self Citations Over Time

Authors

1. Venu Satuluri (Ohio State University)
2. Srinivasan Parthasarathy (Ohio State University)

BibTeX Citation

@article{satuluri_vldb12,
        title = {{Bayesian Locality Sensitive Hashing for Fast Similarity Search}},
        author = {Satuluri, Venu and Parthasarathy, Srinivasan},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {5},
        pages = {430--441},
        doi = {10.14778/2140436.2140440},
        url = {https://doi.org/10.14778/2140436.2140440},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010523759
1,530	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010344205
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010103316
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
2,505	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	8.3779738e-05
2,513	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3679178e-05
2,577	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	8.2738285e-05
2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8519256e-05
3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3910669e-05
3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1790375e-05
3,611	LEMP: Fast Retrieval of Large Entries in a Matrix Product	2015	SIGMOD	7.1628753e-05
3,809	On the Complexity of Inner Product Similarity Join	2016	PODS	7.0089846e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
4,571	SILKMOTH: An Efficient Method for Finding Related Sets with Maximum Matching Constraints	2017	VLDB	6.5286445e-05
4,856	Neighbor-Sensitive Hashing	2016	VLDB	6.3798143e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
6,397	Human-in-the-loop Data Integration	2017	VLDB	5.7989499e-05
7,833	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.443666e-05
9,086	Multivariate Correlations Discovery in Static and Streaming Data	2022	VLDB	5.2283159e-05
9,126	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.22387e-05
9,215	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.2056826e-05
9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1349531e-05
11,813	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	4.9793485e-05
12,035	MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1	2021	VLDB	4.9793485e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-05
12,563	PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data	2013	VLDB	4.9793485e-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
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
1,187	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.00011606901
1,923	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.3750526e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
2	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
3	9,674	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB
4	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
5	280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB
6	3,236	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
7	2,362	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
8	1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
9	4,958	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB
10	8,775	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD