MassDAL Public Code Bank : Sketches and Frequent Items

This page is a library of routines in C for data streaming and other massive data set analysis. Currently, these are derived from internal testing routines ("proof of concept" implementations), and so are distributed with no guarantees. In particular, there is relatively little error checking (parameters in range, memory allocation errors) in these implementations. For support and advice, please contact graham a dimacs dot rutgers dot edu

Count-Min Sketch

countmin.h
countmin.c
Count-Min sketches (Cormode, Muthukrishnan '04). They support:

Finding frequent items
Returning point estimates
Approximating Inner-products
Finding quantiles

Combinatorial Group Testing

cgt.h
cgt.c
Described in "What's Hot and What's Not: Tracking Frequent Items Dynamically" They support:

Finding frequent items

CCFC Sketches

ccfc.h
ccfc.c
Count sketches from Charikar, Chen, Farach-Colton '02. They support:

Finding frequent items
Returning point estimates

AMS Sketches

ams.h
ams.c
"Tug of War" sketches due to Alon, Matias and Szegedy 96, and Alon Gibbon Matias and Szegedy, 99. Some hashing tricks used for faster implementation. They support:

Returning point estimates
Approximating Inner-products
Estimating the L2 norm of a vector

Flajolet-Martin Sketches

fm.h
fm.c
Flajolet-Martin sketches for estimating the number of distinct items in a stream. They support finding the number of distinct items (L0 norm).

Stable Distributions and sketches

stable.h
stable.c
Sketches based on stable distributions. Based on Indyk'00, Cormode, Indyk, Koudas, Muthukrishnan '02, Cormode, Data, Indyk, Muthukrishnan, '02. They support

Estimating the L2 norm of a vector
Estimating the L1 norm of a vector
Estimating the L0 norm of a vector
Estimating arbitrary Lp norms for 0 < p < 2

Library Routines

These are some general routines which are made use of by various of the other code available here.

Random number generators	prng.h prng.c
Timing Routines	timer.h timer.c

Frequent Item Algorithms

These are routines for finding frequent items in data streams. They are derived from code used in the paper "What's Hot and What's Not: Tracking Frequent Items Dynamically"

Method	Files	Description
Frequent	frequent.h frequent.c	Algorithm Frequent for insert only streams
LossyCounting	lossycount.h lossycount.c	Lossy Counting algorithm due to Manku and Motwani

Usage

Each of the .h files exports various methods:

Init -- Initialize the data structure. Takes some parameters defining the accuracy and quality of the results. Returns a pointer to an object which must be supplied to the following routines.
Update -- Takes an item identifier. Some routines take an additional parameter of the count to add on for this arrival (positive or negative increment). Others interpret a positive count as an arrival, a negative count as a departure.
Output -- Takes an integer threshold, returns a list of items which should exceed this threshold.
Size -- Returns the space used by the data structure
Destroy -- Destroys the data structure and frees the associated memory.

Sample Usage

hotitems.c Example usage of the above routines, finding frequent items on a stream drawn from zipf distributions.
teststab.c Example usage of the above routines to estimate the L1, L2, and L0 norms of data streams.
makefile A makefile for the above code

Code Bundle

massdalsketches.zip All the above .c and .h files together in one easy to download .zip file.

The following licence applies to all code distributed here.

This work is licensed under a Creative Commons License.