Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search
A. Shrivastava, and P. Li. Advances in Neural Information Processing Systems 26, page 791--799. Curran Associates, Inc., (2013)
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 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."
%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
}