ZRing: A Dynamic Sketch for Weighted Cardinality Estimation in Data Streams

Estimating the number of distinct elements in a dataset, known as cardinality estimation, plays a central role in data management tasks such as query optimization, network monitoring, and privacy-preserving analytics. In practical scenarios, data often arrive as high-speed streams, making it impractical to store or process the entire dataset. This challenge is further exacerbated in Weighted Cardinality Estimation (WCE), where elements carry different importance levels, and the goal is to estimate the total weight of distinct elements. While existing solutions address WCE under insert-only assumptions, they fall short in fully dynamic settings where both insertions and deletions occur. In this work, we propose a novel sketch-based approach for fully dynamic WCE. We first develop a multi-layer perceptron-based estimator that learns from the structural features of the sketch. To further enhance accuracy, we introduce a Markov-process-inspired probabilistic estimator, which yields unbiased results. We evaluate our approach on both synthetic and real-world datasets, demonstrating up to an order-of-magnitude improvement in estimation accuracy over existing techniques under the same memory budget.