Weighted Minwise Hashing Beats Linear Sketching For Inner Product Estimation

Abstract

We present a new approach for 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 admits guarantees that exactly match 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. They are also important in increasingly popular dataset search applications, where inner product sketches 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 sketch

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keybessa2023weighted

Related papers

• A Memory-efficient Sketch Method For Estimating High Similarities In Streaming Sets (2019)12.02
• Analysis Of Sparsehash: An Efficient Embedding Of Set-similarity Via Sparse Projections (2019)4.52
• Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations (2019)4.52
• Sketchmate: Deep Hashing For Million-scale Human Sketch Retrieval (2018)15.03
• Making Online Sketching Hashing Even Faster (2020)9.23
• Fast Similarity Sketching (2017)9.41
• Superminhash - A New Minwise Hashing Algorithm For Jaccard Similarity Estimation (2017)0.00
• Streaming Binary Sketching Based On Subspace Tracking And Diagonal Uniformization (2017)0.00