Consider collections @math and @math of red and blue sets, respectively. Bichromatic Closest Pair is the problem of finding a pair from @math that has similarity higher than a given threshold according to some similarity measure. Our focus here is the classic Jaccard similarity @math for @math . We consider the approximate version of the problem where we are given thresholds @math and wish to return a pair from @math that has Jaccard similarity higher than @math if there exists a pair in @math with Jaccard similarity at least @math . The classic locality sensitive hashing (LSH) algorithm of Indyk and Motwani (STOC '98), instantiated with the MinHash LSH function of , solves this problem in @math time if @math . In particular, for @math , the approximation ratio @math increases polynomially in @math . In this paper we give a corresponding hardness result. Assuming the Orthogonal Vectors Conjecture (OVC), we show that there cannot be a general solution that solves the Bichromatic Closest Pair problem in @math time for @math . Specifically, assuming OVC, we prove that for any @math there exists an @math such that Bichromatic Closest Pair with Jaccard similarity requires time @math for any choice of thresholds @math , that satisfy @math .
Similarity search can be performed in several ways -- a popular technique is Locality Sensitive Hashing (LSH) @cite_4 which attempts to collect similar items in buckets in order to reduce the number of sets needed to check similarity against. We can for example use Broder's MinHash @cite_0 with locality sensitive hashing to solve Bichromatic Closest Pair with Jaccard similarity in time @math when @math for any @math . This is done by ensuring that the collision probability for pairs with similarity @math is @math and the collision probability for pairs with similarity @math is @math . Hashing @math times means that we find a pair with similarity @math if one exists. The ChosenPath method presented in @cite_9 also uses the LSH framework to solve Bichromatic Closest Pair with Braun-Blanquet similarity in time @math for thresholds @math .
@cite_0 @cite_9 @cite_4
2574633002 2156855109 2108484928 2272255885
We consider the problem of approximate set similarity search under Braun-Blanquet similarity B(x, y) = |x ∩ y| max(|x|, |y|). The (b1, b2)-approximate Braun-Blanquet similarity search problem is to preprocess a collection of sets P such that, given a query set q, if there exists x E P with B(q, x) ≥ b1, then we can efficiently return x′ E P with B(q, x′) > b2. We present a simple data structure that solves this problem with space usage O(n1+ρlogn + ∑x e P|x|) and query time O(|q|nρ logn) where n = |P| and ρ = log(1 b1) log(1 b2). Making use of existing lower bounds for locality-sensitive hashing by O' (TOCT 2014) we show that this value of ρ is tight across the parameter space, i.e., for every choice of constants 0 In the case where all sets have the same size our solution strictly improves upon the value of ρ that can be obtained through the use of state-of-the-art data-independent techniques in the Indyk-Motwani locality-sensitive hashing framework (STOC 1998) such as Broder's MinHash (CCS 1997) for Jaccard similarity and 's cross-polytope LSH (NIPS 2015) for cosine similarity. Surprisingly, even though our solution is data-independent, for a large part of the parameter space we outperform the currently best data-dependent method by Andoni and Razenshteyn (STOC 2015). 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. Our algorithms are 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. Nearest neighbor (NN) search in high dimensional space is an essential query in many multimedia retrieval applications. Due to the curse of dimensionality, existing index structures might perform even worse than a simple sequential scan of data when answering exact NN query. To improve the efficiency of NN search, locality sensitive hashing (LSH) and its variants have been proposed to find approximate NN. They adopt hash functions that can preserve the Euclidean distance so that similar objects have a high probability of colliding in the same bucket. Given a query object, candidate for the query result is obtained by accessing the points that are located in the same bucket. To improve the precision, each hash table is associated with m hash functions to recursively hash the data points into smaller buckets and remove the false positives. On the other hand, multiple hash tables are required to guarantee a high retrieval recall. Thus, tuning a good tradeoff between precision and recall becomes the main challenge for LSH. Recently, locality sensitive B-tree(LSB-tree) has been proposed to ensure both quality and efficiency. However, the index uses random I O access. When the multimedia database is large, it requires considerable disk I O cost to obtain an approximate ratio that works in practice. In this paper, we propose a novel index structure, named HashFile, for efficient retrieval of multimedia objects. It combines the advantages of random projection and linear scan. Unlike the LSH family in which each bucket is associated with a concatenation of m hash values, we only recursively partition the dense buckets and organize them as a tree structure. Given a query point q, the search algorithm explores the buckets near the query object in a top-down manner. The candidate buckets in each node are stored sequentially in increasing order of the hash value and can be efficiently loaded into memory for linear scan. HashFile can support both exact and approximate NN queries. Experimental results show that HashFile performs better than existing indexes both in answering both types of NN queries. Locality-sensitive hashing (LSH) has emerged as the dominant algorithmic technique for similarity search with strong performance guarantees in high-dimensional spaces. A drawback of traditional LSH schemes is that they may have , i.e., the recall is less than 100 . This limits the applicability of LSH in settings requiring precise performance guarantees. Building on the recent theoretical "CoveringLSH" construction that eliminates false negatives, we propose a fast and practical covering LSH scheme for Hamming space called . Inheriting the design benefits of CoveringLSH our method avoids false negatives and always reports all near neighbors. Compared to CoveringLSH we achieve an asymptotic improvement to the hash function computation time from @math to @math , where @math is the dimensionality of data and @math is the number of hash tables. Our experiments on synthetic and real-world data sets demonstrate that is comparable (and often superior) to traditional hashing-based approaches for search radius up to 20 in high-dimensional Hamming space.