Struct CompactThetaSketch 

pub struct CompactThetaSketch { /* private fields */ }

An immutable, serializable snapshot of a theta sketch. Produced by super::ThetaSketch::compact, by any set operation’s result (ThetaUnion::get_result, ThetaIntersection::get_result, ThetaAnotB::compute), or by Self::deserialize.

Implementations

impl CompactThetaSketch

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

Deserializes v1/v2/v3 (uncompressed) bytes. Upstream’s deserialize() auto-detects the serial version transparently, including v4 (compressed) — see Self::deserialize_compressed, which calls the exact same underlying routine; the two Rust names exist purely for call-site symmetry with serialize_compact/serialize_compressed.

Examples found in repository

examples/bench_theta_update.rs (line 339)

fn bench_serde(items: u64, reps: usize) {
    let mut update_sketch = build();
    for key in 0..items {
        update_sketch.update_u64(key);
    }
    let sketch = update_sketch.compact(true);
    let reference = sketch.serialize_compact();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize_compact()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize =
        || CompactThetaSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/theta.rs (line 73)

fn main() {
    // Build two sketches representing two overlapping sets of user IDs.
    let mut visitors_day1 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );

    // Union: total unique visitors across both days.
    let mut union = ThetaUnionBuilder::new().lg_k(12).build().unwrap();
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result(true);
    println!(
        "Total unique visitors (union estimate): {:.0}",
        total_unique.get_estimate()
    );

    // Intersection: visitors who came back on day 2.
    let mut intersection = ThetaIntersection::new();
    intersection.update(&visitors_day1);
    intersection.update(&visitors_day2);
    match intersection.get_result(true) {
        Ok(returning) => println!(
            "Returning visitors (intersection estimate): {:.0}",
            returning.get_estimate()
        ),
        Err(e) => println!("No intersection result: {e}"),
    }

    // A-not-b: visitors who only came on day 1.
    let a_not_b = ThetaAnotB::new();
    let day1_only = a_not_b.compute(&visitors_day1, &visitors_day2, true);
    println!(
        "Day-1-only visitors (a-not-b estimate): {:.0}",
        day1_only.get_estimate()
    );

    // Jaccard similarity: how similar are the two days' visitor sets?
    let similarity = jaccard_similarity(&visitors_day1, &visitors_day2);
    println!(
        "Jaccard similarity: {:.3} (range [{:.3}, {:.3}])",
        similarity.estimate, similarity.lower_bound, similarity.upper_bound
    );

    // Serialize a compact sketch for storage/transmission, then restore it.
    let compact = visitors_day1.compact(true);
    let bytes = compact.serialize_compact();
    println!("Serialized day-1 sketch: {} bytes", bytes.len());
    let restored = apache_datasketches::theta::CompactThetaSketch::deserialize(&bytes).unwrap();
    println!("Restored estimate: {:.0}", restored.get_estimate());
}

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

Deserializes v4 (compressed) bytes. See Self::deserialize — both methods call the same upstream auto-detecting deserialize().

pub fn get_estimate(&self) -> f64

Returns the current estimate of the number of distinct items in this sketch.

Examples found in repository

examples/bench_theta_update.rs (line 333)

fn bench_serde(items: u64, reps: usize) {
    let mut update_sketch = build();
    for key in 0..items {
        update_sketch.update_u64(key);
    }
    let sketch = update_sketch.compact(true);
    let reference = sketch.serialize_compact();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize_compact()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize =
        || CompactThetaSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

/// Two operands with 50% overlap, built once outside every timed region: the
/// operand-construction cost belongs to the setup, not to the union/
/// intersection/jaccard call being measured.
fn build_operands(items: u64) -> (CompactThetaSketch, CompactThetaSketch) {
    let mut a = build();
    for key in 0..items {
        a.update_u64(key);
    }
    let mut b = build();
    for key in (items / 2)..(items + items / 2) {
        b.update_u64(key);
    }
    (a.compact(true), b.compact(true))
}

/// A fresh union is built inside the timed loop, so the figure is
/// construct + two updates + get_result, not the merge alone -- reusing one
/// accumulator across `OP_CALLS` iterations would have each iteration merge
/// into an ever-growing result, measuring a different workload every time.
fn bench_union(items: u64, reps: usize) {
    let (a, b) = build_operands(items);
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        let mut estimate = 0.0;
        for _ in 0..OP_CALLS {
            let mut union = ThetaUnionBuilder::new()
                .lg_k(LG_K)
                .build()
                .expect("fixed valid parameters were rejected");
            union.update(&a);
            union.update(&b);
            estimate = union.get_result(true).get_estimate();
            total += estimate;
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass { elapsed, estimate });
    }
    report_line("union", items, OP_CALLS, &passes, String::new());
}

/// As [`bench_union`]: a fresh intersection per iteration, so the figure is
/// construct + two updates + get_result.
fn bench_intersect(items: u64, reps: usize) {
    let (a, b) = build_operands(items);
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        let mut estimate = 0.0;
        for _ in 0..OP_CALLS {
            let mut intersection = ThetaIntersection::new();
            intersection.update(&a);
            intersection.update(&b);
            estimate = intersection
                .get_result(true)
                .expect("both operands were non-empty")
                .get_estimate();
            total += estimate;
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass { elapsed, estimate });
    }
    report_line("intersect", items, OP_CALLS, &passes, String::new());
}

