Key Features
Common Sketch Properties
- Please refer to the Sketch Criteria for the criteria for sketches to be included in the library.
- Query results are approximate but within well defined error bounds that are user
configurable by trading off sketch size with accuracy.
- Designed for Large-scale computing environments
that must handle Big Data, e.g.:
- The Java-based sketches are registered with the Maven Central Repository. For example: DataSketches-Java.
- Extensive documentation with the systems developer in mind.
- Designed for production environments:
- Available in multiple languages: Java, C++, Python, and Go.
- Binary compatible across systems and languages. For example, a sketch can be built and loaded in a C++ platform, then serialized and transported to a Java platform where it can be merged with other sketches and queried.
Built-In, General Purpose Functions
- General purpose Memory Component for managing data off the Java Heap.
This enables systems designers the ability to manage their own large data heaps with
dedicated processor threads that would otherwise put undue pressure on the Java heap and
its garbage collection. Starting with Java Version 9.0.0, this functionality is now native to the Java 25 language.
- General purpose implementaion of Austin Appleby’s 128-bit MurmurHash3 algorithm,
with a number of useful extensions.
Robust, High Quality Implementations.
- Unit Tests:
- Extensive test code leveraging TestNG.
- High Test Code coverage (> 90%) as measured by [JaCoCo]https://www.eclemma.org/jacoco) and published by
Coveralls.
- Reproducible Characterization Studies
- All our published speed and accuracy performance results can be reproduced using the code included in the
Characterization repository.
- Comprehensive Javadocs.
Opportunities to Extend
- There is ample opportunity for interested parties to contribute additional algorithms in this exciting area.
Key Algorithms
Count Distinct / Count Unique
Solves Computational Challenges Associated with Unique Identifiers
- Estimating cardinality of a stream with many duplicates
- Performing Set Operations (e.g., Union, Intersection,
and Difference) on sets of unique identifiers
- Estimates of the error bounds of the result can be obtained directly from the result sketch
Four families of Count Unique algorithms:
- The HLL Sketch. The famous HyperLogLog algorithm when stored sketch size is of utmost concern.
- The CPC Sketch. The Compressed Probabilistic Counting algorithm when maximizing accuracy per stored sketch size is of utmost concern.
- The Theta Sketch Framework. Theta sketches enable real-time set-expression computations and can operate on or off the java heap.
- The Tuple Sketch. Tuple sketches are associative sketches that are useful for performing approximate join operations and extracting other kinds of statistical behavior associated with unique identifiers.
Quantiles
Get normal or inverse PDFs or CDFs of the distributions of any numeric value from your raw data in a single pass with well defined error bounds on the results.
Frequency
Sampling
Filters and Set Membership
