Skip to content

Instantly share code, notes, and snippets.

@apg
Forked from debasishg/gist:8172796
Created October 17, 2015 17:34
Show Gist options
  • Save apg/efe6833eb74ac264b68b to your computer and use it in GitHub Desktop.
Save apg/efe6833eb74ac264b68b to your computer and use it in GitHub Desktop.
A collection of links for streaming algorithms and data structures
  1. General Background and Overview
  1. Hyperloglog and MinHash : Implementation of a form of hyperloglog and adding capabilities of MinHash algorithm on to it which would enable to perform set intersections."While it does require extra processing power to deal with collecting all the minima, it’s possible to get satisfactory performance out of the structure for a relatively low storage or memory footprint"

  2. Streaming/Sketching Conference from AK Tech : Contains links to videos and slides from the speakers like Muthukrishnan who spoke about Count Min Sketch

  3. Q-digest

  1. t-digest : A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means. Ted Dunning's variant of Q-digest that does some improvements

  2. Implementations

  1. Count-Min Sketch
  1. Surveys
  • References for Data Stream Algorithms by Graham Cormode : an exhaustive set of references with explanations
  • Data Streams - Algorithms and Applications by S. Muthukrishnan : This is an excellent monograph with surveys of all algorithms related to data streams. Also a free copy of the book is available from Muthu's web site at http://www.cs.rutgers.edu/~muthu/
  • Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches by Graham Cormode1, Minos Garofalakis, Peter J. Haas and Chris Jermaine . Describes basic principles and recent developments in approximate query processing. It focuses on four key synopses: random samples, histograms, wavelets, and sketches. It considers issues such as accuracy, space and time efficiency, optimality, practicality, range of applicability, error bounds on query answers, and incremental maintenance. It also discusses the trade-offs between the different synopsis types.
  1. Distributed Streams Algorithms for Sliding Windows by Phillip B. Gibbons and Srikanta Tirthapura

  2. Frugal Streaming

  3. A Framework for Clustering Massive-Domain Data Streams by Charu C. Aggarwal

  4. A framework for clustering evolving data streams by Charu C. Aggarwal et. al.

  5. Unsupervised Feature Selection on Data Streams by Hao Huang

  6. Presentations

  1. Courses
  1. Incremental Learning with Decision Trees for Streamed Data
  1. Clustering Data Streams
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment