A comprehensive Python toolkit for cardinality estimation algorithms, enabling privacy-preserving analytics through probabilistic counting techniques.
CardinalityKit provides implementations of state-of-the-art algorithms for estimating the number of unique elements in large datasets without storing individual values. This is crucial for:
- Privacy-Preserving Analytics: Count unique users without exposing individual identifiers
- Memory Efficiency: Use minimal memory regardless of dataset size
- Cross-Platform Deduplication: Estimate unique reach across multiple platforms
- Sample-Based Extrapolation: Convert panel data to population-level estimates
- Flajolet-Martin: Historical probabilistic counting algorithm
- LogLog: Improved memory efficiency with bucket averaging
- SuperLogLog: Enhanced accuracy with outlier elimination
- HyperLogLog (HLL): Industry-standard algorithm (used by Redis, PostgreSQL)
- HyperReal (HR): Unbiased estimation for research applications
- Extended HyperLogLog: HLL with demographic attribute tracking
- Extended HyperReal: HR with demographic attribute tracking
- Support for audience segmentation while maintaining privacy
- Naive Association: Simple sample-to-population conversion
- Fast Association: Optimized conversion with configurable precision
- Convert survey/panel data to full population estimates
pip install cardinalitykit# Clone the repository
git clone https://github.com/GiacomoSaccaggi/CardinalityKit.git
cd CardinalityKit
# Install the package in development mode
pip install -e .- Python 3.7+
- numpy >= 1.19.0
- pandas >= 1.1.0
- tqdm >= 4.50.0
- scipy >= 1.5.0
from cardinalitykit import HyperLogLogEstimator
import hashlib
# Create estimator with k=10 (1024 buckets)
hll = HyperLogLogEstimator(k=10)
# Process your data
data = ["user_1", "user_2", "user_3", "user_1"] # user_1 appears twice
for item in data:
# Hash the item to binary
hash_val = '{:32b}'.format(int(hashlib.sha256(item.encode()).hexdigest()[:8], 16))
hll.update(hash_val)
# Get estimate
estimate = hll.estimate()
print(f"Estimated unique count: {estimate:.0f}") # Output: ~3
print(f"Memory used: {hll.memory_usage()} bytes") # Output: 1024 bytesfrom cardinalitykit import ExtendedHyperLogLogSketch
# Create extended sketch
ehll = ExtendedHyperLogLogSketch(b_m=8, b_s=8)
# Process events with attributes
events = [
{'id_to_count': 'user_1', 'attribute': 'age_18_24'},
{'id_to_count': 'user_2', 'attribute': 'age_25_34'},
{'id_to_count': 'user_3', 'attribute': 'age_18_24'},
]
for event in events:
ehll.update_sketch(event)
# Get total and per-attribute estimates
total = ehll.get_cardinality_estimate()
by_age = ehll.get_frequency_for_attr()
print(f"Total unique users: {total:.0f}")
print(f"By age group: {by_age}")from cardinalitykit import ExtendedHyperRealSketchFromSample
# Sample data: (id, weight, attribute)
sample_data = [
("panelist_1", 0.4, "demographic_A"),
("panelist_2", 0.6, "demographic_B")
]
# Create converter
converter = ExtendedHyperRealSketchFromSample(b_m=8, sample_data=sample_data)
# Run association (choose naive or fast)
converter.naive_associate(sum_weights=10000)
# OR for better performance:
# converter.fast_associate(sum_weights=10000, D=100)
# Get population estimates
estimate = converter.get_cardinality_estimate()
attr_freq = converter.get_frequency_for_attr()
print(f"Estimated population: {estimate:.0f}")
print(f"By demographic: {attr_freq}")| Algorithm | Memory | Accuracy | Error Rate | Use Case |
|---|---|---|---|---|
| Flajolet-Martin | Low | Basic | ~30% | Historical reference |
| LogLog | Medium | Good | ~5% | General purpose |
| SuperLogLog | Medium | Better | ~3% | Outlier elimination |
| HyperLogLog | Medium | Best | ~1.04/√m | Industry standard |
| HyperReal | Medium | Excellent | Unbiased | Research/high precision |
Error rates are approximate and depend on the number of buckets (m = 2^k)
The k parameter controls the number of buckets (m = 2^k) and affects accuracy vs memory:
# Low memory, lower accuracy (~3.2% error)
hll = HyperLogLogEstimator(k=10) # 1 KB
# Balanced (recommended)
hll = HyperLogLogEstimator(k=14) # 16 KB, ~0.8% error
# High accuracy (~0.4% error)
hll = HyperLogLogEstimator(k=16) # 64 KBStandard error formula: 1.04 / sqrt(2^k)
Run the included examples:
python -m cardinalitykit.examplesOr run specific examples:
from cardinalitykit.examples import *
basic_example() # Basic HyperLogLog usage
comparison_example() # Compare all algorithms
extended_example() # Extended algorithms with attributes
sample_conversion_example() # Sample data conversionEstimate unique visitors without storing user IDs:
# Process millions of user IDs
for user_id in user_stream:
hash_val = hash_function(user_id)
hll.update(hash_val)
# Get estimate without exposing individual users
unique_visitors = hll.estimate()Combine sketches from different platforms:
# Each platform creates its own sketch
mobile_hll = HyperLogLogEstimator(k=14)
web_hll = HyperLogLogEstimator(k=14)
# Merge sketches (implementation in extended algorithms)
# Get deduplicated total reachStream processing with constant memory:
# Memory usage stays constant regardless of stream size
for event in infinite_stream:
hll.update(hash_function(event.user_id))
if event.timestamp % 1000 == 0:
print(f"Current unique users: {hll.estimate():.0f}")Full documentation available in the documentation/ folder:
- Fundamentals - Core concepts
- HyperLogLog - HLL algorithm details
- HyperReal - HR algorithm details
- Extended Algorithms - Attribute tracking
- Panel Conversion - Sample conversion guide
# Compare all algorithms
cd simulation/Simulation\ of\ the\ various\ algorithms/
python main.py
# HyperLogLog vs HyperReal comparison
cd simulation/HLL\ vs\ HR/
python main_HLL_vs_HR.py
# Sample conversion experiments
cd simulation/From\ Sample\ to\ Hr/
python From_Sample_to_HR_Fast_Association.py# Install dev dependencies
pip install -e ".[dev]"
# Run tests
pytest
# Run with coverage
pytest --cov=cardinalitykit --cov-report=html- Update: O(1) - constant time per element
- Estimate: O(m) - linear in number of buckets
- Memory: O(m) - fixed regardless of input size
- Streaming: Supports unlimited input size
MIT License - See LICENSE file for details
- Flajolet, P., & Martin, G. N. (1985). "Probabilistic counting algorithms for data base applications"
- Durand, M., & Flajolet, P. (2003). "Loglog counting of large cardinalities"
- Flajolet, P., et al. (2007). "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm"
Contributions are welcome! Please feel free to submit a Pull Request.
Giacomo Saccaggi — GitHub
For questions and issues, please open an issue on GitHub.