Skip to yearly menu bar Skip to main content


Poster

Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements

Ankush Mandal · He Jiang · Anshumali Shrivastava · Vivek Sarkar

Room 517 AB #140

Keywords: [ Software Toolkits ] [ Web Applications and Internet Data ] [ Benchmarks ]


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.

Live content is unavailable. Log in and register to view live content