Skip to content

A collection of libraries for single-pass, distributed, sublinear-space approximate aggregation and sketching algorithms. Currently: HyperLogLog++; more to come.

License

Notifications You must be signed in to change notification settings

Shifu-Engineer/zetasketch

 
 

Repository files navigation

ZetaSketch

ZetaSketch is a collection of libraries for single-pass, distributed, approximate aggregation and sketching algorithms.

These algorithms estimate statistics that are often too expensive to compute exactly.

The estimates use far fewer memory resources than exact calculations. For example, the HyperLogLog++ algorithm can estimate daily active users with:

ZetaSketch currently includes libraries to implement the following algorithms:

Algorithm Statistics Libraries
HyperLogLog++ Estimates the number of distinct values Java

What is a sketch?

ZetaSketch libraries calculate statistics from sketches. A sketch is a summary of a large data stream. You can extract statistics from a sketch to estimate particular statistics of the original data, or merge sketches to summarize multiple data streams.

After choosing an algorithm, you can use its corresponding libraries to:

  • Create sketches
  • Add new data to existing sketches
  • Merge multiple sketches
  • Extract statistics from sketches

HyperLogLog++

The HyperLogLog++ (HLL++) algorithm estimates the number of distinct values in a data stream. HLL++ is based on HyperLogLog; HLL++ more accurately estimates the number of distinct values in very large and small data streams.

Creating a sketch

// Create a sketch for estimating the number of unique strings in a data stream.
// You can also create sketches for estimating the number of unique byte
// sequences, integers, and longs.

HyperLogLogPlusPlus<String> hll = new HyperLogLogPlusPlus.Builder().buildForStrings();

// You can also set a custom precision. The default normal and sparse precisions
// are 15 and 20, respectively.
HyperLogLogPlusPlus<String> hllCustomPrecision = new HyperLogLogPlusPlus.Builder()
    .normalPrecision(13).sparsePrecision(19).buildForStrings();

Adding new data to a sketch

// Add three strings to the `hll` sketch. You must first initialize an empty
// sketch and then add data to it.
hll.add("apple");
hll.add("orange");
hll.add("banana");

Merging sketches

// Merge `hll2` and `hll3` with `hll`. The sketches must have the same
// original data type and precision.
hll.merge(hll2);
hll.merge(hll3);

Extracting cardinality estimates

// Return the estimate of the number of distinct values.
long result = hll.result();

How to use ZetaSketch

Please find the instructions for your build tool on the right side of https://search.maven.org/artifact/com.google.zetasketch/zetasketch

How to build ZetaSketch

ZetaSketch uses Gradle as its build system. To build the project, simply run:

./gradlew build

License

Apache License 2.0

Contributing

We are not currently accepting contributions to this project. Please feel free to file bugs and feature requests using GitHub's issue tracker.

Disclaimer

This is not an officially supported Google product.

About

A collection of libraries for single-pass, distributed, sublinear-space approximate aggregation and sketching algorithms. Currently: HyperLogLog++; more to come.

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Java 100.0%