? Differentially Private Event Histogram Publication on Sequences over Graphs
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
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 Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
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

Abstract
Reference
Related Articles
Download: [PDF 672KB]     Export: BibTeX or EndNote (RIS)  
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.
Articles by authors
Keywordsdifferential privacy   histogram publication   sequence   graph     
Received 2016-05-09;
Fund:

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.

Corresponding Authors: 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.
Cite this article:   
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
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1778-z
Copyright 2010 by Journal of Computer Science and Technology