Calculating the number of distinct values (i.e., NDV) in a column of a big table is costly yet fundamental to a variety of database applications such as data compression and profiling. To reduce the high time and space cost, a number of sketch methods (e.g., HyperLogLog) have been proposed, which estimate the NDV from a constructed compact data summary of distinct values. However, these methods fail or are costly to manage fully-dynamic scenarios where data is often inserted into and deleted from the table. To solve this issue, we propose a novel sketch method, Half-Xor . Our Half-Xor sketch consists of a compact bit matrix and a small counter array, and it needs to set a few bits and update a counter when handling a data insertion/deletion. Compared with the state-of-the-art mergeable method, our experimental results demonstrate that our method Half-Xor is up to 6.6 times more accurate under the same memory usage and reduces the memory usage by up to 16 times to achieve the same estimation accuracy.
12 March 2024 in Proceedings of the ACM on Management of Data
Given two sets of elements held by two different parties separately, computing the cardinality (i.e., the number of distinct elements) of their intersection set is a fundamental task in applications such as network monitoring and database systems. To handle large sets with limited space, computation, and communication costs, lightweight probabilistic methods (i.e., sketch methods) such as the Flajolet-Martin (FM) sketch and the HyperLogLog (HLL) sketch are extensively used. However, when a set's probabilistic data summary and the hash functions used to construct the sketch are disclosed to an untrusted third party, the set's privacy is compromised. Directly applyingLocal Differential Privacy (LDP) techniques to safeguard the sketch collection results in extremely large estimation errors of set intersection cardinalities. To address this issue, we propose a novel sketch method that makes it easier to incorporate noise into the constructed sketch to achieve differential privacy. More importantly, our sketch method is compatible with the LDP noise. In other words, the probabilistic model underlying our LDP-based data summary is quite basic, allowing us to eliminate the estimation error generated by the noise. We perform extensive experiments on various synthetic and real-world datasets and the experimental results demonstrate that our method is orders of magnitude more accurate and several times faster than state-of-the-art methods.
24 December 2025 in IEEE Transactions on Dependable and Secure Computing
Computing the number of distinct elements (i.e., cardinality) in the intersection of two sets is a fundamental task in various distributed systems, including measuring origin-destination flows in wide-area networks and data synchronization in distributed databases. Due to the enormous data scale, lightweight probabilistic methods, such as FM sketch and HyperLogLog sketch, are extensively used in these systems to estimate the set intersection cardinality, with memory efficiency, high accuracy, and low communication costs. However, if a set's sketch and the hash functions used to construct the sketch are disclosed to an untrusted third party, the privacy of the set's sensitive elements may be compromised. Applying the differential privacy mechanism directly to safeguard the sketch's privacy may incur significant estimation errors. To address this challenge, we propose a novel private sketch, SetXor, for securely estimating intersection cardinality for static sets. Specifically, we incorporate the randomized response noise into the constructed sketch to achieve local differential privacy while ensuring our SetXor sketch is mergeable. We establish a concrete probabilistic model to mitigate the estimation error caused by the noise and theoretically analyze the variance. We further propose a novel sketch SetXorDyn enabling intersection cardinality estimation for streaming sets where elements appear sequentially and contain duplicates. We employ a sampling-like method to eliminate the impact of different parities of element occurrences, allowing us to handle all elements without bias. We conduct extensive experiments on synthetic and four real-world datasets. The results demonstrate that our methods reduce the Average Absolute Relative Error (AARE) of state-of-the-art baselines by up to $110\times$ on synthetic datasets and $80\times$ on real-world datasets, while achieving up to $18.7\times$ speedup under the same settings.
22 September 2025 in Proceedings of the ACM on Management of Data
Counting the number of distinct values (NDV) is a fundamental problem in web applications and databases, particularly under memory constraints. Sketch-based methods, such as the Flajolet-Martin sketch, construct compact data summaries to estimate NDV but primarily focus on insertion-only scenarios. However, supporting delete operations is crucial for maintaining accurate and up-to-date cardinality estimates in many real-world applications, such as databases. Existing methods for fully dynamic scenarios, involving both insertions and deletions, often incur considerable computational and memory overhead. Furthermore, collaborative computation often requires sharing sketches with external or untrusted parties, which introduces significant privacy risks. To address these challenges, we propose a novel sketch method, GMod, specifically designed for fully dynamic scenarios and compatible with local differential privacy (LDP) for both NDV estimation and privacy preservation. Our method supports efficient deletions with minimal additional overhead by utilizing a single discrete uniformly distributed random variable. Additionally, we introduce a lightweight probabilistic estimation model to compute NDV, achieving 3× faster performance compared to the state-of-the-art. By incorporating carefully designed sketch perturbation mechanisms, our model mitigates the impact of LDP noise. Experimental results demonstrate that our method uses 1/3 of the memory to achieve comparable estimation accuracy in local settings and provides 8× higher accuracy under LDP scenarios compared to state-of-the-art methods.
5 June 2019 in DEStech Transactions on Social Science, Education and Human Science
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.