期刊
2015 IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM)
卷 -, 期 -, 页码 11-20出版社
IEEE
DOI: 10.1109/ICDM.2015.46
关键词
-
Given two sets of vectors, A = {(a(1)) over right arrow, . . . , (a(m)) over right arrow} and B = {(b(1)) over right arrow, . . . ,(b(n)) over right arrow}, our problem is to find the top-t dot products, i.e., the largest vertical bar(a(i)) over right arrow . (b(j)) over right arrow vertical bar 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 ((a(i)) over right arrow . (b(j)) over right arrow)(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-the-art hashing methods.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据