We propose DiCar, a novel sketch that supports flexible and memory-efficient estimation of diverse cardinalities. The core innovations include: 1) A hierarchical structure that supports adaptive extensions to provide memory-efficient tracking on skewed cardinality distributions; 2) A lossless extension algorithm based on modular arithmetic theorem to enable flexible shifting between different estimation tasks. Evaluations on real-world traces demonstrate that DiCar outperforms existing methods by achieving 3.5-4.3 × lower average relative errors with only 0.5MB memory and maintains < 3% false positive rate in detecting super nodes with high cardinalities.
Xia et al. (Thu,) studied this question.