Achieving Top-K-fairness for Finding Global Top-$K$ Frequent Items
Yikai Zhao, Wei Zhou, Wenchen Han, Zheng Zhong, Yinda Zhang, Xiuqi Zheng, Tong Yang, Bin Cui · IEEE Transactions on Knowledge and Data Engineering · 2024
Finding top-$K$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-$K$in a single data stream. In this paper, we tackle finding global top-$K$across multiple data streams. We find that using prior sketch algorithms directly is often unfair in global scenarios, degrading global top-$K$accuracy. We define top-$K$-fairness and show its importance for finding global top-$K$. 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-$K$-fairness while maintaining high accuracy. Extensive experiments verify top-$K$-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-$K$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.