examples/theta.rs (line 39)

fn main() {
    // Build two sketches representing two overlapping sets of user IDs.
    let mut visitors_day1 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );

    // Union: total unique visitors across both days.
    let mut union = ThetaUnionBuilder::new().lg_k(12).build().unwrap();
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result(true);
    println!(
        "Total unique visitors (union estimate): {:.0}",
        total_unique.get_estimate()
    );

    // Intersection: visitors who came back on day 2.
    let mut intersection = ThetaIntersection::new();
    intersection.update(&visitors_day1);
    intersection.update(&visitors_day2);
    match intersection.get_result(true) {
        Ok(returning) => println!(
            "Returning visitors (intersection estimate): {:.0}",
            returning.get_estimate()
        ),
        Err(e) => println!("No intersection result: {e}"),
    }

    // A-not-b: visitors who only came on day 1.
    let a_not_b = ThetaAnotB::new();
    let day1_only = a_not_b.compute(&visitors_day1, &visitors_day2, true);
    println!(
        "Day-1-only visitors (a-not-b estimate): {:.0}",
        day1_only.get_estimate()
    );

    // Jaccard similarity: how similar are the two days' visitor sets?
    let similarity = jaccard_similarity(&visitors_day1, &visitors_day2);
    println!(
        "Jaccard similarity: {:.3} (range [{:.3}, {:.3}])",
        similarity.estimate, similarity.lower_bound, similarity.upper_bound
    );

    // Serialize a compact sketch for storage/transmission, then restore it.
    let compact = visitors_day1.compact(true);
    let bytes = compact.serialize_compact();
    println!("Serialized day-1 sketch: {} bytes", bytes.len());
    let restored = apache_datasketches::theta::CompactThetaSketch::deserialize(&bytes).unwrap();
    println!("Restored estimate: {:.0}", restored.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. See ThetaSketch::get_lower_bound for the meaning of num_std_dev.

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 ThetaSketch::get_lower_bound for the meaning of num_std_dev.

pub fn is_empty(&self) -> bool

Returns true if this sketch represents an empty set.

pub fn is_estimation_mode(&self) -> bool

Returns true if this sketch’s theta threshold is below 1.0 (i.e. Self::get_estimate is a statistical estimate rather than an exact count).

pub fn is_ordered(&self) -> bool

Returns true if this sketch’s retained entries are sorted by hash value.

pub fn get_theta(&self) -> f64

Returns the current theta threshold (1.0 if not in estimation mode).

pub fn get_num_retained(&self) -> u32

Returns the number of entries currently retained by this sketch.

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

Serializes in the v3 (uncompressed) format. Note: unlike the design spec’s initially-sketched signature, this takes no ordered parameter — upstream’s compact_theta_sketch::serialize() has none; orderedness is fixed when this sketch was created (e.g. via ThetaSketch::compact(ordered)).

Examples found in repository

examples/bench_theta_update.rs (line 320)

fn bench_serde(items: u64, reps: usize) {
    let mut update_sketch = build();
    for key in 0..items {
        update_sketch.update_u64(key);
    }
    let sketch = update_sketch.compact(true);
    let reference = sketch.serialize_compact();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize_compact()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize =
        || CompactThetaSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/theta.rs (line 71)

fn main() {
    // Build two sketches representing two overlapping sets of user IDs.
    let mut visitors_day1 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = ThetaSketchBuilder::new().lg_k(12).build().unwrap();
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );

    // Union: total unique visitors across both days.
    let mut union = ThetaUnionBuilder::new().lg_k(12).build().unwrap();
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result(true);
    println!(
        "Total unique visitors (union estimate): {:.0}",
        total_unique.get_estimate()
    );

    // Intersection: visitors who came back on day 2.
    let mut intersection = ThetaIntersection::new();
    intersection.update(&visitors_day1);
    intersection.update(&visitors_day2);
    match intersection.get_result(true) {
        Ok(returning) => println!(
            "Returning visitors (intersection estimate): {:.0}",
            returning.get_estimate()
        ),
        Err(e) => println!("No intersection result: {e}"),
    }

    // A-not-b: visitors who only came on day 1.
    let a_not_b = ThetaAnotB::new();
    let day1_only = a_not_b.compute(&visitors_day1, &visitors_day2, true);
    println!(
        "Day-1-only visitors (a-not-b estimate): {:.0}",
        day1_only.get_estimate()
    );

    // Jaccard similarity: how similar are the two days' visitor sets?
    let similarity = jaccard_similarity(&visitors_day1, &visitors_day2);
    println!(
        "Jaccard similarity: {:.3} (range [{:.3}, {:.3}])",
        similarity.estimate, similarity.lower_bound, similarity.upper_bound
    );

    // Serialize a compact sketch for storage/transmission, then restore it.
    let compact = visitors_day1.compact(true);
    let bytes = compact.serialize_compact();
    println!("Serialized day-1 sketch: {} bytes", bytes.len());
    let restored = apache_datasketches::theta::CompactThetaSketch::deserialize(&bytes).unwrap();
    println!("Restored estimate: {:.0}", restored.get_estimate());
}

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

Serializes in the v4 (compressed) format.

Trait Implementations

impl Send for CompactThetaSketch

impl ThetaInput for CompactThetaSketch