Topkapi: Parallel And Fast Sketches For Finding Top-K Frequent Elements

Authors:
Ankush Mandal Georgia Institute of Technology
He Jiang Rice University
ANSHUMALI Shrivastava Rice University
Vivek Sarkar Georgia Institute of Technology

Introduction:

Identifying the top-K frequent items is one of the most common and important operations in large data processing systems.As a result, several solutions have been proposed to solve this problem approximately.

Abstract:

Identifying the top-K frequent items is one of the most common and important operations in large data processing systems. As a result, several solutions have been proposed to solve this problem approximately. In this paper, we identify that in modern distributed settings with both multi-node as well as multi-core parallelism, existing algorithms, although theoretically sound, are suboptimal from the performance perspective. In particular, for identifying top-K frequent items, Count-Min Sketch (CMS) has fantastic update time but lack the important property of reducibility which is needed for exploiting available massive data parallelism. On the other end, popular Frequent algorithm (FA) leads to reducible summaries but the update costs are significant. In this paper, we present Topkapi, a fast and parallel algorithm for finding top-K frequent items, which gives the best of both worlds, i.e., it is reducible as well as efficient update time similar to CMS. Topkapi possesses strong theoretical guarantees and leads to significant performance gains due to increased parallelism, relative to past work.

You may want to know: