ternary-sketch

Ternary sketch data structure for approximate GPU workload analysis. Count-Min sketch with ternary counters {-1,0,+1} for streaming frequency estimation.

Why This Matters

ternary-sketch

Ternary sketch for approximate GPU workload analysis. Count-Min sketch with ternary counters.

The Five-Layer Stack

This crate is part of the Oxide Stack — a distributed GPU runtime built on five layers:

┌─────────────────┐
│  cudaclaw        │  Persistent GPU kernels, warp consensus, SmartCRDT
├─────────────────┤
│  cuda-oxide      │  Flux → MIR → Pliron → NVVM → PTX compiler
├─────────────────┤
│  flux-core       │  Bytecode VM + A2A agent protocol
├─────────────────┤
│  pincher         │  "Vector DB as runtime, LLM as compiler"
├─────────────────┤
│  open-parallel   │  Async runtime (tokio fork)
└─────────────────┘

The key insight: ternary values {-1, 0, +1} map directly to GPU compute. They pack 16× denser than FP32, enable XNOR+popcount matmul, and conservation laws become compile-time checks.

Design

Every value in this crate follows ternary algebra (Z₃):

This isn't arbitrary — ternary is the natural encoding for:

1. BitNet b1.58 (Microsoft) — ternary LLMs at 60% less power
2. GPU warp voting — hardware ballot returns ternary consensus
3. Conservation laws — {-1, 0, +1} preserves quantity

Key Types

pub struct TernarySketch
pub fn new
pub fn insert
pub fn remove
pub fn estimate
pub fn heavy_hitters
pub fn merge
pub fn fill_rate
pub fn total_updates

Usage

[dependencies]
ternary-sketch = "0.1.0"

use ternary_sketch::*;
// See src/lib.rs tests for complete working examples

Testing

git clone https://github.com/SuperInstance/ternary-sketch.git
cd ternary-sketch
cargo test    # 7 tests

Stats

License

Apache-2.0