We Built asap_sketchlib, the Fastest Sketching-Algorithm Library

TL;DR — We built asap_sketchlib, a Rust library of sketching algorithms and the fastest one we know of. In our benchmarks it reaches up to 11.4× higher throughput than other sketch libraries.

In our previous blog, we gave an intuitive explanation of what sketches are and why they are so useful for computing aggregations over large volumes of data. Here, ProjectASAP is releasing asap_sketchlib. Built in Rust, it reaches 93.8M inserts/sec and 65.2M queries/sec for Count-Min Sketch in our benchmarks¹, with throughput gaps of 11.4× for insertions and 11.1× for queries over Apache DataSketches Rust. asap_sketchlib v0.2.2² supports 13 sketches (and we’re adding more!) for aggregations such as frequency estimation, cardinality estimation, quantile estimation, heavy-hitter detection, and entropy estimation. Below, we provide a few examples of how to use asap_sketchlib, along with performance benchmarks.

Today, you can simply use asap_sketchlib in your Rust codebase by running: cargo add asap_sketchlib!

An example: using asap_sketchlib for cardinality estimation

Suppose you want to count how many distinct user IDs appear in a large data stream. As discussed in our previous blog, exact data structures are often the natural starting point, but their memory usage can become expensive at scale. In that post, an exact set used 63× more memory than HyperLogLog on one workload. For cardinality estimation, HyperLogLog³ offers a sketch-based alternative: it estimates the number of distinct items without storing every unique ID.

The following example starts with the exact HashSet approach and then shows the corresponding asap_sketchlib version. The code shape is similar, but the tradeoff is different: HashSet gives an exact answer by retaining all distinct IDs, while HyperLogLog gives an approximate, yet accurate answer using a compact, fixed-size state.

let mut exact = HashSet::new();
for &id in &user_ids {
    exact.insert(id);
}
let exact_count = exact.len(); // exact distinct count

When an approximate answer is sufficient, we can use HyperLogLog instead. It follows a similar insert-and-query pattern without storing every distinct user ID.

// ErtlMLE is an HLL estimator variant, more accurate than Classic at very low or very high cardinalities.
let mut hll = HyperLogLog::<ErtlMLE>::default();
for &id in &user_ids {
    hll.insert(&DataInput::U64(id));
}
let estimated_count = hll.estimate(); // approximate distinct count

See the HyperLogLog API docs for the available estimator variants and how to choose one.

The full runnable example is available in the asap_sketchlib repository.

An example: using asap_sketchlib for frequency estimation

The same pattern applies to frequency estimation. Suppose you want to know how many times a specific user ID appears in a large data stream. A natural exact solution is to use a HashMap: store one counter for each distinct user ID, increment the counter on every occurrence, and look up the count at the end.

let mut counts: HashMap<u64, u64> = HashMap::new();
for &id in &user_ids {
    *counts.entry(id).or_insert(0) += 1;
}
let exact_count = counts[&target_id]; // exact frequency

When an approximate answer is sufficient, Count-Min Sketch keeps its memory fixed no matter how many distinct keys appear.

// FixedMatrix: a statically-sized array, so memory is bounded and known at compile time.
// FastPath: reuses a single hash across all rows (bit-masking picks each row's index).
let mut cms = CountMin::<FixedMatrix, FastPath>::default();
for &id in &user_ids {
    cms.insert(&DataInput::U64(id));
}
let estimated_count = cms.estimate(&DataInput::U64(target_id)); // approximate frequency

See frequency_cms.rs for the full runnable example.

Benchmarks

The examples above used exact data structures (HashSet, HashMap) as a familiar reference. Here we measure asap_sketchlib against other sketch libraries on throughput, and against Polars on an end-to-end quantile workload.

Highlights

• 11.4× higher insertion throughput than Apache DataSketches Rust (93.8M vs 8.2M inserts/sec)
• 11.1× higher query throughput than Apache DataSketches Rust (65.2M vs 5.9M queries/sec)
• 37.2× lower quantile analysis latency than Polars (214.4ms vs 7,979.7ms)
• 6-7× higher throughput than sketch_oxide, the fastest alternative

Setup

We measure the throughput of Count-Min Sketch⁴ and Count Sketch⁵, two classic sketches for frequency estimation. Both support the frequency estimation query: “How many times has item x appeared in the stream?”

We benchmark asap_sketchlib⁶ against sketch_oxide⁷ (a Rust library containing various sketch implementations) and Apache DataSketches ([C++]⁸, [Rust]⁹). We use synthetic data consisting of 10M items drawn from a Zipf distribution with skewness s=1.1 and support size k=100K. Each sketch is configured with 5 rows and 32768 counters per row, and every implementation is built with release optimizations.¹ Apache DataSketches implements only Count-Min Sketch, not Count Sketch, so the Count Sketch panels compare asap_sketchlib against sketch_oxide only.

Accuracy

The sketch size is chosen to provide good accuracy on this workload. We assess this on heavy hitters, defined as items that appear at least 1,000 times in the 10M-item stream. Although these heavy hitters represent only a small fraction of the distinct items, their occurrences account for more than 70% of the stream, making them the most important items to estimate well in this skewed workload.

