Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search
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:
where C is a size n collection of sets (or binary vectors). We show that approximate 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 R 3way search is shown on the "Google Sets" application. In addition, we demonstrate the advantage of R 3way resemblance over the pairwise case in improving retrieval quality.
This paper describes a nice trick to extend MinHash to 
      estimate the generalization of the Jaccard index to more than two sets. 
      Using the trick, the paper presents efficient search algorithms for (1) 
      given S and T, indentifying U for which (S,T,U) are similar, (2) given S, 
      identifying T and U for which (S,T,U) are similar, and (3) identifying S, 
      T and I for which (S,T,U) are similar. There are experiments showing the 
      value of a >2-way similaruty measure. This paper is not written 
      well and is consequently difficult to read. As far as I know, the 
      work is original. The algorithms are significant and may prove to be 
      useful in many domains. If this paper is edited to remove all of the 
      grammar errors, it will be very nice. The anecdotes for the 
      "Google Sets" problem are very cool. I found the search-quality 
      experiments very hard to follow. It would be help a lot if the metric 
      discussion is promoted to come earlier in the section and discussed in a 
      little more depth. Example presentation issues (restricting to one 
      per page) Page 1: "one of the most widely used notion" => 
      "notions" Page 2: "may be" => "maybe" Page 3: "any two point" 
      => "any two points" Page 4: "One of the peculiarity" => 
      "peculiarities" Page 5: "c-BP" in the Section 5 title should be "c-CP" 
      Page 6: "if we are interested in very high similarity cluster" => 
      "a very" or "clusters" Page 7: "report top 5 words" => "report the 
      top 5 words" Page 8: "We formulated ... and obtain" => "formulate" 
      or "obtained"