%0 Conference Paper %1 ShrivastavaLi2013a %A Shrivastava, Anshumali %A Li, Ping %B Advances in Neural Information Processing Systems 26 %D 2013 %E Burges, C.J.C. %E Bottou, L. %E Welling, M. %E Ghahramani, Z. %E Weinberger, K.Q. %I Curran Associates, Inc. %K imported %P 791--799 %T Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search %U http://papers.nips.cc/paper/5216-beyond-pairwise-provably-fast-algorithms-for-approximate-k-way-similarity-search/ %X 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: R^3way= |S_1 S_2 S_3||S_1 S_2 S_3|, S_1, S_2, S_3 C, 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."

@inproceedings{ShrivastavaLi2013a, abstract = {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 \emph{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 \emph{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."}, added-at = {2015-01-19T16:50:57.000+0100}, author = {Shrivastava, Anshumali and Li, Ping}, biburl = {https://www.bibsonomy.org/bibtex/269f083cf7bbd4cbbbf0e7be0c179fa0e/ncrn-cornell}, booktitle = {Advances in Neural Information Processing Systems 26}, editor = {Burges, C.J.C. and Bottou, L. and Welling, M. and Ghahramani, Z. and Weinberger, K.Q.}, file = {5216-beyond-pairwise-provably-fast-algorithms-for-approximate-k-way-similarity-search.pdf:http\://papers.nips.cc/paper/5216-beyond-pairwise-provably-fast-algorithms-for-approximate-k-way-similarity-search.pdf:PDF}, interhash = {1bd95d1bab5f154b8f42d5a6851c40e1}, intrahash = {69f083cf7bbd4cbbbf0e7be0c179fa0e}, keywords = {imported}, owner = {vilhuber}, pages = {791--799}, publisher = {Curran Associates, Inc.}, timestamp = {2015-01-19T16:50:57.000+0100}, title = {Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search}, url = {http://papers.nips.cc/paper/5216-beyond-pairwise-provably-fast-algorithms-for-approximate-k-way-similarity-search/}, year = 2013 }