JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation

The inner-product estimation is the base of many important tasks in various big data scenarios, including measuring the similarity of streams in data stream processing, estimating join size in the database, and analyzing cosine similarity in various applications. Sketch, as a class of probabilistic algorithms, is promising in inner-product estimation. However, existing sketch solutions suffer from low accuracy due to neglecting the high skewness of real data. In this paper, we design a new sketch algorithm for accurate and unbiased inner-product estimation, namely JoinSketch. To improve accuracy, JoinSketch consists of multiple components and records items with different frequencies in different components. We theoretically prove that JoinSketch is unbiased and has lower variance than the well-known AGMS and Fast-AGMS sketch. The experimental results show that JoinSketch improves the accuracy of inner-product by 10 times on average while maintaining a comparable throughput.

All code is open-sourced at Github [1].