Crucial Patterns Mining with Differential Privacy over Data Streams
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61502111, 61763003, 61672176, 61762016, 61562007); Guangxi Natural Science Foundation (2016GXNSFAA380192); Guangxi Special Project of Science and Technology Base and Talents (AD16380008); Guangxi 1000-Plan of Training Middle-aged/Young Teachers in Higher Education Institutions; Guangxi "Bagui Scholar" Teams for Innovation and Research Project; Guangxi Collaborative Innovation Center of Multisource Information Integration and Intelligent Processing

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Frequent patterns mining is an important task for data mining. Nevertheless, mining concise crucial patterns is more promising than frequent patterns over data streams, since crucial patterns can avoid redundancy to reduce storage space and extract lossless information from frequent patterns. Nevertheless, mining crucial patterns from data streams which aggregate information from individuals is more likely to reveal privacy than static scenarios, because the background knowledge of the release at adjacent time instances can enhance the adversary's inferential ability. This study points out the problems and principles of privacy leakage over mining crucial patterns in data streams, and proposes a differentially private crucial patterns mining algorithm which designs a two-phase mechanism at every timestamp. Specifically, the two-phase mechanism includes the dissimilarity calculation phase and the noise-mining phase, which considers not only the tradeoff between privacy and utility but also the tradeoff between mining time and maintenance cost. To improve data utility over successive releases in streams, the dissimilarity is computed to decide to return either low noisy statistic or accurately approximated statistic in the first phase. When the low noisy statistic needs to be turned, the algorithm goes into the noise-mining phase. In the noise-mining phase, crucial pattern candidate set with a judgment query set is firstly identified, and then random noise drawn from the Laplace distribution to their supports are added to obtain the noisy supports. Finally, strict theoretical analysis and extensive experiments are provided to confirm the effectiveness and efficiency of our algorithm.

    Reference
    Related
    Cited by
Get Citation

王金艳,刘陈,傅星珵,罗旭东,李先贤.差分隐私的数据流关键模式挖掘方法.软件学报,2019,30(3):648-666

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 18,2018
  • Revised:September 20,2018
  • Adopted:
  • Online: March 06,2019
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063