alecmocatta / streaming_algorithms

Performant implementations of various streaming algorithms, including Count–min sketch, Top k, HyperLogLog, Reservoir sampling.

streaming_algorithms

📖 Docs | 💬 Chat

SIMD-accelerated implementations of various streaming algorithms.

This library is a work in progress. PRs are very welcome! Currently implemented algorithms include:

• Count–min sketch
• Top k (Count–min sketch plus a doubly linked hashmap to track heavy hitters / top k keys when ordered by aggregated value)
• HyperLogLog
• Reservoir sampling

A goal of this library is to enable composition of these algorithms; for example Top k + HyperLogLog to enable an approximate version of something akin to SELECT key FROM table GROUP BY key ORDER BY COUNT(DISTINCT value) DESC LIMIT k.

Run your application with RUSTFLAGS="-C target-cpu=native" and the nightly feature to benefit from the SIMD-acceleration like so:

RUSTFLAGS="-C target-cpu=native" cargo run --features "streaming_algorithms/nightly" --release

See this gist for a good list of further algorithms to be implemented. Other resources are Probabilistic data structures – Wikipedia, DataSketches – A similar Java library originating at Yahoo, and Algebird – A similar Java library originating at Twitter.

As these implementations are often in hot code paths, unsafe is used, albeit only when necessary to a) achieve the asymptotically optimal algorithm or b) mitigate an observed bottleneck.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE.txt or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT.txt or http://opensource.org/licenses/MIT)

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

streaming_algorithms's Issues

hyperlogloglog one log more

Hello Team,

Recently, the hyperlogloglog was published to be even more space efficient. Just wondering whether it is possible to also add it: https://dl.acm.org/doi/abs/10.1145/3534678.3539246

Thanks,

Jianshu

better HLL estimator

Hello Team,

It seems that new cardinality estimator paper has two new estimators, the improved estimator and MLE estimator, better than the one originally proposed, see paper here: https://arxiv.org/pdf/1706.07290.pdf

Just wondering whether it worth trying, C++ version can be found in the paper.

Thank you,

Jianshu

Is this abandoned?

There are dependency updates like the rand one from dependabot not merged. It looks like a useful crate but I'm trying to assess whether I'd need to fork it or whether it is still maintained.

nightly features packed sims feature not available

Hello @alecmocatta,

Since the nightly Rust v1.78, feature stdsimd does not exists any more:
error[E0557]: feature has been removed
--> /Users/jianshuzhao/.cargo/registry/src/index.crates.io-6f17d22bba15001f/packed_simd-0.3.9/src/lib.rs:218:5
|
218 | platform_intrinsics,
| ^^^^^^^^^^^^^^^^^^^ feature has been removed
|
= note: SIMD intrinsics use the regular intrinsics ABI now

We need some updates.

Thanks,

Jianshu