Bayesian Locality Sensitive Hashing for Fast Similarity Search

Venu Satuluri; Srinivasan Parthasarathy

Source-linked AI summary

Bayesian Locality Sensitive Hashing for Fast Similarity Search

Venu Satuluri, Srinivasan Parthasarathy

arXiv:1110.1328v3Oct 6, 2011cs.DBcs.AIcs.DScs.IR

TL;DR

All-pairs similarity search must identify object pairs above a threshold, but LSH methods traditionally use hashing mainly for candidate generation. BayesLSH applies Bayesian inference to candidate pruning and similarity estimation, yielding controllable guarantees and typically 2x-20x speedups over baselines.

Problem
LSH-based similarity search traditionally uses hashing for candidate generation, while standard estimation cannot jointly optimize accuracy and performance or exploit early candidate pruning.
Method
BayesLSH uses Bayesian inference over LSH hashes for candidate pruning and similarity estimation, while BayesLSH-Lite prunes candidates and computes remaining similarities exactly.
Results
2x-20x speedups over baseline approaches are reported across six real datasets with AllPairs and LSH candidate generation, while recall is generally at least 97%.
Takeaways & Limitations
BayesLSH provides probabilistic accuracy and recall guarantees with intuitive tuning and no manual setting of the number of hashes.
Takeaways & Limitations
For Cosine similarity, the relevant LSH family corresponds to a slightly different similarity measure, 1−θ(x,y).

Abstract

from arXiv · show

Given a collection of objects and an associated similarity measure, the all-pairs similarity search problem asks us to find all pairs of objects with similarity greater than a certain user-specified threshold. Locality-sensitive hashing (LSH) based methods have become a very popular approach for this problem. However, most such methods only use LSH for the first phase of similarity search - i.e. efficient indexing for candidate generation. In this paper, we present BayesLSH, a principled Bayesian algorithm for the subsequent phase of similarity search - performing candidate pruning and similarity estimation using LSH. A simpler variant, BayesLSH-Lite, which calculates similarities exactly, is also presented. BayesLSH is able to quickly prune away a large majority of the false positive candidate pairs, leading to significant speedups over baseline approaches. For BayesLSH, we also provide probabilistic guarantees on the quality of the output, both in terms of accuracy and recall. Finally, the quality of BayesLSH's output can be easily tuned and does not require any manual setting of the number of hashes to use for similarity estimation, unlike standard approaches. For two state-of-the-art candidate generation algorithms, AllPairs and LSH, BayesLSH enables significant speedups, typically in the range 2x-20x for a wide variety of datasets.

1. INTRODUCTION

Similarity search retrieves objects or object pairs exceeding a similarity threshold, and LSH-based methods traditionally use hashing mainly for candidate generation. BayesLSH extends LSH into candidate verification and similarity estimation, producing tunable accuracy, recall guarantees, and substantial speedups.

Problem: Similarity search retrieves all object pairs whose similarity exceeds a user-specified threshold, supporting applications including clustering, retrieval, and near-duplicate detection.Approximate similarity assessments may be acceptable when they reduce running time.
Existing pipeline: LSH-based search generates candidates by hashing objects repeatedly and pairing objects that share at least one hash bucket.Traditional candidate verification then computes similarities exactly or estimates them from hash agreements.
Approach: BayesLSH applies Bayesian inference to hashes during candidate verification, estimating threshold probabilities and similarities while pruning unpromising candidate pairs.BayesLSH-Lite performs candidate pruning but computes similarities exactly.
Guarantees: BayesLSH provides probabilistic guarantees for retaining likely true positives and bounding similarity-estimation error.The guarantees are parameterized by recall ǫ and accuracy parameters δ and γ.
Practical advantages: BayesLSH supports intuitive quality tuning through γ, δ, and ǫ without manually selecting the number of hashes used for similarity estimation.The method applies to similarity measures with LSH families, including demonstrated Cosine and Jaccard similarities, and supports binary and real-valued vectors.
Evaluation: 2x-20x speedups over baseline approaches are reported across six real datasets when BayesLSH variants are combined with AllPairs and LSH candidate generation.BayesLSH typically achieves these gains by pruning false-positive candidates while maintaining recall generally at 97% or above.

