Fast Similarity Sketching

Dahlgaard Søren, Langhede Mathias Bæk Tejs, Houen Jakob Bæk Tejs, Thorup Mikkel. Arxiv 2017

[Paper]    
ARXIV Supervised

We consider the $\mathit{\text{Similarity Sketching}}$ problem: Given a universe $[u]=\{0,\dots ,u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that the Jaccard similarity $J(A,B)=|A\cap B|/|A\cup B|$ between sets $A$ and $B$ is preserved. More precisely, define $X_i=[S(A)[i]=S(B)[i]]$ and $X=\sum _{i\in [t]}{X}_i$. We want $E[X_i]=J(A,B)$, and we want $X$ to be strongly concentrated around $E[X]=t\cdot J(A,B)$ (i.e. Chernoff-style bounds). This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\mathit{\text{sketches}}$. Strong concentration is critical, for often we want to sketch many sets $B_1,\dots ,B_n$ so that we later, for a query set $A$, can find (one of) the most similar $B_i$. It is then critical that no $B_i$ looks much more similar to $A$ due to errors in the sketch. The seminal $t\times \mathit{\text{MinHash}}$ algorithm uses $t$ random hash functions $h_1,\dots ,h_t$, and stores $(\underset{a\in A}{min}{h}_1(A),\dots ,\underset{a\in A}{min}{h}_t(A))$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. (continued…)

Similar Work

• A Memory-efficient Sketch Method For Estimating High Similarities In Streaming Sets
• On Learning Semantic Representations For Million-scale Free-hand Sketches
• Sketchmate Deep Hashing For Million-scale Human Sketch Retrieval
• (b)-bit Sketch Trie Scalable Similarity Search On Integer Sketches