# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 2 Problem Statements and Preliminaries
### FM Sketch  
A FM sketch is a data structure for probabilistic counting of distinct elements that has been introduced in [9]. It is widely used in network applications, such as data dissemination [10] and probabilistic aggregation [11; 12].  
FM sketch represents an approximation of a positive integer by a bit field \(S=s_{1},s_{2},...,s_{w}\) of length \(w\), where \(w\geq 1\). The bit field is initialized to zero at all positions. To add an element \(x\) to the sketch, it is hashed by a hash function \(h\) with geometrically distributed positive integer output, where the probability is \(P(h(x)=i)=2^{-i}\). The entry \(s_{h(x)}\) is then set to \(1\). With probability \(2^{-w}\), we have \(h(x)>w\) and no operation is performed in this case. A hash function with the necessary properties can easily be derived from a common hash function with equidistributed bit string output by using the position of the first 1-bit in the output string as the hash value.  
According to [9], an approximation \(C(S)\) of the number of distinct elements added to the sketch can be obtained by locating the end of the initial, uninterrupted sequence of ones.  
\[Z(S):=\min(\{i\in\mathds{N}_{0}\mid i<w\wedge s_{i+1}=0\}\cup\{w\}) \tag{5}\]  
\[C(S):=\frac{2^{Z(S)}}{\varphi},\varphi\approx 0.775351 \tag{6}\]  
Since the variance of \(Z(S)\) is pretty significant, the approximation \(C(S)\) in Equation (6) is not very accurate. To avoid this situation, a set of sketches will be used to represent a single value instead of only one sketch. [9] proposes the respective technique called Probabilistic Counting with Stochastic Averaging (PCSA). With PCSA, before being added there, each element is first mapped to one of the sketches by using an equidistributed hash function. If \(d\) sketches are used, denoted by \(S_{1},...,S_{d}\), the estimation for the total number of distinct elements added is then calculated through  
\[C(S_{1},...,S_{d}):=d\cdot\frac{2^{\sum_{i=1}^{d}\frac{Z(S_{i})}{d}}}{\varphi} \tag{7}\]  
However, in [9] it also points out that Equation (7) is rather inaccurate as long as the number of elements is below approximately \(10\cdot d\). According to [13], we modify Equation (7) in the following way:  
\[C(S_{1},...,S_{d}):=d\cdot\frac{2^{\sum_{i=1}^{d}\frac{Z(S_{i})}{d}}-2^{-k \cdot\sum_{i=1}^{d}\frac{Z(S_{i})}{d}}}{\varphi},\kappa\approx 1.75 \tag{8}\]  
This alleviates the initial inaccuracies, while otherwise being asymptotically equivalent to Equation (7). PCSA with \(d\) sketches yields a standard error of approximately \(0.78/\sqrt{d}\)[9; 14]. For many mobile sensing projects, it can achieve sufficiently good approximations when the sizes of dataset are reasonable.  
The FM sketch can be merged to obtain the total number of distinct elements added to any of them by a simple bitwise OR. It is important to note that, by their construction, repeatedly combining the same sketches or adding already present elements again will not change the results, no matter how often or in which order these operations occur. This makes FM sketches ideally suited for the distinct counting scheme in mobile sensing.