Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search

Grey Ballard, Ali Pinar, Tamara G. Kolda +1

Given two sets of vectors, $A=\{a_1,\dots ,a_m\}$ and $B=\{b_1,\dots ,b_n\}$, our problem is to find the top-$t$ dot products, i.e., the largest $|a_i\cdot b_j|$ among…