Diamond Sampling for Approximate Maximum All-Pairs Dot-Product (MAD) Search
Authors:
- Grey BallardGBGrey Ballard
- Tamara G. KoldaTKTamara G. Kolda
- Ali PinarAPAli Pinar
- C. SeshadhriCSC. Seshadhri
- 1 November 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 11-20
Abstract
Given two sets of vectors, A = {a1→, . . . , am→} and B = {b1→, . . . , bn→}, our problem is to find the top-t dot products, i.e., the largest |ai→ · bj→| among all possible pairs. This is a fundamental mathematical problem that appears in numerous data applications involving similarity search, link prediction, and collaborative filtering. We propose a sampling-based approach that avoids direct computation of all mn dot products. We select diamonds (i.e., four-cycles) from the weighted tripartite representation of A and B. The probability of selecting a diamond corresponding to pair (i, j) is proportional to (ai→ · bj→)2, amplifying the focus on the largest-magnitude entries. Experimental results indicate that diamond sampling is orders of magnitude faster than direct computation and requires far fewer samples than any competing approach. We also apply diamond sampling to the special case of maximum inner product search, and get significantly better results than the state-of-theart hashing methods.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Image-Based Recommendations on Styles and Substitutes2015
- LEMP2015
- Path Sampling2015
- Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces2014
- The million song dataset challenge2012
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- Finding associations and computing similarity via biased pair samplingKnowledge and Information Systems, 2011
- Faster join-projects and sparse matrix multiplications2009
- A linear algorithm for generating random numbers with a given distributionIEEE Transactions on Software Engineering, 1991
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted TranspositionACM Transactions on Mathematical Software, 1978