A Differentially Private Scheme for Top-k Frequent Itemsets Mining Over Data Streams

Frequent Itemset Mining(FIM) is a popular technique for analyzing transactional data. Currently, continually mining frequent patterns over data streams have important application value. However, if these data are sensitive, directly releasing frequent patterns and their true supports may disclose the privacy of individuals. The protection of user privacy while obtaining statistical information is important. Differential privacy, as a rigid and provable privacy model, has recently gained significant attention in frequent itemset mining. Several differentially private schemes for FIM have been proposed. However, most of them are designed for static datasets and focus on privacy preservation for one-shot release of frequent patterns. In this paper, we focus on differentially private FIM over data streams, and aim to design a private continual release scheme which can not only achieve high data utility and a high degree of privacy, but also offer high time efficiency. Compared to the static release, the privacy preservation processing in FIM over data streams should meet the real-time requirement while achieving high data utility. Therefore, two challenges will be faced when designing the private scheme for FIM over data streams: the first is the cumulative consumption of privacy budget in the continual release process, which may result in low data utility. The second is the enlargement of candidate itemsets, which may cause a high error of the released result and low release efficiency. Some strategies need to be designed to solve the two challenges to promote the data utility and release efficiency. To solve the first challenge, a strategy of event level privacy for FIM over data streams is designed. Benefitting from this strategy, the utilization of the privacy budget for the continual release can be maximized, and thus the data utility can be improved. To solve the second challenge, an efficient transaction splitting method based on count estimation under differential privacy is first proposed in the preprocessing stage. Since splitting may cause a certain amount of information loss, the information loss is then analyzed and compensated in the publishing stage. Benefitting from transaction splitting, both the candidate itemsets and the information loss can be reduced, and thus the error of the released result can also be significantly reduced. Then in the continually publishing stage, when mining based on Cantree, the generated candidate patterns are compressed based on the support threshold to further reduce the error of the released result. Only the patterns whose support is smaller than the threshold can be retained in the sampling set. Based on the reduced sampling set, an incremental update release scheme is designed by combining weighted reservoir sampling with exponential mechanism (EM). The advantage of this combination is the sampling set can be traversed only once when finding the top-k frequent patterns, which can promote the release efficiency while not affecting the privacy level and data utility. By formal privacy analysis, we theoretically show that our scheme is ε-differentially private. Finally, extensive experiments on real-world datasets illustrate that our scheme outperforms the state-of-the-art comparison methods. © 2021, Science Press. All right reserved.