Top-κ closed co-occurrence patterns mining with differential privacy over multiple streams

摘要

The frequent pattern mining over data streams is a very important problem for many applications. However, many researches investigate a single stream in which every transaction is independent and it is not considered that some transactions are generated by the same individual. Some real-world applications involve multiple streams that continuously generate objects, and interesting observations are the objects appearing in many streams, such as emerging topic discovery, e-commerce, web usage pattern mining and location-based services. In this paper, we analyze the privacy problems in mining top-κ closed co-occurrence patterns over multiple streams caused by single release of a window and continuous releases in successive windows. To prevent privacy leakage, we propose a differentially private top-κclosed co-occurrence patterns mining algorithm across multiple streams with exponential mechanism and Laplace mechanism. The algorithm consists of dissimilarity calculation phase and differentially private mining phase, where differentially private mining phase includes adjusting CP-Graph with splitting transaction, perturbing CP-Graph to obtain the top-κ closed co-occurrence patterns candidate set and adding noise to the supports of patterns. Finally, we prove our algorithm satisfies differential privacy and experiment results show the utility and efficiency of our algorithm.