Sketches for Size of Join Estimation

• Schemes for generating pseudo-random numbers

  +/-1 random variables and b-valued hashes are at the core of all the sketching techniques. The package contains efficient implementations of the generating schemes based on BCH codes, Reed-Muller codes, and Carter-Wegman hashes. Implementations for fast range-summation and dyadic mappings of the +/-1 random variables are also provided.
  For details see the papers:
  1. Fast Range-Summable Random Variables for Efficient Aggregate Estimation by F. Rusu and A. Dobra
  2. Pseudo-Random Number Generation for Sketch-Based Estimations by F. Rusu and A. Dobra
  Files:
  • gen_scheme.h
  • range_sum.h
  • RM7_range_sum.h
  • xis.h
  • xis.cpp

• Sketches for size of join estimation

  The package contains the implementation of the known sketches for size of join and second frequency moment estimation. It includes the original AGMS sketches and the improved versions Fast-AGMS sketches, Fast-Count sketches, and Count-Min sketches.
  For details consult the papers:
  1. Statistical Analysis of Sketch Estimators by F. Rusu and A. Dobra
  2. Sketches for Size of Join Estimation by F. Rusu and A. Dobra
  Files:
  • sketches.h
  • sketches.cpp

• Sketches over sampled data

  The update performance of sketches can be significantly improved if only a sample of the data is sketched, without significant degradation in the accuracy. Simple sampling algorithms like Bernoulli sampling, sampling without replacement, and sampling with replacement, are also included in the package.
  For details see the paper:
  1. Sketching Sampled Data Streams by F. Rusu and A. Dobra
  Files:
  • sampling.h
  • sampling.cpp

• Synthetic data generator

  The package contains a simple data generator for different distributions with customizable parameters. This allows the testing of the implemented algorithms.
  Files:
  • data_generator.h
  • relation.h
  • relation.cpp

• Examples

  Two usage examples are included in the package. The first example generates size of join estimations with all the implemented sketching techniques. The second example is for sketching Bernoulli samples.
  Files:
  • sketch_compare.cpp
  • sketch_sampling.cpp

Requirements

Download