Communications of the ACM
Research Archive
The Research archive provides access to all Research articles published in past issues of Communications of the ACM.
August 2019
From Communications of the ACM
Heavy Hitters via Cluster-Preserving Clustering
We develop a new algorithm for the turnstile heavy hitters problem in general turnstile streams, the EXPANDERSKETCH, which finds the approximate top-k items in a universe of size n using the same asymptotic O(k log n) words of…
From Communications of the ACM
Technical Perspective: The True Cost of Popularity
The main focus of "Heavy Hitters via Cluster-Preserving Clustering" by Kasper Green Larsen et al. is on building up sufficient information to allow a more effective search process.