Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements
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.
This paper presents topkapi, an new algorithm that estimates the most frequent elements in a set in a distributed fashion.  This paper presents some positive developments on an important topic for big data and would be a good candidate for publication at this conference. However, this reviewer feels that the paper could be significantly strengthened before publication.  - structure: the current paper goes at length to describe a hybrid between CMS and FA, but it casually turns around in section 3.3 to essentially dismiss the sketch part of the algorithm. The reviewer would suggest to focus earlier on presenting the algorithm as FA with sketch-flavored hashing.  - proofs: this reviewer is of the opinion that formal guarantees are important for such algorithms and should be made explicit to practitioners. Unfortunately, all the theorems are relegated to the appendix. At least presenting the main results in the paper would reinforce the paper, as it currently is presented more as a discussion without obvious formal backing.  - presentation: CMS computes counts of elements, while FA focuses on the identification of the most frequent elements. The paper puts them on equal footing, which led this reviewer to wonder if identifying or computing the frequencies of the top-k elements was the eventual goal of the paper. In particular, presenting CMS as not good for reducibility seems to distract the flow, as pure sketches (without tracking the top elements in a heap) are excellent for distribution and reducibility.  Some other comments: - Both 'Frequent' and 'FA' are used, which is a bit confusing. The authors should pick one notation. - The reviewer wonders how the guarantees would be strengthened if, for each of the CMS bins in the sketch, 2 or 3 FA counts would be kept instead of just one. The update would still be trivial with 2 comparisons, but it could lead to more robust estimates, at least in theory. - In practice, it is useful to also have access to the frequencies of the most frequent elements (which is provided by sketches). How would the authors plan to address this point? - Regarding the experiments, the reviewer would be curious to see how pure CMS fares (with a first sketch building pass followed by a heavy hitter hash-based identification pass). This would be more fair and also simpler than a heap augmentation of CMS.  Overall, the reviewer would welcome this contribution, provided the points above are addressed.  UPDATE: The reviewer thanks the authors for their comments. - regarding the 2-pass CMS + Top-K, this is a 'natural' approach for batch or memory-constrained settings (and of course prohibitive for streams, but the context of the paper is more general than streaming). Given the good performance of topkapi, I would recommend this is included in the final submission, especially as it explicitly now compares against spark, and spark has both built-in CMS and top-k. - regarding bounds on results, the authors rightfully mentioned that CMS and FA provide upper and lower bounds on the exact value. I believe this is worth mentioning as this is important information in practice - the updated version of the paper mentions spark prominently in the abstract as a point of comparison, but the reviewer sees no experiment against it (although the results would be expected to be quite in favor of topkapi). This should be addressed in the final version, either by removing mention of spark or at least mentioning some experiments. These are fairly minor points though, and this reviewer would welcome this contribution provided the points above are addressed in the final revision.