2. BACKGROUND

LSH constructs efficient similarity-search indices by exploiting the higher collision probability of similar objects. After candidate generation, similarity can be computed exactly or estimated from hash agreement, but estimation accuracy and efficiency remain central concerns.

LSH principle: LSH is defined as a family of hash functions in which similar objects are likely to collide under a randomly selected hash function.The definition applies to each object pair, not to a randomly sampled pair.
Similarity measures: LSH supports Jaccard, Cosine, and kernelized similarity functions.These families enable hashing-based indexing for multiple similarity measures.
Candidate generation via LSH: Candidate-generation indices form multiple signatures from concatenated hashes and output pairs sharing at least one signature.Hash tables make retrieval of objects sharing signatures efficient.
Candidate verification: Candidate similarities are verified either by exact calculation or by estimating similarity as the fraction of agreeing hashes.Hash-based estimation is often faster when candidate counts or exact similarity costs are large.
Open issue: The unresolved background problem is whether hash-based similarity estimation is sufficiently accurate and can be made faster while preserving the indexing benefits of LSH.The paper addresses this question in its subsequent method development.

3. CLASSICALSIMILARITY ESTIMATION FOR LSH

Classical LSH similarity estimation uses observed hash agreements to produce point estimates, but its variance depends on the unknown similarity. Consequently, one global hash count cannot simultaneously optimize accuracy and performance, while early pruning opportunities are missed.

Inference formulation: Similarity estimation with LSH treats the similarity as an inferred parameter and successive hash comparisons as observed data.The underlying probability model is supplied by the LSH equation.
Estimator behavior: The standard estimator is unbiased, but its variance depends on the similarity being estimated, requiring different hash counts for different similarities.The variance is proportional to s(1−s)/n.
Hash-count variation: 350 hashes are needed for similarity 0.5, whereas 16 hashes suffice for similarity 0.95 when δ = γ = 0.05.Similarities near 0.5 require substantially more hashes than similarities near 0 or 1.
Accuracy requirements: Stricter accuracy requirements further increase the differences in required hash counts across similarity values.The required count is determined by concentrating the estimate within δ of the true similarity with probability 1−γ.
Tuning limitation: Because the true similarity is unknown beforehand, standard estimation cannot choose one hash count that jointly achieves optimal performance and accuracy across a dataset.Using too many hashes harms performance, while using too few harms accuracy.
Early pruning: Standard estimation also misses early pruning opportunities, such as discarding a candidate after only 10 matches among its first 100 hashes when the threshold is 0.8.The example motivates pruning candidates before comparing all planned hashes.

4. CANDIDATE PRUNING AND SIMILARITY ESTIMATION USING BAYESLSH

BayesLSH uses Bayesian inference over LSH hash matches to prune unlikely candidate pairs and estimate similarities with probabilistic control. BayesLSH-Lite retains Bayesian pruning but computes surviving similarities exactly, while both variants support concrete LSH-based instantiations.

Bayesian inference: Bayesian inference treats similarity as uncertain and uses observed hash matches to derive a posterior distribution for each candidate pair.The posterior supports threshold probabilities, similarity estimates, and concentration probabilities.
BayesLSH algorithm: BayesLSH incrementally compares hashes, pruning a pair when its posterior probability of exceeding the threshold becomes sufficiently small.Unpruned pairs continue until the similarity estimate is sufficiently concentrated, then enter the output with an estimate.
BayesLSH-Lite: BayesLSH-Lite uses the same posterior threshold test but computes the similarities of unpruned pairs exactly, with a maximum-hash parameter h.It can be faster when exact similarity calculations are cheap, such as for binary or small object representations.
Parameterization: BayesLSH-Lite removes the need for δ and γ because its final similarity calculations are exact, while recall remains controlled through ǫ.BayesLSH instead exposes δ and γ for similarity-estimation accuracy and concentration.
Instantiation scope: The framework is intended to work with LSH families for different similarity measures and does not assume a particular candidate-generation algorithm.The supplied section introduces a Jaccard instantiation and identifies cosine as another target measure.
Jaccard instantiation: For Jaccard similarity, the method uses minwise independent permutations, a binomial likelihood, and a conjugate Beta prior for tractable inference.The Beta prior can be uniform or estimated from sampled candidate-pair similarities.

