Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
复制标题
DOI：
10.1145/3584372.3588679
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Aline Bessa;Majid Daliri;Juliana Freire;Cameron Musco;Christopher Musco;Aécio S. R. Santos;H. Zhang
中科院分区：
文献类型：
--
作者：
Aline Bessa;Majid Daliri;Juliana Freire;Cameron Musco;Christopher Musco;Aécio S. R. Santos;H. Zhang
我们提出了一种独立计算紧凑草图的新方法，该方法可用于近似高维向量对之间的内积。基于加权MinHash算法，我们的方法具有很强的准确性保证，提高了流行的线性草图方法对内积估计的保证，如countssketch和Johnson-Lindenstrauss投影。具体来说，虽然我们的方法完全匹配密集向量的线性草图，但对于非零条目之间有限重叠的稀疏向量，它产生的误差要低得多。这样的向量出现在许多涉及稀疏数据的应用程序中，以及日益流行的数据集搜索应用程序中，其中内积用于估计数据协方差、条件均值和其他涉及未连接表中的列的数量。我们通过证明我们的方法在经验上优于现有的稀疏向量线性草图和基于未加权哈希的草图来补充我们的理论结果。
We present a new approach for independently computing compact sketches that can be used to approximate the inner product between pairs of high-dimensional vectors. Based on the Weighted MinHash algorithm, our approach admits strong accuracy guarantees that improve on the guarantees of popular linear sketching approaches for inner product estimation, such as CountSketch and Johnson-Lindenstrauss projection. Specifically, while our method exactly matches linear sketching for dense vectors, it yields significantly lower error for sparse vectors with limited overlap between non-zero entries. Such vectors arise in many applications involving sparse data, as well as in increasingly popular dataset search applications, where inner products are used to estimate data covariance, conditional means, and other quantities involving columns in unjoined tables. We complement our theoretical results by showing that our approach empirically outperforms existing linear sketches and unweighted hashing-based sketches for sparse vectors.