Streaming Algorithms
1. Overview
1.1. Count-min Sketch
The Count-min sketch calculates the frequency of an item in a stream.
1.2. Matrix
Matrix data structure for a 2d matrix.
1.3. Piecewise Parabolic Prediction (P2)
The p2 algorithm for dynamic calculation of quantiles and histograms without storing observation.
1.4. Running Stats
Calculates the mean, variance, and standard deviation https://www.johndcook.com/blog/standard_deviation/
1.5. Time Series
Time series data structure for windowed calculations.
2. Installation
2.1. Prerequisites
- C compiler (GCC 4.7+, Visual Studio 2013)
- CMake (3.6+) - http://cmake.org/cmake/resources/software.html
- Git http://git-scm.com/download
2.1.1. Optional (used for documentation)
- Graphviz (2.28.0) - http://graphviz.org/Download.php
- Doxygen (1.8.11+)- http://www.stack.nl/~dimitri/doxygen/download.html#latestsrc
- gitbook (2.3) - https://www.gitbook.com/
2.2. CMake Build Instructions
git clone https://github.com/trink/streaming_algorithms.git
cd streaming_algorithms
mkdir release
cd release
# UNIX
cmake -DCMAKE_BUILD_TYPE=Release -DCPACK_GENERATOR=[TGZ|RPM|DEB] ..
make
# Windows Visual Studio 2013
cmake -DCMAKE_BUILD_TYPE=Release -G "NMake Makefiles" ..
nmake
ctest