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 ourSetXorsketch 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 sketchSetXorDynenabling 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.

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.

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.

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.