2025/05/25 by Nima Shahbazi, Shahbazi, Nima, Stavros Sintos +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2505.18919
openalex publication_date 2025/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Frequency estimation in streaming data often relies on sketches like Count-Min (CM) to provide approximate answers with sublinear space. However, CM sketches introduce additive errors that disproportionately impact low-frequency elements, creating fairness concerns across different groups of elements. We introduce Fair-Count-Min, a frequency estimation sketch that guarantees equal expected approximation factors across element groups, thus addressing the unfairness issue. We propose a column partitioning approach with group-aware semi-uniform hashing to eliminate collisions between elements from different groups. We provide theoretical guarantees for fairness, analyze the price of fairness, and validate our theoretical findings through extensive experiments on real-world and synthetic datasets. Our experimental results show that Fair-Count-Min achieves fairness with minimal additional error and maintains competitive efficiency compared to standard CM sketches.