Achieving Top-K-fairness for Finding Global Top-$K$ Frequent Items

Finding top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> frequent items has been a hot topic in data stream processing with wide-ranging applications. However, most existing sketch algorithms focus on finding local top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> in a single data stream. In this paper, we tackle finding global top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> across multiple data streams. We find that using prior sketch algorithms directly is often unfair in global scenarios, degrading global top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> accuracy. We define top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>-fairness and show its importance for finding global top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>. To achieve this, we propose the Double-Anonymous (DA) sketch, where double-anonymity ensures fairness. We also propose two techniques, hot-filtering and early-freezing, to improve accuracy further. We theoretically prove that the DA sketch achieves top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>-fairness while maintaining high accuracy. Extensive experiments verify top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>-fairness in disjoint data streams, showing that the DA sketch's error is up to 129 times (60 times on average) smaller than the state-of-the-art. To enhance the applicability and technical depth, we also investigate how to extend the DA sketch to general distributed data stream scenarios and how to provide a fairer and more accurate global ranking for top-<inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> items. The experimental results show that the extended version of the DA sketch can indeed compute better rankings and still has significant advantages in general data streams.