moon-frequency-sketch

MoonBit 高吞吐频率与重频项估计库

A production-quality streaming frequency estimation library for MoonBit, implementing a comprehensive suite of probabilistic data structures for counting, top-K detection, membership testing, and time-windowed analysis.

Features

Structure	Description	Guarantee
Count-Min Sketch	Core frequency estimator	ε-approximate, never under-counts
Count Sketch	Unbiased frequency estimator	Error ∝ L2 norm of stream
Space-Saving	Top-K heavy hitter tracker	Detects all items with freq > N/k
Misra-Gries	Frequent items algorithm	Detects all items with freq > N/(k+1)
Bloom Filter	Probabilistic membership test	No false negatives, tunable FP rate
Counting Bloom Filter	Membership with deletion support	Same as Bloom + O(1) deletes
Sliding Window	Time-decaying frequency tracking	Approximate, bucket-based aging
Decay Counter	Exponential time weighting	Smooth decay factor α per tick
Binary Codec	Sketch serialization/merge	Lossless round-trip

Quick Start

# Run the CLI demo
moon run cli

# Run all tests
moon test --target all

# Run benchmarks
moon run bench

Module Structure

moon-frequency-sketch/
├── hash/               # MurmurHash3, FNV-1a, xxHash
├── sketch/
│   ├── cms/            # Count-Min Sketch + Merge + Config
│   ├── topk/           # Space-Saving + Misra-Gries + HeavyHitters
│   ├── countsketch/    # Count Sketch + Median Estimator
│   └── bloomfilter/    # Bloom Filter + Counting Bloom Filter
├── window/             # RingBuffer + SlidingWindow + DecayCounter
├── codec/              # Binary serialization + Snapshot + Merge protocol
├── bench/              # Benchmark driver
└── cli/                # Command-line demo tool

Usage Examples

Count-Min Sketch

// Create a CMS from error bounds: ε=0.001, δ=0.01
let cms = CountMinSketch::from_error(0.001, 0.01)

// Track API call frequencies
cms.add_str("/api/users", 1L)
cms.add_str("/api/products", 1L)
cms.add_str("/api/users", 1L)

// Query estimated frequency
let freq = cms.estimate_str("/api/users") // ≥ 2
println("Frequency: " + freq.to_string())

// Distributed merge
let shard_a = CountMinSketch::new(5, 2000)
let shard_b = CountMinSketch::new(5, 2000)
// ... each shard processes its data stream ...
let merged = cms_merge(shard_a, shard_b)

Heavy Hitters (Space-Saving)

// Track top-20 most frequent URLs
let hh = HeavyHitters::new(SpaceSavingAlgo, 20)
hh.add("/home")
hh.add("/home")
hh.add("/about")

let top5 = hh.top_k(5)
for entry in top5 {
  println(entry.key + ": " + entry.estimated_count.to_string())
}

Bloom Filter

// Create Bloom filter for 100,000 items with 1% FP rate
let bf = BloomFilter::from_params(100000, 0.01)
bf.add_str("user:alice")
bf.add_str("user:bob")

if bf.contains_str("user:alice") {
  println("Possibly in set")
}

Sliding Window

// 10-bucket sliding window, each bucket is a CMS(4×200)
let sw = SlidingWindow::new(10, 4, 200)
sw.add_str("/api/endpoint", 5L)

// Advance time by one bucket
sw.tick()

// Estimate frequency in current window
let est = sw.estimate_str("/api/endpoint")

Serialization

// Serialize a sketch for network transfer or disk persistence
let sketch = CountMinSketch::new(5, 1000)
sketch.add_str("key", 42L)

let bytes = cms_serialize(sketch)
// ... transfer bytes ...

match cms_deserialize(bytes) {
  Ok(restored) => println(restored.estimate_str("key").to_string())
  Err(_) => println("Deserialization failed")
}

Algorithm Details

Count-Min Sketch Error Bounds

Given depth d and width w, and N total insertions:

• Space: O(d × w) = O((1/ε) × ln(1/δ)) counters
• Error: With probability ≥ 1 − δ: f̂(x) ≤ f(x) + ε·N
• Update/Query time: O(d) = O(ln(1/δ))

Typical parameters:

• d = 5, w = 2000 → δ ≈ 0.0067, ε ≈ 0.00136

Space-Saving Guarantee

A Space-Saving summary with k counters guarantees that every element with true frequency f(x) > N/k appears in the output. The over-count error per element is bounded by the minimum counter at eviction time.

Hash Functions

Three independent hash families are provided:

• MurmurHash3: Excellent avalanche, fast for short strings
• FNV-1a: Minimal implementation, good for integers
• xxHash32: Cache-friendly for bulk data

All support multi-hash generation via seeded variants.

Theoretical Background

This library implements classical streaming algorithms from the data streams literature:

• Cormode & Muthukrishnan (2005): An Improved Data Stream Summary: The Count-Min Sketch and its Applications
• Metwally, García-Molina & Agrawal (2005): Efficient Computation of Frequent and Top-k Elements in Data Streams
• Misra & Gries (1982): Finding Repeated Elements
• Charikar, Chen & Farach-Colton (2002): Finding Frequent Items in Data Streams (Count Sketch)
• Bloom (1970): Space/Time Trade-offs in Hash Coding with Allowable Errors

Build & Test

# Build
moon build --target all

# Test with formatting and interface checks
moon fmt --deny-warn
moon info --deny-warn
moon test --target all

# Run benchmarks
moon run bench

# Run CLI demo
moon run cli

CI

This project uses GitHub Actions with a three-platform matrix (Linux, macOS, Windows). Both workflows (ci.yml and check.yml) enforce moon fmt --deny-warn and moon info --deny-warn to ensure code quality.

License

Apache License 2.0. See LICENSE.

Project Origin

This is an original MoonBit implementation. The algorithms are well-known in the streaming algorithms literature (cited above) and have been implemented from scratch in MoonBit for the OSC 2026 competition. No source code from other repositories has been copied or adapted.