Struct SpaceSaving 

pub struct SpaceSaving<T: Hash + Eq + Clone + Debug> { /* private fields */ }

Available on crate features frequency and std only.

Space-Saving algorithm for finding frequent items

The Space-Saving algorithm maintains a summary of the k most frequent items with the following guarantees:

• Any item with true frequency > n/k is guaranteed to be in the summary
• The maximum overcount error for any item is at most n/k

Example

use flowstats::frequency::SpaceSaving;
use flowstats::traits::HeavyHitters;

let mut ss = SpaceSaving::new(10); // Track top 10

// Add some items
for _ in 0..100 { ss.add("apple"); }
for _ in 0..50 { ss.add("banana"); }
for _ in 0..25 { ss.add("cherry"); }
for _ in 0..10 { ss.add("date"); }

// Get top 3 items
let top = ss.top_k(3);
println!("Top items: {:?}", top);

Implementations

impl<T: Hash + Eq + Clone + Debug> SpaceSaving<T>

pub fn new(capacity: usize) -> Self

Create a new Space-Saving structure with the given capacity

Arguments

• capacity - Maximum number of items to track (k)

pub fn capacity(&self) -> usize

Get the capacity (k)

pub fn num_tracked(&self) -> usize

Get the number of distinct items currently tracked

pub fn total_count(&self) -> u64

Get the total count

pub fn add(&mut self, item: T)

Add an item to the structure

pub fn add_count(&mut self, item: T, count: u64)

Add an item with a specific count

pub fn estimate(&self, item: &T) -> u64

Estimate the frequency of an item

pub fn error(&self, item: &T) -> u64

Get the error bound for an item’s estimate

pub fn guaranteed_count(&self, item: &T) -> u64

Get guaranteed minimum count for an item

Returns (count - error), which is guaranteed to be at most the true count.

pub fn contains(&self, item: &T) -> bool

Check if an item is currently tracked

Trait Implementations

impl<T: Clone + Hash + Eq + Clone + Debug> Clone for SpaceSaving<T>

fn clone(&self) -> SpaceSaving<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Hash + Eq + Clone + Debug> Debug for SpaceSaving<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Hash + Eq + Clone + Debug> FrequencySketch for SpaceSaving<T>

fn estimate_frequency(&self, item: &T) -> u64

Estimate frequency of an item

fn exceeds_threshold(&self, item: &Self::Item, threshold: u64) -> bool

Check if frequency exceeds threshold

impl<T: Hash + Eq + Clone + Debug> HeavyHitters for SpaceSaving<T>

fn heavy_hitters(&self, threshold: f64) -> Vec<(T, u64)>

Get items with estimated frequency above threshold

fn top_k(&self, k: usize) -> Vec<(T, u64)>

Get top-k most frequent items

impl<T: Hash + Eq + Clone + Debug + Serialize> Serialize for SpaceSaving<T>

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<T: Hash + Eq + Clone + Debug> Sketch for SpaceSaving<T>

type Item = T

The type of item this sketch processes

fn update(&mut self, item: &T)

Add an item to the sketch

fn merge(&mut self, _other: &Self) -> Result<(), MergeError>

Merge another sketch into this one

fn clear(&mut self)

Reset sketch to empty state

fn size_bytes(&self) -> usize

Memory usage in bytes

fn count(&self) -> u64

Number of items processed

fn is_empty(&self) -> bool

Check if sketch is empty