Abstract

 Identifying the top-K frequent items in a collection or data stream 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. We observe that the existing algorithms, although theoretically sound, are suboptimal from the performance perspective because of their limitations in exploiting parallelism in modern distributed compute settings. In particular, for identifying top-K frequent items, Count-Min Sketch (CMS) has an excellent update time, but lacks the important property of reducibility which is needed for exploiting available massive data parallelism. On the other end, the popular Frequent algorithm (FA) leads to reducible summaries but its 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 and has fast update time similar to CMS. Topkapi possesses strong theoretical guarantees and leads to significant performance gains due to increased parallelism, relative to past work.