Beyond Pairwise Provably Fast Algorithms For Approximate k-way Similarity Search

Anshumali Shrivastava, Ping Li. Neural Information Processing Systems 2013

[Paper]    
Independent LSH NEURIPS

We go beyond the notion of pairwise similarity and look into search problems with \(k\)-way similarity functions. In this paper, we focus on problems related to 3-way Jaccard similarity: \(\mathcal{R}^{3way}= \frac{

S_1 \cap S_2 \cap S_3

}{

S_1 \cup S_2 \cup S_3

}\), \(S_1, S_2, S_3 \in \mathcal{C}\), where \(\mathcal{C}\) is a size \(n\) collection of sets (or binary vectors). We show that approximate \(\mathcal{R}^{3way}\) similarity search problems admit fast algorithms with provable guarantees, analogous to the pairwise case. Our analysis and speedup guarantees naturally extend to \(k\)-way resemblance. In the process, we extend traditional framework of locality sensitive hashing (LSH) to handle higher order similarities, which could be of independent theoretical interest. The applicability of \(\mathcal{R}^{3way}\) search is shown on the Google sets” application. In addition, we demonstrate the advantage of \(\mathcal{R}^{3way}\) resemblance over the pairwise case in improving retrieval quality.”

Similar Work