›› 2017, Vol. 32 ›› Issue (5): 1008-1024.doi: 10.1007/s11390-017-1778-z

Special Issue: Data Management and Data Mining

• Regular Paper • 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. 1 College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China;
    2 College of Computer, Electronics and Information, Guangxi University, Nanning 530004, China
  • Received:2016-05-09 Revised:2017-01-22 Online:2017-09-05 Published:2017-09-05
  • Contact: Ge Yu,yuge@cse.neu.edu.cn E-mail: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.
  • Supported by:

    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.

PDF

874

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.

[1] Poel D V, Buckinx W. Predicting online-purchasing behaviour. European Journal of Operational Research, 2005, 166(2):557-575.

[2] Wang J, Song S, Zhu X, Lin X. Efficient recovery of missing events. Proceedings of the VLDB Endowment, 2013, 6(10):841-852.

[3] Jeung H, Yiu M L, Zhou X, Jensen C S. Path prediction and predictive range querying in road network databases. The International Journal on Very Large Data Bases, 2010, 19(4):585-602.

[4] Song R, Sun W, Zheng B, Zheng Y. Press:A novel framework of trajectory compression in road networks. Proceedings of the VLDB Endowment, 2014, 7(9):661-672.

[5] Liu C, White R W, Dumais S T. Understanding web browsing behaviors through Weibull analysis of dwell time. In Proc. the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, July 2010, pp.379-386.

[6] Dwork C, McSherry F, Nissim K, Smith A. Calibrating noise to sensitivity in private data analysis. In Proc. the 3rd Conference on Theory of Cryptography, March 2006, pp.265-284.

[7] Götz M, Nath S, Gehrke J. Maskit:Privately releasing user context streams for personalized mobile applications. In Proc. the 2012 ACM SIGMOD International Conference on Management of Data, May 2012, pp.289-300.

[8] He Y, Barman S, Wang D, Naughton J F. On the complexity of privacy-preserving complex event processing. In Proc. the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June 2011, pp.165-174.

[9] Wang D, He Y, Rundensteiner E A, Naughton J F. Utilitymaximizing event stream suppression. In Proc. the 2013 ACM SIGMOD International Conference on Management of Data, June 2013, pp.589-600.

[10] Rastogi V, Nath S. Differentially private aggregation of distributed time-series with transformation and encryption. In Proc. the 2010 ACM SIGMOD International Conference on Management of Data, June 2010, pp.735-746.

[11] Chen R, Ács G, Castelluccia C. Differentially private se-quential data publication via variable-length n-grams. In Proc. the 2012 ACM conference on Computer and Communications Security, October 2012, pp.638-649.

[12] Zeng C, Naughton J F, Cai J. On differentially private frequent itemset mining. Proceedings of the VLDB Endowment, 2012, 6(1):25-36.

[13] Hay M, Rastogi V, Miklau G, Suciu D. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment, 2010, 3(1):1021-1032.

[14] Qardaji W H, Yang W, Li N. Understanding hierarchical methods for differentially private histograms. Proceedings of the VLDB Endowment, 2013, 6(14):1954-1965.

[15] Li H G, Chen S, Tatemura J, Agrawal D, Candan K S, Hsiung W P. Safety guarantee of continuous join queries over punctuated data streams. In Proc. the 32nd International Conference on Very Large Data Bases, September 2006, pp.19-30.

[16] Maheshwari P, Tam S S L. Events-based exception handling in supply chain management using Web services. In Proc. the Advanced Int. Conference on Telecommunications and Int. Conference on Internet and Web Applications and Services, February 2006, pp.151-156.

[17] Roh G P, Roh J W, Hwang S, Yi B K. Supporting patternmatching queries over trajectories on road networks. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(11):1753-1758.

[18] Maruseac M, Ghinita G, Rughinis R. Privacy-preserving publication of provenance workflows. In Proc. the 4th ACM Conference on Data and Application Security and Privacy, February 2014, pp.159-162.

[19] Chen R, Fung B C M, Desai B C, Sossou N M. Differentially private transit data publication:A case study on the Montreal transportation system. In Proc. the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2012, pp.213-221.

[20] McSherry F, Mahajan R. Differentially-private network trace analysis. In Proc. the ACM SIGCOMM 2010 Conference, August 2010, pp.123-134.

[21] He X, Cormode G, Machanavajjhala A, Procopiuc C M, Srivastava D. DPT:Differentially private trajectory synthesis using hierarchical reference systems. Proceedings of the VLDB Endowment, 2015, 8(11):1154-1165.

[22] Kellaris G, Papadopoulos S. Practical differential privacy via grouping and smoothing. Proceedings of the VLDB Endowment, 2013, 6(5):301-312.

[23] Yuan G, Zhang Z, Winslett M, Xiao X, Yang Y, Hao Z. Lowrank mechanism:Optimizing batch queries under differential privacy. Proceedings of the VLDB Endowment, 2012, 5(11):1352-1363.

[24] Li C, Miklau G. An adaptive mechanism for accurate query answering under differential privacy. Proceedings of the VLDB Endowment, 2012, 5(6):514-525.

[25] Li C, Hay M, Miklau G, Wang Y. A data-and workloadaware query answering algorithm for range queries under differential privacy. Proceedings of the VLDB Endowment, 2014, 7(5):341-352.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved