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). We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in R d , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree. The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes and simplifies the results from those papers.