? 面向满足图约束关系的序列数据的差分隐私直方图发布
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (5) :1008-1024    DOI: 10.1007/s11390-017-1778-z
Regular Paper << Previous Articles | Next Articles >>
面向满足图约束关系的序列数据的差分隐私直方图发布
Ning Wang1, Student Member, CCF, Yu Gu1, Senior Member, CCF, Jia Xu2, Member, CCF, Fang-Fang Li1, Member, CCF, Ge Yu1,*, Fellow, CCF, Member, ACM, IEEE
1 College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;
2 College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China
Differentially Private Event Histogram Publication on Sequences over Graphs
Ning Wang1, Student Member, CCF, Yu Gu1, Senior Member, CCF, Jia Xu2, Member, CCF, Fang-Fang Li1, Member, CCF, Ge Yu1,*, Fellow, CCF, Member, ACM, IEEE
1 College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;
2 College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China

摘要
参考文献
相关文章
Download: [PDF 672KB]  
摘要 大数据时代的到来导致日益增长的分析虚拟世界中私人信息和足迹的需求。为了保护分析过程中隐私信息不被泄露,作为第一个具有理论保证的隐私保护模型,差分隐私技术被提出。本文将图中每一条边看做一个事件,针对事件序列数据库,发布差分隐私事件直方图。这样的事件序列广泛存在于工业生产中的工作流,在线的游戏日志和时空轨迹数据中。直接发布事件直方图会造成私人隐私信息泄露。而当前存在的差分隐私方面的工作主要致力于解决具有全序特征的数据的发布。由于序列数据可以遵循图上的任意路径,本文的问题面临着新的挑战。三步框架被采用来解决事件直方图发布问题,具体地1)本文权衡噪音误差与截断误差之间的关系,提出差分隐私的方法来截断数据库中的原始序列。2)本文基于查询负载,将图分解成路径。3)针对每一个分解得到的路径,为了降低噪音规模,深度优化的树结构被采用来发布路径上事件对应的直方图。在以上三个步骤中,本文对理论误差进行分析,分别提出了优化策略。除此之外,实验验证了相比于当前最优的方法,三步框架方法在精确度方面有很大提高。
关键词差分隐私   直方图发布   序列        
Abstract: The big data era is coming with strong and ever-growing demands on analyzing personal information and footprints in the cyber world. To enable such analysis without privacy leak risk, differential privacy (DP) is quickly rising in recent years, as the first practical privacy protection model with rigorous theoretical guarantee. This paper discusses how to publish differentially private histograms on events in time series domain, with sequences of personal events over graphs with events as edges. Such individual-generated sequences commonly appear in formalized industrial workflows, online game logs and spatial-temporal trajectories, the direct publication of which may compromise personal privacy. While existing DP mechanisms mainly target at normalized domains with fixed and aligned dimensions, our problem raises new challenges when the sequences could follow arbitrary paths on the graph. To tackle the problem, we reformulate the problem with a three-step framework, which 1) carefully truncates the original sequences, trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy, 2) decomposes the event graph into path sub-domains based on the given query workload, and 3) employs a deeply optimized tree-based histogram construction approach for each sub-domain to benefit with less noise addition. We present a careful analysis on our framework to support thorough optimizations over each step of the framework, and verify the huge improvements of our proposals over state-of-the-art solutions.
Keywordsdifferential privacy   histogram publication   sequence   graph     
Received 2016-05-09;
本文基金:

This work was supported by the National Natural Science Foundation of China under Grant Nos. 61472071 and 61272179, the Fundamental Research Funds for Central Universities of China under Grant No. 161604005, and the National Basic Research 973 Program of China under Grant No. 2012CB316201.

通讯作者: Ge Yu,yuge@cse.neu.edu.cn     Email: yuge@cse.neu.edu.cn
About author: Ning Wang is a Ph.D. candidate in computer software and theory, Northeastern University, Shenyang. She received her B.E. and M.E. degrees in computer science both from Northeastern University, Shenyang, in 2011 and 2013 respectively. Her current area of research is data privacy.
引用本文:   
Ning Wang, Yu Gu, Jia Xu, Fang-Fang Li, Ge Yu.面向满足图约束关系的序列数据的差分隐私直方图发布[J]  Journal of Computer Science and Technology , 2017,V32(5): 1008-1024
Ning Wang, Yu Gu, Jia Xu, Fang-Fang Li, Ge Yu.Differentially Private Event Histogram Publication on Sequences over Graphs[J]  Journal of Computer Science and Technology, 2017,V32(5): 1008-1024
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1778-z
Copyright 2010 by Journal of Computer Science and Technology