Hardness of bichromatic closest pair with Jaccard similarity
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- OA-Hardness of Bichromatic Closest Pair with
Forlagets udgivne version, 513 KB, PDF-dokument
Consider collections A and B of red and blue sets, respectively. Bichromatic Closest Pair is the problem of finding a pair from A x B that has similarity higher than a given threshold according to some similarity measure. Our focus here is the classic Jaccard similarity |a cap b|/|a cup b| for (a,b) in A x B. We consider the approximate version of the problem where we are given thresholds j_1 > j_2 and wish to return a pair from A x B that has Jaccard similarity higher than j_2 if there exists a pair in A x B with Jaccard similarity at least j_1. The classic locality sensitive hashing (LSH) algorithm of Indyk and Motwani (STOC '98), instantiated with the MinHash LSH function of Broder et al., solves this problem in Õ(n^(2-delta)) time if j_1 >= j_2^(1-delta). In particular, for delta=Omega(1), the approximation ratio j_1/j_2 = 1/j_2^delta increases polynomially in 1/j_2. 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 O(n^(2-Omega(1))) time for j_1/j_2 = 1/j_2^o(1). Specifically, assuming OVC, we prove that for any delta>0 there exists an epsilon>0 such that Bichromatic Closest Pair with Jaccard similarity requires time Omega(n^(2-delta)) for any choice of thresholds j_2 < j_1 < 1-delta, that satisfy j_1 <= j_2^(1-epsilon).
Originalsprog | Engelsk |
---|---|
Titel | 27th Annual European Symposium on Algorithms, ESA 2019 |
Redaktører | Michael A. Bender, Ola Svensson, Grzegorz Herman |
Antal sider | 13 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2019 |
Artikelnummer | 74 |
ISBN (Elektronisk) | 9783959771245 |
DOI | |
Status | Udgivet - 2019 |
Begivenhed | 27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Tyskland Varighed: 9 sep. 2019 → 11 sep. 2019 |
Konference
Konference | 27th Annual European Symposium on Algorithms, ESA 2019 |
---|---|
Land | Tyskland |
By | Munich/Garching |
Periode | 09/09/2019 → 11/09/2019 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 144 |
ISSN | 1868-8969 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 238368920