Under this configuration, asap_sketchlib achieves a mean relative error of 0.54% for Count-Min Sketch and 0.69% for Count Sketch on those items, averaged over 10 runs, consistent with the algorithm’s theoretical accuracy.

Insertion throughput

The figure shows the throughput comparison. All benchmark results are single-threaded and use one CPU core for simplicity. For Count-Min Sketch, asap_sketchlib reaches 93.8M inserts/sec, compared with 15.5M for sketch_oxide, 8.2M for Apache DataSketches Rust, and 9.5M for Apache DataSketches C++. Among the tested alternatives, the largest measured gap is 11.4× (93.8M / 8.2M). Even the fastest of them, sketch_oxide (15.5M), trails by about 6×. For Count Sketch, asap_sketchlib reaches 76.6M inserts/sec versus 10.7M for sketch_oxide, a 7.2× improvement. These throughput differences were stable across the 10 runs. Both sketches use the FixedMatrix and FastPath configuration shown in the earlier code example.

Query throughput

The experiment setup is the same as in the previous section. Each query asks: “what is the frequency of a specific item x?”. We issue one query for each distinct item in the data stream.

For Count-Min Sketch, asap_sketchlib reaches 65.2M queries/sec, compared with 9.8M for sketch_oxide, 5.9M for Apache DataSketches Rust, and 4.7M for Apache DataSketches C++. Among the tested alternatives, the largest measured gap is 13.9× (65.2M / 4.7M). Even the fastest of them, sketch_oxide (9.8M), trails by about 6.7×. For Count Sketch, asap_sketchlib reaches 22.2M queries/sec versus 4.9M for sketch_oxide, a 4.5× improvement. As with insertions, these gaps held across all 10 runs.

Latency compared to Polars

Quantiles are another common aggregation that we have not covered yet. A typical example is a latency percentile like p90 or p99. We compute quantiles over the same synthetic data and compare KLL¹⁰ from asap_sketchlib with Polars, a fast and widely used data processing engine written in Rust. KLL is a streaming quantile sketch that estimates quantiles using bounded memory. Polars instead computes exact quantiles by sorting the buffered data, and it has no approximate quantile option. So when an approximate answer is acceptable, KLL can return it much faster.

For a fair comparison, we measure the total latency of the full ingest-prepare-query pipeline: ingesting data, performing the necessary preparation, and querying 101 quantiles (p0, p1, p2,… p100). The following code snippet shows how this pipeline can be implemented in Polars:

use polars::prelude::*;

// Buffer all values — Polars needs the full dataset before computing quantiles.
let df = DataFrame::new(vec![Column::new("v".into(), &values)]).unwrap();

// Build quantile expressions for p0, p1, ..., p100.
let exprs: Vec<Expr> = (0..=100)
    .map(|i| {
        col("v")
            .quantile(lit(i as f64 / 100.0), QuantileMethod::Linear)
            .alias(format!("q{i}"))
    })
    .collect();

// Expensive: Polars sorts all 10M buffered values to compute exact quantiles.
// This is the dominant cost — the orange segment in the latency figure below.
let result = df.lazy().select(exprs).collect().unwrap();

// Query is now just a cached lookup; the cost was already paid above.
let p90: f64 = result.column("q90").unwrap().get(0).unwrap().try_extract().unwrap();

Unlike Polars, KLL from asap_sketchlib never sorts the full dataset: the sketch is updated incrementally as each value arrives, so quantile queries are served from a compact summary:

let mut sketch = KLL::<i64>::init_kll(200);
for v in &values {
    sketch.update(v); // sketch maintenance happens here, not at query time
}

// Build CDF once after ingestion; subsequent queries are O(log n).
let cdf: Cdf = sketch.cdf();
let p90 = cdf.query(0.90);

The full KLL example is in quantile_kll.rs.

On this workload, asap_sketchlib’s KLL completes the full pipeline in 214.4ms versus 7,979.7ms for Polars — a 37.2× speedup. The ingestion phase is faster in Polars because it only buffers the input values, while KLL performs additional sketch-maintenance work during updates. The dominant difference is the orange segment: Polars must compute exact quantiles over all 10M buffered values, whereas KLL has already maintained a compact sketch during ingestion. Once the data is ingested, querying the 101 quantiles is negligible for both.

What’s next

We will show an asap_sketchlib primer next, on how to use the library for accelerating data analytics and observability-query tasks. Stay tuned!

Sketches supported in asap_sketchlib v0.2.2

The sketches we provide are:

• Count-Min Sketch (CMS) — frequency estimation
• Count Sketch (CS) — frequency estimation
• HyperLogLog (HLL) — cardinality estimation
• K Minimum Values (KMV) — cardinality estimation
• KLL (Karnin–Lang–Liberty) — quantile estimation
• DDSketch (DD) — quantile estimation with relative-error guarantees
• Elastic Sketch — adaptive flow-size measurement
• CocoSketch (Coco) — arbitrary partial-key queries
• OctoSketch (Octo) — multi-core sketch aggregation
• UnivMon (Universal Monitoring) — universal sketch for multiple statistics
• Hydra — subpopulation queries over multidimensional streams
• NitroSketch (Nitro) — sampling-accelerated sketch updates
• Exponential Histogram (EH) — approximate statistics over sliding windows (implementation context from the PromSketch paper¹¹)

For an in-depth description of each, see this page.