notfilippo commented on code in PR #1: URL: https://github.com/apache/datasketches-rust/pull/1#discussion_r2617112595
########## src/hll/mod.rs: ########## @@ -0,0 +1,152 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! HyperLogLog sketch implementation for cardinality estimation. +//! +//! This module provides a probabilistic data structure for estimating the cardinality +//! (number of distinct elements) of large datasets with high accuracy and low memory usage. +//! +//! # Overview +//! +//! HyperLogLog (HLL) sketches use hash functions to estimate cardinality in logarithmic space. +//! This implementation follows the Apache DataSketches specification and supports multiple +//! storage modes that automatically adapt based on cardinality: +//! +//! - **List mode**: Stores individual values for small cardinalities +//! - **Set mode**: Uses a hash set for medium cardinalities +//! - **HLL mode**: Uses compact arrays for large cardinalities +//! +//! Mode transitions are automatic and transparent to the user. Each promotion preserves +//! all previously observed values and maintains estimation accuracy. +//! +//! # HLL Types +//! +//! Three target HLL types are supported, trading precision for memory: +//! +//! - [`HllType::Hll4`]: 4 bits per bucket (most compact) +//! - [`HllType::Hll6`]: 6 bits per bucket (balanced) +//! - [`HllType::Hll8`]: 8 bits per bucket (highest precision) +//! +//! # Serialization +//! +//! Sketches can be serialized and deserialized while preserving all state, including: +//! - Current mode and HLL type +//! - All observed values (coupons or register values) +//! - HIP accumulator state for accurate estimation +//! - Out-of-order flag for merged/deserialized sketches +//! +//! The serialization format is compatible with Apache DataSketches implementations +//! in Java and C++, enabling cross-platform sketch exchange. + +use std::hash::Hash; + +mod array4; +mod array6; +mod array8; +mod aux_map; +mod composite_interpolation; +mod container; +mod coupon_mapping; +mod cubic_interpolation; +mod estimator; +mod harmonic_numbers; +mod hash_set; +mod list; +mod serialization; +mod sketch; + +pub use sketch::HllSketch; + +/// Target HLL type. +/// +/// See [module level documentation](self) for more details. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HllType { + /// Uses a 4-bit field per HLL bucket and for large counts may require the use of a + /// small internal auxiliary array for storing statistical exceptions, which are rare. + /// For the values of lgConfigK > 13 (K = 8192), this additional array adds about 3% + /// to the overall storage. + /// + /// It is generally the slowest in terms of update time, but has the smallest storage + /// footprint of about K/2 * 1.03 bytes. + Hll4, + /// Uses a 6-bit field per HLL bucket. It is the generally the next fastest in terms Review Comment: https://apache.github.io/datasketches-java/8.0.0/org/apache/datasketches/hll/package-summary.html#hll-6-heading I copy-pasted the original description. Seems like the Java docs might need an update for this as well. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
