Differentially Private Event Histogram Publication on Sequences over Graphs

Differentially Private Event Histogram Publication

on Sequences over Graphs

Ning Wang;Yu Gu;Jia Xu;Fang-Fang Li;Ge Yu

【期刊名称】《计算机科学技术学报（英文版）》 【年(卷),期】2017(032)005

【摘要】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) has been 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. Directly publishing the statistics of sequences 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 a group of event pivots, 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. 【总页数】17页(1008-1024) 【关键词】

【作者】Ning Wang;Yu Gu;Jia Xu;Fang-Fang Li;Ge Yu

【作者单位】College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China;College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China 【正文语种】英文 【中图分类】 【文献来源】

https://www.zhangqiaokeyan.com/academic-journal-cn_journal-

computer-science-technology_thesis/0201241194693.html 【相关文献】

1.Higher-order differential variational principle and differential equations of motion for mechanical systems in event space [J], Zhang Xiang-Wu; LiYuan-Yuan; Zhao Xiao-Xia; Luo Wen-Feng

2.OBSERVABILITY OF EXTENDED TIMED EVENT GRAPH [J], ZHUO Zhibing; CHEN Wende 3.INTEGRATED

APPROACH

TO

GENERATION

OF

PRECEDENCE

RELATIONS AND PRECEDENCE GRAPHS FOR ASSEMBLY SEQUENCE PLANNING [J],

4.Disassembly sequence planning using component-joint graph and ant colony optimization [J], Zheng Menglei; Tian Ling; Liu Beibei

5.A novel configuration model for random graphs with given degree sequence [J], Xu Xin-Ping; Liu Feng

以上内容为文献基本信息，获取文献全文请下载