MoonSketch

MoonSketch is a MoonBit library for streaming sketches and approximate analytics.

The project focuses on reusable data structures for large-scale or continuous data streams, including frequency estimation, cardinality estimation, heavy hitter detection, and online sampling.

Motivation

Many systems need to answer questions such as:

• How many distinct users appeared in a stream?
• Which keys are the most frequent?
• How often did an item appear?
• How can we sample from an unknown-length stream?

Exact data structures can be expensive when the input stream is large. Sketch-based algorithms provide approximate answers with bounded memory and predictable error behavior.

MoonSketch aims to provide these capabilities as a native MoonBit package.

Planned Components

The first version will focus on the following components:

• Count-Min Sketch for approximate frequency estimation
• HyperLogLog for approximate cardinality estimation
• Space-Saving Top-K for heavy hitter detection
• Reservoir Sampling for online random sampling
• Shared seeded hash utilities
• Tests, examples, and basic benchmarks

Non-goals

MoonSketch does not aim to duplicate existing MoonBit Bloom Filter projects.

Bloom Filter and Bloomier Filter already exist in the MoonBit ecosystem, so this project focuses on streaming analytics sketches rather than membership-query filters.

Example Use Cases

• Log analytics
• Event stream monitoring
• Recommendation item popularity estimation
• Approximate UV/PV statistics
• Cache and service telemetry
• Lightweight analytics in MoonBit applications

Current Components

• Hash Utilities: deterministic seeded hash helpers for sketch prototypes.
• Count-Min Sketch: approximate frequency estimation for integer streams.
• HyperLogLog: initial register structure for approximate cardinality estimation.

Examples

See docs/EXAMPLES.md for example use cases such as item frequency estimation, log event counting, and recommendation item popularity tracking.

Changelog

See CHANGELOG.md for the current development history.

Stage-One Checklist

See docs/STAGE_ONE_CHECKLIST.md for the current OSC 2026 stage-one preparation status.

Roadmap

See docs/ROADMAP.md for the project scope, planned modules, non-goals, and implementation milestones.

Status

MoonSketch is currently in the OSC 2026 stage-one preparation stage.

The repository already includes:

• deterministic hash utilities;
• Count-Min Sketch core implementation, merge support, tests, and documentation;
• initial HyperLogLog register structure, tests, and documentation;
• examples, roadmap, changelog, and stage-one submission checklist.

License

Apache License 2.0.