5. EXPERIMENTS

Experiments on six diverse real datasets show that BayesLSH variants usually accelerate AllPairs and LSH while preserving high recall and accurate similarity estimates. The main gains come from pruning false-positive candidates after examining few hashes, with variant performance depending on threshold, representation, and dataset characteristics.

Datasets and setup: Experiments covered six real datasets, including text corpora and graph datasets, with realistic applications for all-pairs similarity search.The evaluation included weighted and binary representations using Cosine and Jaccard similarity.
Overall results: BayesLSH variants usually improved AllPairs and LSH running times by 2x-20x, while recall was usually above 97%.Similarity estimates usually had no more than 5% of output pairs with error above 0.05.
Variant behavior: BayesLSH and BayesLSH-Lite often had comparable speeds because pruning drives most of the benefit, while hashing overhead distinguishes their performance.BayesLSH-Lite was faster at higher thresholds or when exact similarity calculations were cheaper.
Baseline behavior: BayesLSH improved both LSH and AllPairs even when either baseline was already fast, although dataset structure determined which baseline was stronger.AllPairs tended to favor smaller average vector lengths and greater variance in vector lengths, while LSH was faster on several other datasets.
Accuracy: BayesLSH estimates had more consistent accuracy across thresholds than standard LSH approximation using a fixed 2048 hashes.Standard LSH produced too many errors at low thresholds and too few at high thresholds, whereas BayesLSH maintained similar accuracies.

6. CONCLUSIONS AND FUTURE WORK

BayesLSH combines Bayesian inference with LSH for candidate verification and similarity estimation, complementing candidate-generation methods. The paper reports broad speedups and identifies extensions to learned metrics and nearest-neighbor retrieval as future work.

Conclusions: BayesLSH and BayesLSH-Lite provide general candidate verification and similarity estimation algorithms that complement candidate-generation research.The approach is presented as largely orthogonal to indexing strategies focused on candidate generation.
Conclusions: BayesLSH variants are typically the fastest algorithms across diverse datasets and similarity measures, while enabling significant speedups for AllPairs and LSH.The conclusion reports this pattern across the two state-of-the-art candidate-generation algorithms.
Future work: Future work includes extending BayesLSH to learned kernelized metrics and developing a BayesLSH-Lite analogue for nearest-neighbor retrieval with Euclidean distances.The proposed extensions may require exact final-distance computation for nearest-neighbor retrieval.

(a) Prior distributions

The paper contrasts several very different prior distributions for similarity with their posterior behavior after hash outcomes are observed. Figure 5 emphasizes that the resulting posteriors become very similar after only a small number of hashes.

Prior distributions: Figure 5 compares posterior distributions produced from very different prior distributions after observing hash outcomes.The figure focuses on how posterior distributions change after examining hashes.
Prior distributions: After a small number of observed hashes, the different prior distributions converge to very similar posteriors.The figure caption states the convergence pattern directly.
Prior distributions: The comparison highlights the influence of observed outcomes on posterior distributions rather than treating the prior alone as decisive.This point summarizes the comparison encoded by the figure without adding a quantitative claim.

A. THE INFLUENCE OF PRIOR VS. DATA

The paper examines how prior distributions and observed hash agreements jointly determine posterior similarity estimates. In a cosine-similarity example, posteriors from initially different priors become close after 32 hashes and converge further as more hashes are observed.

Data versus prior: For a pair with cosine similarity 0.70, three initially different priors produce posteriors that are already quite close after 32 hashes and 24 agreements.The transformed similarity is r(x,y)=0.75 in this example.
Data versus prior: The posteriors become closer quickly as the number of observed hashes increases.The passage describes this trend across Figures 5(c) and 5(d).
Data versus prior: After n hashes with m agreements, the likelihood is s^m(1 − s)^(n−m) and becomes more sharply concentrated as n increases.The passage explains this concentration as the mechanism behind the diminishing influence of differing priors.