# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 4 Performance Evaluation
### Efficiency Evaluation of PPDC  
After confirming the accuracy of PPDC through a set of experiments, we explore efficiency of PPDC by testing the communication cost and computing time. 1. _Communication Overhead._ Table 1 shows the comparison of communication cost between the baseline method without privacy protection and PPDC. In Table 1, the total bits sent by a user, as the communication cost of a user, and the total bits received by the aggregator, as the communication cost of the aggregator, are the measured standards, as well as the computation complexity and round complexity of two schemes. The mentioned parameters include: \(n\) which is the total number of users, and the range of users' data is \([0,N-1]\), and \(w=\lceil\log_{2}N\rceil\) is the length of each user's bit string, and \(d\) is the number of FM sketches we applied. As the proof of Theorem 1 shows, \(1-(w/2^{q})^{d}\) is the upper limit of the correctness of PPDC. When \(q\) is approximately equal to \(w\) and not too small, the error rate of PPDC will decrease to an acceptable level (for example, less than 0.001). Meanwhile, the communication cost of PPDC affected by \(q\) would also be reduced. Besides, PPDC can send or receive less data than the baseline method when \(n\) is not greater than \(N\), i.e., \(n=O(N)\). However, the total communication cost is also influenced by the round complexity. The round complexity refers to the amount of time a user has to keep communicating online. Notice that the baseline method needs only one round of communication which is its most significant advantage. Therefore, the cases where PPDC performs better are when the network connection is stable, while when the network connection cannot stay reliable, the baseline method is more suitable. 2. _Computation Overhead._ We discuss the computing time spent during the whole process. Here, the computing time of PPDC includes the time of hash operation and coding, encryption time for each user, and the time of decryption to determine the final FM sketch \(S\) and calculating results for the aggregator. Note that 'decryption' is the decryption of the bitwise XOR of all users' plaintexts which guarantees the protection of user's privacy. The data used as a comparison is the computing time of the number of distinct counting calculated without privacy protection in Figure 9. It can be seen that it takes more time for PPDC to calculate the results. Since there are more processes like encoding, encrypting, decrypting and formula calculating than the general method, PPDC is relatively more  
Figure 8: Accuracy rate of PPDC on different size of datasets. time-consuming. However, this consumption is within an acceptable range, as shown in Figure 9; with the dataset expanding, the trend of the increase in the consumption time is slower than the linear increase. Besides, due to solving the distinct counting problem, the following other operations on the aggregated dataset will reduce resources consumption of repetitive process. Furthermore, when the size of a dataset is huge, the probability of the index \(Z(S)\) approaching the end of FM sketch \(S\) is high. With our knack in Section 3.2, the computing time will gradually decrease accordingly. Therefore, on the whole, PPDC does not waste computing time. This conclusion proves that the efficiency of PPDC is appropriate for large-scale data aggregation processing. When it comes to the computing time, we also conducted assessments of PPDC under different factors. Firstly, the value of \(q\) has an effect on the computing time. Figure 10 shows the variation trend of computing time of PPDC with different values of \(q\). As the \(q\) is bigger, the corresponding time is much more and the difference caused between contiguous different \(q\) rises when the size of dataset increases. Therefore, an appropriate value of \(q\) is needed. Next, we evaluate the computing time spent by each step in PPDC.