amadeus-streaming

Crates.ioamadeus-streaming
lib.rsamadeus-streaming
version0.4.3
sourcesrc
created_at2020-08-07 08:07:28.020966
updated_at2021-05-20 17:24:18.867207
descriptionSIMD-accelerated implementations of various streaming algorithms, including Count–min sketch, Top k, HyperLogLog, Reservoir sampling.
homepagehttps://github.com/constellation-rs/amadeus
repositoryhttps://github.com/constellation-rs/amadeus
max_upload_size
id273899
size166,554
Alec Mocatta (alecmocatta)

documentation

https://docs.rs/amadeus

README

amadeus-streaming

SIMD-accelerated implementations of various streaming algorithms.

This is a subcrate of the amadeus project.

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.

Commit count: 550

cargo fmt