Sketches for Inner Product Estimation (Coming soon)

This repository provides implementations of sketching algorithms for inner product estimation used in the paper "Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation", which introduces an approach for inner product estimation using minwise hashing sketches. The code is meant for research and has not been optimized in any way.

Note: The code has not been released yet. It will be available soon.

Sketches

• WMH (Weighted MinHash)
• MH (MinHash)
• KMV (k-Minimum Values)
• JL (Johnson-Lidenstrauss projections)
• CS (CountSketch)

Papers

• Aline Besa, Majid Daliri, Juliana Freire, Cameron Musco, Christopher Musco, Aécio Santos, and Haoxiang Zhang. "Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation." Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, (2023). arXiv preprint arXiv:2301.05811

Please take a look at the paper for a detailed explanation of the underlying algorithms and techniques used in the library.