Struct HllSketch 

pub struct HllSketch { /* private fields */ }

A HyperLogLog sketch: estimates the number of distinct items added via update_*, using bounded memory regardless of how many items are added.

lg_config_k (passed to HllSketch::new, valid range 4..=21) trades memory for accuracy: higher values are more accurate but use more space.

Implementations

impl HllSketch

pub fn new( lg_config_k: u8, tgt_type: TargetHllType, ) -> Result<Self, SketchError>

Creates a new, empty sketch with the given lg_config_k (4..=21) and internal representation. Returns SketchError::InvalidConfig if lg_config_k is out of range.

Examples found in repository

examples/hll.rs (line 12)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn copy_as(&self, tgt_type: TargetHllType) -> Self

Returns a copy of this sketch converted to a different TargetHllType, preserving its current state.

pub fn deserialize(bytes: &[u8]) -> Result<Self, SketchError>

Reconstructs a sketch from bytes produced by Self::serialize_compact or Self::serialize_updatable.

Examples found in repository

examples/hll.rs (line 34)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn update_u64(&mut self, value: u64)

Adds a u64 value to the sketch.

Examples found in repository

examples/hll.rs (line 15)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn update_i64(&mut self, value: i64)

Adds an i64 value to the sketch.

pub fn update_f64(&mut self, value: f64)

Adds an f64 value to the sketch.

pub fn update_str(&mut self, value: &str)

Adds a string value to the sketch.

Examples found in repository

examples/hll.rs (line 21)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn update_bytes(&mut self, value: &[u8])

Adds an arbitrary byte slice to the sketch.

Examples found in repository

examples/hll.rs (line 22)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn get_estimate(&self) -> f64

Returns the current estimate of the number of distinct items added.

Examples found in repository

examples/hll.rs (line 24)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn get_lower_bound(&self, num_std_dev: u8) -> Result<f64, SketchError>

Returns the lower bound of the confidence interval around Self::get_estimate, for the given number of standard deviations (1, 2, or 3, corresponding to roughly 67%, 95%, and 99% confidence). Returns SketchError::InvalidConfig for any other value.

Examples found in repository

examples/hll.rs (line 27)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn get_upper_bound(&self, num_std_dev: u8) -> Result<f64, SketchError>

Returns the upper bound of the confidence interval around Self::get_estimate. See Self::get_lower_bound for the meaning of num_std_dev.

Examples found in repository

examples/hll.rs (line 28)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn get_lg_config_k(&self) -> u8

Returns the lg_config_k this sketch was built with.

pub fn get_target_type(&self) -> TargetHllType

Returns the TargetHllType this sketch currently uses.

pub fn is_empty(&self) -> bool

Returns true if no items have been added to this sketch.

pub fn reset(&mut self)

Resets this sketch to its initial, empty state.

pub fn to_string_summary(&self) -> String

Returns a human-readable, multi-line summary of this sketch’s internal state — useful for debugging, not for parsing.

pub fn serialize_compact(&self) -> Vec<u8>

Serializes this sketch in compact form (read-only once deserialized): smaller on the wire, but a Self::deserialized sketch produced from these bytes cannot be updated further. Use Self::serialize_updatable if you need to resume adding items after deserializing.

Examples found in repository

examples/hll.rs (line 33)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_config_k` (4..=21)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut sketch = HllSketch::new(12, TargetHllType::Hll4).expect("valid lg_config_k");

    for i in 0..10_000u64 {
        sketch.update_u64(i);
    }
    // Duplicates don't affect the distinct count.
    for i in 0..5_000u64 {
        sketch.update_u64(i);
    }
    sketch.update_str("some-key");
    sketch.update_bytes(b"raw bytes work too");

    println!("distinct count estimate: {:.1}", sketch.get_estimate());
    println!(
        "95% confidence interval: [{:.1}, {:.1}]",
        sketch.get_lower_bound(2).unwrap(),
        sketch.get_upper_bound(2).unwrap()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later.
    let bytes = sketch.serialize_compact();
    let restored = HllSketch::deserialize(&bytes).expect("valid sketch bytes");
    assert_eq!(sketch.get_estimate(), restored.get_estimate());
    println!(
        "serialized to {} bytes and restored successfully",
        bytes.len()
    );

    // HllUnion merges multiple sketches into one, e.g. combining
    // per-shard/per-day counts into a total distinct count.
    let mut shard_a = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 0..10_000u64 {
        shard_a.update_u64(i);
    }
    let mut shard_b = HllSketch::new(12, TargetHllType::Hll4).unwrap();
    for i in 5_000..15_000u64 {
        shard_b.update_u64(i);
    }

    let mut union = HllUnion::new(12).expect("valid lg_max_k");
    union.update_sketch(&shard_a);
    union.update_sketch(&shard_b);

    let merged = union.get_result(TargetHllType::Hll4);
    println!(
        "merged distinct count across two overlapping shards (true count = 15000): {:.1}",
        merged.get_estimate()
    );
}

pub fn serialize_updatable(&self) -> Vec<u8>

Serializes this sketch in updatable form: larger on the wire than Self::serialize_compact, but a deserialized sketch can have more items added to it.

Trait Implementations

impl Send for HllSketch