hyperloglog_rs/
lib.rs

1//! # HyperLogLog
2//!
3//! This crate provides an implementation of the HyperLogLog algorithm, which is a probabilistic algorithm used to estimate
4//! the number of distinct elements in a set. The algorithm uses a fixed amount of memory and is able to estimate the number
5//! of distinct elements with a small relative error.
6//!
7//! The `HyperLogLog` struct provided by this crate is parametrized by two constants: `PRECISION` and `BITS`. `PRECISION`
8//! determines the number of bits used to index a register, and `BITS` determines the number of bits used to represent
9//! the hashed value of an element. The optimal values of these constants depend on the expected number of distinct elements
10//! and the available memory.
11//!
12//! This implementation already provides almost all the benefits available from [HyperLogLog++](https://static.googleusercontent.com/media/research.google.com/it//pubs/archive/40671.pdf).
13//! We **do not** intend to integrate the sparse registers feature, as the use cases for this library focus of cases
14//! where registers need to be a relatively small number and a dense set. Except for that, all
15//! other observations provided in the HLL++ paper are already implemented.
16//!
17//! ## No STD
18//! This crate is designed to be as lightweight as possible and does not require any dependencies from the Rust standard library (std). As a result, it can be used in a bare metal or embedded context, where std may not be available.
19//!
20//! All functionality of this crate can be used without std, and the prelude module provides easy access to all the relevant types and traits. If you encounter any issues using this crate in a no_std environment, please don't hesitate to open an issue or submit a pull request on GitHub.
21//!
22//! ## Usage
23//!
24//! Add this to your `Cargo.toml`:
25//!
26//! ```toml
27//! [dependencies]
28//! hyperloglog = "0.1"
29//! ```
30//!
31//! and this to your crate root:
32//!
33//! ```rust
34//! use hyperloglog_rs::prelude::*;
35//! ```
36//!
37//! ## Examples
38//!
39//! ```rust
40//! use hyperloglog_rs::prelude::*;
41//!
42//! let mut hll = HyperLogLog::<Precision14, 5>::default();
43//! hll.insert(&1);
44//! hll.insert(&2);
45//!
46//! let mut hll2 = HyperLogLog::<Precision14, 5>::default();
47//! hll2.insert(&2);
48//! hll2.insert(&3);
49//!
50//! let union = hll | hll2;
51//!
52//! let estimated_cardinality = union.estimate_cardinality();
53//! assert!(estimated_cardinality >= 3.0_f32 * 0.9 &&
54//!         estimated_cardinality <= 3.0_f32 * 1.1);
55//! ```
56//!
57//! ## Fuzzing
58//! Fuzzing is a technique for finding security vulnerabilities and bugs in software by
59//! providing random input to the code. It can be an effective way of uncovering issues
60//! that might not be discovered through other testing methods. In our library,
61//! we take fuzzing seriously, and we use the [cargo fuzz](https://github.com/rust-fuzz/cargo-fuzz)
62//! tool to ensure our code is robust and secure. cargo fuzz automates the process of generating
63//! and running randomized test inputs, and it can help identify obscure bugs that would be
64//! difficult to detect through traditional testing methods. We make sure that our fuzz targets
65//! are continuously updated and run against the latest versions of the library to ensure that
66//! any vulnerabilities or bugs are quickly identified and addressed.
67//!
68//! [Learn more about how we fuzz here](https://github.com/LucaCappelletti94/hyperloglog-rs/tree/main/fuzz)
69//!
70//! ## References
71//!
72//! * [Flajolet, Philippe](https://en.wikipedia.org/wiki/Philippe_Flajolet), Éric Fusy, Olivier Gandouet, and Frédéric Meunier. "[Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.](https://hal.science/file/index/docid/406166/filename/FlFuGaMe07.pdf)" In Proceedings of the 2007 conference on analysis of algorithms, pp. 127-146. 2007.
73#![feature(const_float_bits_conv)]
74#![feature(const_fn_floating_point_arithmetic)]
75#![cfg_attr(not(feature = "std"), no_std)]
76
77mod array_default;
78mod bias;
79pub mod bitand;
80pub mod bitor;
81mod bitor_iter;
82pub mod estimated_union_cardinalities;
83pub mod hyper_spheres_sketch;
84pub mod hyperloglog;
85pub mod hyperloglog_array;
86mod hyperloglog_multiplicities;
87mod hyperloglog_trait;
88pub mod iter;
89pub mod log;
90mod max_min;
91mod ones;
92mod precisions;
93mod primitive;
94mod raw_estimate_data;
95pub mod serde;
96mod sip;
97pub mod utils;
98mod zeros;
99
100#[cfg(feature = "std")]
101mod exact_hyper_spheres_sketch;
102#[cfg(feature = "std")]
103mod joint_estimation;
104
105#[cfg(feature = "std")]
106mod optimizers;
107
108pub use crate::estimated_union_cardinalities::EstimatedUnionCardinalities;
109pub use crate::hyperloglog::HyperLogLog;
110
111pub mod prelude {
112    #[cfg(feature = "std")]
113    pub use crate::joint_estimation::*;
114
115    pub use crate::array_default::*;
116    pub use crate::estimated_union_cardinalities::*;
117    pub use crate::hyper_spheres_sketch::*;
118    pub use crate::hyperloglog::*;
119    pub use crate::hyperloglog_array::*;
120    pub use crate::hyperloglog_multiplicities::*;
121    pub use crate::hyperloglog_trait::*;
122    pub use crate::iter::*;
123    pub use crate::max_min::*;
124    pub use crate::ones::*;
125    #[cfg(feature = "std")]
126    pub use crate::optimizers::*;
127    pub use crate::precisions::*;
128    pub use crate::primitive::*;
129    pub use crate::serde::*;
130    pub use crate::utils::*;
131    pub use crate::zeros::*;
132    pub use core::ops::{BitOr, BitOrAssign};
133}
hyperloglog_rs/lib.rs

hyperloglog_rs/
lib.rs
