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 .
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).