Set similarity search beyond MinHash

DOI10.1145/3055399.3055443MaRDI QIDQ4978050zbMATH OpenOpenAlexFDO

Authors Tobias Christiani, Rasmus Pagh

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07710

zbMATH Keywords

Braun-Blanquet similarityJaccard similaritylocality-sensitive hashingMinHashnear neighbor searchsimilarity search

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Abstract: We consider the problem of approximate set similarity search under Braun-Blanquet similarity $B(mathbfx,mathbfy)=|mathbfxcapmathbfy|/max(|mathbfx|,|mathbfy|)$. The $(b_2,b_2)$-approximate Braun-Blanquet similarity search problem is to preprocess a collection of sets $P$ such that, given a query set $mathbfq$, if there exists $mathbfxinP$ with $B(mathbfq,mathbfx)geq{b}_1$, then we can efficiently return $mathbf{x}^{\prime }inP$ with $B(mathbfq,mathbf{x}^{\prime })>b_2$. We present a simple data structure that solves this problem with space usage $O(n^{1+ho}logn+su{m}_{mathbfxinP}|mathbfx|)$ and query time $O(|mathbfq|n^{ho}logn)$ where $n=|P|$ and $ho=log(1/b_1)/log(1/b_2)$. Making use of existing lower bounds for locality-sensitive hashing by O'Donnell et al. (TOCT 2014) we show that this value of $ho$ is tight across the parameter space, i.e., for every choice of constants $0<b_2<b_1<1$. In the case where all sets have the same size our solution strictly improves upon the value of $ho$ 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 Andoni et al.'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).

Recommendations

• Index structures for fast similarity search for binary vectors
• Index structures for fast similarity search for real-valued vectors. I
• Improving MinHash via the containment index with applications to metagenomic analysis
• The exact probability law for the approximated similarity from the Minhashing method
• Locality-sensitive hashing without false negatives

Cited in

(11)

• ForestDSH: a universal hash design for discrete probability distributions
• Dimension independent similarity computation
• Efficient processing of similarity search on uncertain set-valued data
• Fingerprints for highly similar streams
• Exact and approximate maximum inner product search with LEMP
• Hardness of bichromatic closest pair with Jaccard similarity
• Estimation of three-way similarities based on connected bit Minwise Hash
• The exact probability law for the approximated similarity from the Minhashing method
• Index structures for fast similarity search for binary vectors
• Approximate similarity search under edit distance using locality-sensitive hashing
• Improved space-efficient approximate nearest neighbor search using function inversion

This page was built for publication: Set similarity search beyond MinHash

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978050)