notfilippo commented on code in PR #1: URL: https://github.com/apache/datasketches-rust/pull/1#discussion_r2616342597
########## src/hll/mod.rs: ########## @@ -0,0 +1,132 @@ +// 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 coupons for small cardinalities +//! - **Set mode**: Uses a hash set for medium cardinalities +//! - **HLL mode**: Uses compact arrays for large cardinalities +//! +//! # 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) +//! +//! # Coupons +//! +//! A coupon is a 32-bit value encoding both a slot number (26 bits) and a value (6 bits). +//! The slot identifies which bucket to update, and the value represents the number of +//! leading zeros in the hash plus one. + +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; + +// Re-export public API +pub use sketch::HllSketch; + +/// Target HLL type +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HllType { + Hll4 = 0, + Hll6 = 1, + Hll8 = 2, +} + +const KEY_BITS_26: u32 = 26; +const KEY_MASK_26: u32 = (1 << KEY_BITS_26) - 1; + +const COUPON_RSE_FACTOR: f64 = 0.409; // at transition point not the asymptote +const COUPON_RSE: f64 = COUPON_RSE_FACTOR / (1 << 13) as f64; + +// Constants +const RESIZE_NUMER: u32 = 3; // Resize at 3/4 = 75% load factor +const RESIZE_DENOM: u32 = 4; + +/// Extract slot number (low 26 bits) from coupon +#[inline] +fn get_slot(coupon: u32) -> u32 { + coupon & KEY_MASK_26 +} + +/// Extract value (upper 6 bits) from coupon +#[inline] +fn get_value(coupon: u32) -> u8 { + (coupon >> KEY_BITS_26) as u8 +} + +/// Pack slot number and value into a coupon +/// +/// Format: [value (6 bits) << 26] | [slot (26 bits)] +#[inline] +fn pack_coupon(slot: u32, value: u8) -> u32 { + ((value as u32) << KEY_BITS_26) | (slot & KEY_MASK_26) +} + +pub fn coupon<H: Hash>(v: H) -> u32 { Review Comment: Yeah that function definitely belongs to just a plan `fn` visibility, I forgot to mark it as such; we can promote it `pub(crate) fn` once we have other sketches that might need the same functionality. -- 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]
