API Snapshots: Core, Memory, Pig, Hive, Misc

Table of Contents

Selected References on Frequent Items Sketches

  • Daniel Anderson, Pryce Bevan, Kevin Lang, Edo Liberty, Lee Rhodes, Justin Thaler. A High-Performance Algorithm for Identifying Frequent Items in Data Streams. https://arxiv.org/abs/1705.07001
  • Misra, J., Gries, D. Finding repeated elements. Sci. Comput. Programming 2 (1982), 143–152
  • Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137–147, 1999.
  • Finding Frequent Items in Data Streams Moses Charikar, Kevin Chen, Martin Farach-Colton
  • Phillip Gibbons and Yossi Matias. New sampling-based summary statistics for improving approximate query answers. In Proc. ACM SIGMOD International Conference on Management of Data, pages 331–342, 1998
  • Finding the Frequent Items in Streams of Data. Graham Cormode and Marios Hadjieleftheriou
  • Cormode, G., Muthukrishnan, S. An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55, 1 (2005), 58–75
  • Demaine, E., López-Ortiz, A., Munro, J.I Frequency estimation of internet packet streams with limited space. In European Symposium on Algorithms (ESA) (2002).
  • Karp, R., Papadimitriou, C., Shenker, S. A simple algorithm for finding frequent elements in sets and bags. ACM Trans. Database Syst. 28 (2003), 51–55
  • Metwally, A., Agrawal, D., Abbadi, A.E. Efficient computation of frequent and top-k elements in data streams. In International Conference on Database Theory (2005)