A three-phase approach to differentially private crucial patterns mining over data streams

摘要

Frequent patterns mining over transactional data streams is an important task for a wide range of online data mining applications. Nevertheless, mining crucial patterns is even more appropriate than frequent patterns over transactional data streams, because crucial patterns are the subset of frequent patterns with the minimum storage cost and information lossless extraction. In this paper, we argue that the privacy of mining crucial patterns from data streams (i.e., aggregating information from individuals) is more likely to be leaked than static scenarios, due to successive releases. However, to the best of our knowledge, there is little work on differential privacy in continuously publishing crucial patterns from data streams. To this end, this paper proposes a real-time differentially private crucial pattern computation algorithm which designs a three-phase mechanism (i.e., the preprocessing phase, the deep-going calculation phase, and the noise-mining phase) at every timestamp. The algorithm is able to not only improve the utility of the crucial pattern statistics as much as possible which satisfy differential privacy, but also reduce the average mining time without incurring high maintenance cost according to the feature of crucial patterns. To reduce the number of calls to crucial pattern computation algorithm, we design two-dissimilarity formulas according to the relationship between frequent patterns and crucial patterns to decide to return either low noisy statistic or accurately approximated statistic in the first two phases. When the low noisy statistic needs to be turned, the algorithm goes into the noise-mining phase. To obtain private crucial patterns, we first filter crucial pattern candidate set by perturbing the scoring functions, and then add independent Laplace noise to their supports. Finally, we conduct extensive experiments on dense datasets and sparse datasets to show the effectiveness and efficiency of our algorithm. (C) 2018 Elsevier Ltd. All rights reserved.