Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search
Anshumali Shrivastava, Ping Li · 2013
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: R3way = |S1∩S2∩S3||S1∪S2∪S3 | , S1; S2; S3 ∈ C, where C is a size n collection of sets (or binary vectors). We show that approximate R3way similarity search problems admit fast algorithms with provable guarantees, analo-gous 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 in-dependent theoretical interest. The applicability ofR3way search is shown on the “Google Sets ” application. In addition, we demonstrate the advantage of R3way resemblance over the pairwise case in improving retrieval quality. 1