Branches

Apache® DataSketches™ Core Rust Library Component

Apache DataSketches Rust provides stochastic streaming algorithms for answering queries over large data sets with compact, mergeable summaries. It is the core Rust component of Apache DataSketches and currently implements a subset of the algorithms available in the other language components.

Getting started

Sketch implementations are opt-in Cargo features; the crate enables none by default. For example, add the HyperLogLog implementation with:

cargo add datasketches --features hll

Then build a sketch and query its distinct-count estimate:

use datasketches::hll::HllSketch;
use datasketches::hll::HllType;

let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
for user in ["alice", "bob", "alice", "carol"] {
    sketch.update(user);
}

assert!(sketch.estimate() >= 3.0);

Enable multiple algorithms by listing their features together, such as features = ["hll", "theta"] in Cargo.toml.

Available sketches

Feature	Main types	Use case
`bloom`	`BloomFilter`	Space-efficient probabilistic set membership with a configurable false-positive rate.
`countmin`	`CountMinSketch`	Approximate point-frequency queries over a stream.
`cpc`	`CpcSketch`, `CpcUnion`, `CpcWrapper`	Highly compact distinct-count estimation and unions.
`frequencies`	`FrequentItemsSketch`	Heavy-hitter discovery with upper and lower frequency bounds.
`hll`	`HllSketch`, `HllUnion`	Fast distinct-count estimation and unions.
`kll`	`KllSketch`	General-purpose quantile, rank, PMF, and CDF queries over totally ordered items.
`req`	`ReqSketch`	Relative-error quantile, rank, PMF, and CDF queries with configurable high- or low-rank accuracy.
`tdigest`	`TDigestMut`, `TDigest`	Quantile and rank estimation, with high accuracy near distribution tails.
`theta`	`ThetaSketch` and set operations	Distinct counts, set expressions, and Jaccard similarity.
`tuple`	`TupleSketch` and set operations	Theta-style keys with user-defined summaries attached to retained entries.
`xor`	`XorFilter`, `XorFilterBuilder`	Immutable probabilistic membership with 8-, 16-, or 32-bit fingerprints.

See the API documentation for configuration, accuracy guarantees, serialization, and examples for each algorithm. Runnable end-to-end scenarios live in datasketches/examples.

Compatibility

The minimum supported Rust version is 1.86.0. The crate currently supports little-endian targets only.

Cross-language serialization tests use Java, C++, and Go fixtures from the DataSketches TCK.

Serialization compatibility does not imply that an ordinary Rust Hash implementation produces the same update bytes across languages. When sketches must represent the same inputs across implementations, use hash::value::{raw_bytes, canonical_float, sign_extend, natural_extend} (and the constructors within those modules) to select matching input encodings. When interoperating with an implementation that skips empty strings, skip them before updating here as well.

See the changelog for release notes and migration guidance.

Other language implementations

Apache DataSketches also provides core library components for other languages:

Visit the Apache DataSketches website for algorithm documentation, research background, and project-wide resources.

Community and contributing

Questions, bug reports, and feature requests are welcome through GitHub issues and GitHub discussions. The Apache DataSketches community page lists the public mailing lists and other ways to participate.

See CONTRIBUTING.md to build, test, and contribute to the Rust component. All project participation is governed by the Apache Software Foundation Code of Conduct.

To report a security vulnerability, follow the ASF security reporting process instead of opening a public issue.

License

Licensed under the Apache License, Version 2.0.

A software library of stochastic streaming algorithms, a.k.a. sketches.