| Popis: |
Finding heavy hitters in databases and data streams is a fundamental problem, with applications ranging from network monitoring to database query optimization, anomaly detection, and more. Approximation algorithms offer practical solutions, but they present multi-faceted trade-offs involving throughput, memory usage, and accuracy. Moreover, evolving applications demand capabilities beyond sequential processing - they require both parallel performance scaling and support for concurrent queries/updates. To address these challenges holistically, we first propose a new algorithm, Cuckoo Heavy Keeper, that combines careful algorithmic design with system-aware perspectives, to effectively balance competing trade-offs. Recognizing the diverse needs of different applications, we then propose two parallel algorithms optimized for different workload patterns: one prioritizes insertion throughput while the other targets efficient heavy hitter queries, both achieving high performance via efficient parallel scaling while supporting concurrent operations. Besides discussing the algorithms' bounds, through extensive evaluation, we demonstrate that Cuckoo Heavy Keeper improves throughput by 1.7X to 5.6X and accuracy by 1.9X to 27,542X compared to state-of-the-art methods under tight memory constraints, maintaining these advantages even with low-skew datasets. The parallel variants achieve near-linear scaling up to 70 threads while maintaining heavy hitters query latencies as low as 36 {\mu}sec to 350 {\mu}sec. |
