The 1B Challenge¶

A story of memory management, algorithmic trade-offs, and the satisfying click of watching numbers improve.

At the core of rusket is the belief that frequent itemset mining should scale on a single machine. No Spark cluster, no distributed coordination — just one process, tuned to be as efficient as possible.

The 1 Billion Row Challenge is how we hold ourselves accountable.

Where We Started: Sorted Chunks + K-Way Merge¶

The first streaming design took inspiration from external-sort databases:

1. Each call to add_chunk() receives (txn_id, item_id) arrays from Python.
2. Rust sorts each chunk in-place using rayon::par_sort_unstable().
3. Chunks exceeding the RAM budget are spilled to anonymous tempfile files on disk.
4. When .mine() is called, a k-way heap merge streams all sorted chunks in order, building the CSR matrix on the fly.

Memory: O(chunk_size)
mine() memory: O(k cursors + CSR output)

The first problem: disk exhaustion¶

Running the 500M → 1B targets, our machine hit 99% disk usage. The culprit: 500k transactions/chunk × 23 items/txn × 12 bytes/pair = ~138 MB per chunk. At 1B rows that's ~2,000 chunks = ~276 GB of tempfiles. Oops.

The second problem: mine_t grows super-linearly¶

The heap with 1,000+ cursors causes cache thrashing — a fundamental problem with the architecture.

The Insight: HashMap Aggregation¶

The key observation: the sorted-chunk approach stores every pair from every chunk. The real data that matters is unique_transactions × avg_items_per_transaction. For 1B rows with ~43M unique transactions × 23 items: that's only ~5GB vs the sorted approach's ~12GB.

We replaced the entire chunk + merge system with a single AHashMap<i64, Vec<i32>>:

pub fn add_chunk(&mut self, txn_ids: ..., item_ids: ...) {
    for (&t, &i) in txns.iter().zip(items.iter()) {
        self.txns.entry(t).or_default().push(i);
    }
}

mine() now just:

1. Collects (txn_id, &items) from the HashMap
2. par_sort by txn_id
3. Sort+dedup each transaction's item list
4. Build CSR → feed to algorithm

No k-way merge. No disk spill. No tempfiles.

Initial numbers (100M & 200M, FP-Growth)¶

Compared to the old approach's 300M taking 299.5s — a 3× speedup just from the architecture change.

What We Tried: The Iteration Phase¶

Approach: SmallVec + u16 items (❌ Regression)¶

Using SmallVec<[u16; 32]> to store items inline on the stack caused a 2× slowdown. The 32-element inline size is too large for the CPU stack, causes cache pressure on every HashMap lookup.

Lesson: measure first, optimize second.

Knob: Chunk size (100k vs 500k vs 2M)¶

Chunk size barely matters.

Knob: Algorithm (FP-Growth vs Eclat)¶

This was the biggest discovery. At 100M rows:

Eclat is ~14× faster at mining for dense retail data. The reason: Eclat works with vertical tidlists — for dense datasets with many frequent 2-itemsets, intersection operations are extremely cache-friendly.

Final Results: The Road to 1B¶

Dense retail data (avg 23 items/txn)¶

✅ 1 Billion rows. 382 seconds. 15,233 frequent itemsets. No OOM. No disk spill.

Sparse catalogue data (avg 4.4 items/txn)¶

The 1B challenge for sparse datasets remains open.

What We Learned¶

Architecture beats micro-optimisation¶

The jump from k-way merge → HashMap changed 5-minute runs into 30-second runs.

Eclat vs FP-Growth depends on density¶

Running It Yourself¶

from rusket import FPMiner
import numpy as np

miner = FPMiner(n_items=your_n_items)

for txn_ids_chunk, item_ids_chunk in your_data_stream():
    miner.add_chunk(
        txn_ids_chunk.astype(np.int64),
        item_ids_chunk.astype(np.int32),
    )

freq = miner.mine(min_support=0.02, max_len=3, method="eclat")
print(f"Found {len(freq):,} frequent itemsets")

The full benchmark script is in benchmarks/bench_fpminer_realistic.py.