Timezone: »

 
Poster
Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements
Ankush Mandal · He Jiang · Anshumali Shrivastava · Vivek Sarkar

Tue Dec 04 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #140
in Tue Poster Session B »

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.

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

Author Information

Ankush Mandal (Georgia Institute of Technology)
He Jiang (Rice University)
Anshumali Shrivastava (Rice University)
Vivek Sarkar (Georgia Institute of Technology)

More from the Same Authors