August  2018, 1(3): 295-309. doi: 10.3934/mfc.2018014

A real-time aggregate data publishing scheme with adaptive ω-event differential privacy

1. 

School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing, China

2. 

School of Big Data & Software Engineering, Chongqing University, Chongqing, China

* Corresponding author: Yan Huo

Received  November 2017 Revised  February 2018 Published  July 2018

Fund Project: The first and second authors are supported by NSFC grants (No. 61471028) and the Fundamental Research Funds for the Central Universities (No. 2017JBM004).
The third author is supported by NSFC grants (No. 61702062).
The fourth author is supported by NSFC grants (No. 61571010).

Although massive real-time data collected from users can provide benefits to improve the quality of human daily lives, it is possible to expose users' privacy. $\epsilon$-differential privacy is a notable model to provide strong privacy preserving in statistics. The existing works highlight $ω$-event differential privacy with a fixed window size, which may not be suitable for many practical scenarios. In view of this issue, we explore a real-time scheme with adaptive $ω$-event for differentially private time-series publishing (ADP) in this paper. In specific, we define a novel notion, Quality of Privacy (QoP) to measure both the utility of the released statistics and the performance of privacy preserving. According to this, we present an adaptive $ω$-event differential privacy model that can provide privacy protection with higher accuracy and better privacy protection effect. In addition, we also design a smart grouping mechanism to improve the grouping performance, and then improve the availability of publishing statistics. Finally, comparing with the existing schemes, we exploit real-world and synthetic datasets to conduct several experiments to demonstrate the superior performance of the ADP scheme.

Citation: Chengtao Yong, Yan Huo, Chunqiang Hu, Yanfei Lu, Guanlin Jing. A real-time aggregate data publishing scheme with adaptive ω-event differential privacy. Mathematical Foundations of Computing, 2018, 1 (3) : 295-309. doi: 10.3934/mfc.2018014
References:
[1]

Administration, United States Federal Highway, Traffic monitoring guide, Evaluation, (2001). Google Scholar

[2]

K. AleksandraK. KrishnaramM. Nina and N. Alexandros, Releasing search queries and clicks privately, International Conference on World Wide Web, (2009), 171-180.   Google Scholar

[3]

J. Ankur, Adaptive stream resource management using Kalman Filters, ACM SIGMOD International Conference on Management of Data, (2004), 11-22.   Google Scholar

[4]

A. Blum, K. Ligett and A. Roth, A learning theory approach to non-interactive database privacy, Journal of the ACM, 60 (2008), Art. 12, 25 pp. doi: 10.1145/2450142.2450148.  Google Scholar

[5]

C. A. BradleyD. Rolka and J. Loonsk, BioSense: Implementation of a national early event detection and situational awareness system, Mmwr Supplements, 54 (2005), 11pp.   Google Scholar

[6]

Z. CaiZ. HeX. Guan and Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Transactions on Dependable and Secure Computing, PP (2016), 1-1.  doi: 10.1109/TDSC.2016.2613521.  Google Scholar

[7]

J. CaoQ. XiaoG. GhinitaN. LiE. Bertino and T. Kian Lee, Efficient and accurate strategies for differentially-private sliding window queries, International Conference on Extending Database Technology, (2013), 191-202.   Google Scholar

[8]

R. ChenN. MohammedB. C. M. FungB. C. Desai and X. Li, Publishing setvalued data via differential privacy, Vldb, 4 (2012), 1087-1098.   Google Scholar

[9]

S. ChengZ. CaiJ. Li and H. Gao, Extracting kernel dataset from big sensory data in wireless sensor networks, IEEE Transactions on Knowledge and Data Engineering, 29 (2017), 813-827.  doi: 10.1109/TKDE.2016.2645212.  Google Scholar

[10]

S. ChengZ. Cai and J. Li, Curve query processing in wireless sensor networks, IEEE Transactions on Vehicular Technology, 64 (2015), 5198-5209.  doi: 10.1109/TVT.2014.2375330.  Google Scholar

[11]

S. ChengZ. CaiJ. Li and X. Fang, Drawing dominant dataset from big sensory data in wireless sensor networks, The 34th Annual IEEE International Conference on Computer Communications (INFOCOM 2015), (2015), 531-539.  doi: 10.1109/INFOCOM.2015.7218420.  Google Scholar

[12]

D. Cynthia, Differential privacy, International Colloquium on Automata, Languages, and Programming, 4052 (2006), 1-12.  doi: 10.1007/11787006_1.  Google Scholar

[13]

D. Cynthia, Differential privacy in new settings, Acm-Siam Symposium on Discrete Algorithms, (2010), 174-183.   Google Scholar

[14]

C. DworkM. NaorT. Pitassiand and G. N. Rothblum, Differential privacy under continual observation, STOC '10 Proceedings of the Forty-Second ACM Symposium on Theory of Computing, (2010), 715-724.  doi: 10.1145/1806689.1806787.  Google Scholar

[15]

C. DworkM. NaorO. ReingoldG. N. Rothblum and S. Vadhan, On the complexity of differentially private data release: Efficient algorithms and hardness results, Proc. 41st Annu. ACM STOC, (2009), 381-390.   Google Scholar

[16]

C. DworkF. McSherryK. Nissim and A. Smith, Calibrating noise to sensitivity in private data analysis, Theory of Cryptography, 3876 (2006), 265-284.  doi: 10.1007/11681878_14.  Google Scholar

[17]

L. Fan and L. Xiong, An adaptive approach to real-time aggregate monitoring with differential privacy, IEEE Transactions on Knowledge and Data Engineering, 26 (2014), 2094-2106.   Google Scholar

[18]

T. Florian, Privacy issues in vehicular ad hoc networks, International Conference on Privacy Enhancing Technologies, (2005), 197-209.   Google Scholar

[19]

B. J. Frey and D. Dueck, Clustering by passing messages between data points, Science, 315 (2007), 972-976.  doi: 10.1126/science.1136800.  Google Scholar

[20]

C. GrahamP. CeciliaS. Divesh and T. T. L. Tran, Differentially private summaries for sparse data, International Conference on Database Theory, (2011), 299-311.   Google Scholar

[21]

Z. HeZ. Cai and J. Yu, Latent-data Privacy Preserving with Customized Data Utility for Social Network Data, IEEE Transactions on Vehicular Technology, 67 (2018), 665-673.  doi: 10.1109/TVT.2017.2738018.  Google Scholar

[22]

Z. HeZ. CaiS. Cheng and X. Wang, Approximate aggregation for tracking quantiles and range countings in wireless sensor networks, Theoretical Computer Science, 607 (2015), 381-390.  doi: 10.1016/j.tcs.2015.07.056.  Google Scholar

[23]

Th. H. Chan, E. Shi and D. Song, Private and continual release of statistics, Automata, Languages and Programming, Part Ⅱ, 405-417, Lecture Notes in Comput. Sci., 6199, Springer, Berlin, 2010. doi: 10.1007/978-3-642-14162-1_34.  Google Scholar

[24]

T. H. Hubert ChanM. LiE. Shi and W. Xu, Differentially private continual monitoring of heavy hitters from distributed streams, Springer Berlin Heidelberg, (2012), 140-159.   Google Scholar

[25]

R. Kalman, A new approach to linear filtering and prediction problem, Journal of Basic Engineering, 82 (1960), 35-45.  doi: 10.1115/1.3662552.  Google Scholar

[26]

G. KellarisS. PapadopoulosX. Xiao and D. Papadias, Differentially private event sequences over infinite streams, Proc. of the VLDB Endowment, 7 (2014), 1155-1166.  doi: 10.14778/2732977.2732989.  Google Scholar

[27]

D. Kifer and B.-R. Lin, Towards an axiomatization of statistical privacy and utility, Proc. of ACM PODS, (2010), 147-158.  doi: 10.1145/1807085.1807106.  Google Scholar

[28]

C. LiM. HayV. RastogiG. Miklau and A. Mcgregor, Optimizing linear counting queries under differential privacy, Twenty-Ninth ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems, (2010), 123-134.   Google Scholar

[29]

J. Li, S. Cheng, Z. Cai, J. Yu, C. Wang and Y. Li, Approximate holistic aggregation in wireless sensor networks, 2015 IEEE 35th International Conference on Distributed Computing Systems, (2015). doi: 10.1109/ICDCS.2015.86.  Google Scholar

[30]

Y. Liang and Z. Cai and Q. Han and Y. Li, Location privacy leakage through sensory data, Security and Communication Networks, (2017), Article ID 7576307, 12 pages. doi: 10.1155/2017/7576307.  Google Scholar

[31]

J. Mao, W. Tian, Y. Zhang, J. Cui, H. Ma, J. Bian, J. Liu and J. Zhang, Co-Check: Collab-orative outsourced data auditing in multicloud environment, Security and Communication Networks, (2017), Article ID 2948025, 13 pages doi: 10.1155/2017/2948025.  Google Scholar

[32]

J. MaoY. ZhangP. LiT. LiQ. Wu and J. Liu, A Position-aware Merkle Tree for Dynamic Cloud Data Integrity Verification, Soft Computing, 21 (2017), 2151-2164.  doi: 10.1007/s00500-015-1918-8.  Google Scholar

[33]

H. MichaelR. VibhorM. Gerome and D. Suciu, Boosting the accuracy of differentially private histograms through consistency, Proceedings of the Vldb Endowment, 3 (2010), 1021-1032.   Google Scholar

[34]

J. SunY. Fang and X. Zhu, Privacy and emergency response in e-healthcare leveraging wireless body sensor networks, IEEE Wireless Communications, 17 (2010), 66-73.  doi: 10.1109/MWC.2010.5416352.  Google Scholar

[35]

B. Thomas, A framework for generating network-based moving objects, Geoinformatica, 6 (2002), 153-180.   Google Scholar

[36]

Q. Wang, Y. Zhang, X. Lu and Z. Wang, RescueDP: Real-time spatio-temporal crowdsourced data publishing with differential privacy, IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, (2016). doi: 10.1109/INFOCOM.2016.7524458.  Google Scholar

[37]

X. XiaoG. BenderH. Michael and G. Johannes, iReduct: differential privacy with reduced relative errors, ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June, (2011), 229-240.   Google Scholar

[38]

J. XuZ. ZhangX. XiaoY. Yang and G. Yu, Differentially private histogram publication, IEEE International Conference on Data Engineering, (2012), 32-43.   Google Scholar

[39]

L. ZhangZ. Cai and X. Wang, FakeMask: A Novel Privacy Preserving Approach for Smartphones, IEEE Transactions on Network and Service Management, 13 (2016), 335-348.  doi: 10.1109/TNSM.2016.2559448.  Google Scholar

[40]

X. ZhengZ. CaiJ. YuC. Wang and Y. Li, Follow but no track: Privacy preserved profile publishing in cyber-physical social systems, IEEE Internet of Things Journal, 4 (2017), 1868-1878.  doi: 10.1109/JIOT.2017.2679483.  Google Scholar

[41]

CTR Data, Available from: https://www.kaggle.com/c/avazu-ctr-prediction. Google Scholar

[42]

Capital Bikeshare Data, Available from: https://www.capitalbikeshare.com/system-data. Google Scholar

show all references

References:
[1]

Administration, United States Federal Highway, Traffic monitoring guide, Evaluation, (2001). Google Scholar

[2]

K. AleksandraK. KrishnaramM. Nina and N. Alexandros, Releasing search queries and clicks privately, International Conference on World Wide Web, (2009), 171-180.   Google Scholar

[3]

J. Ankur, Adaptive stream resource management using Kalman Filters, ACM SIGMOD International Conference on Management of Data, (2004), 11-22.   Google Scholar

[4]

A. Blum, K. Ligett and A. Roth, A learning theory approach to non-interactive database privacy, Journal of the ACM, 60 (2008), Art. 12, 25 pp. doi: 10.1145/2450142.2450148.  Google Scholar

[5]

C. A. BradleyD. Rolka and J. Loonsk, BioSense: Implementation of a national early event detection and situational awareness system, Mmwr Supplements, 54 (2005), 11pp.   Google Scholar

[6]

Z. CaiZ. HeX. Guan and Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Transactions on Dependable and Secure Computing, PP (2016), 1-1.  doi: 10.1109/TDSC.2016.2613521.  Google Scholar

[7]

J. CaoQ. XiaoG. GhinitaN. LiE. Bertino and T. Kian Lee, Efficient and accurate strategies for differentially-private sliding window queries, International Conference on Extending Database Technology, (2013), 191-202.   Google Scholar

[8]

R. ChenN. MohammedB. C. M. FungB. C. Desai and X. Li, Publishing setvalued data via differential privacy, Vldb, 4 (2012), 1087-1098.   Google Scholar

[9]

S. ChengZ. CaiJ. Li and H. Gao, Extracting kernel dataset from big sensory data in wireless sensor networks, IEEE Transactions on Knowledge and Data Engineering, 29 (2017), 813-827.  doi: 10.1109/TKDE.2016.2645212.  Google Scholar

[10]

S. ChengZ. Cai and J. Li, Curve query processing in wireless sensor networks, IEEE Transactions on Vehicular Technology, 64 (2015), 5198-5209.  doi: 10.1109/TVT.2014.2375330.  Google Scholar

[11]

S. ChengZ. CaiJ. Li and X. Fang, Drawing dominant dataset from big sensory data in wireless sensor networks, The 34th Annual IEEE International Conference on Computer Communications (INFOCOM 2015), (2015), 531-539.  doi: 10.1109/INFOCOM.2015.7218420.  Google Scholar

[12]

D. Cynthia, Differential privacy, International Colloquium on Automata, Languages, and Programming, 4052 (2006), 1-12.  doi: 10.1007/11787006_1.  Google Scholar

[13]

D. Cynthia, Differential privacy in new settings, Acm-Siam Symposium on Discrete Algorithms, (2010), 174-183.   Google Scholar

[14]

C. DworkM. NaorT. Pitassiand and G. N. Rothblum, Differential privacy under continual observation, STOC '10 Proceedings of the Forty-Second ACM Symposium on Theory of Computing, (2010), 715-724.  doi: 10.1145/1806689.1806787.  Google Scholar

[15]

C. DworkM. NaorO. ReingoldG. N. Rothblum and S. Vadhan, On the complexity of differentially private data release: Efficient algorithms and hardness results, Proc. 41st Annu. ACM STOC, (2009), 381-390.   Google Scholar

[16]

C. DworkF. McSherryK. Nissim and A. Smith, Calibrating noise to sensitivity in private data analysis, Theory of Cryptography, 3876 (2006), 265-284.  doi: 10.1007/11681878_14.  Google Scholar

[17]

L. Fan and L. Xiong, An adaptive approach to real-time aggregate monitoring with differential privacy, IEEE Transactions on Knowledge and Data Engineering, 26 (2014), 2094-2106.   Google Scholar

[18]

T. Florian, Privacy issues in vehicular ad hoc networks, International Conference on Privacy Enhancing Technologies, (2005), 197-209.   Google Scholar

[19]

B. J. Frey and D. Dueck, Clustering by passing messages between data points, Science, 315 (2007), 972-976.  doi: 10.1126/science.1136800.  Google Scholar

[20]

C. GrahamP. CeciliaS. Divesh and T. T. L. Tran, Differentially private summaries for sparse data, International Conference on Database Theory, (2011), 299-311.   Google Scholar

[21]

Z. HeZ. Cai and J. Yu, Latent-data Privacy Preserving with Customized Data Utility for Social Network Data, IEEE Transactions on Vehicular Technology, 67 (2018), 665-673.  doi: 10.1109/TVT.2017.2738018.  Google Scholar

[22]

Z. HeZ. CaiS. Cheng and X. Wang, Approximate aggregation for tracking quantiles and range countings in wireless sensor networks, Theoretical Computer Science, 607 (2015), 381-390.  doi: 10.1016/j.tcs.2015.07.056.  Google Scholar

[23]

Th. H. Chan, E. Shi and D. Song, Private and continual release of statistics, Automata, Languages and Programming, Part Ⅱ, 405-417, Lecture Notes in Comput. Sci., 6199, Springer, Berlin, 2010. doi: 10.1007/978-3-642-14162-1_34.  Google Scholar

[24]

T. H. Hubert ChanM. LiE. Shi and W. Xu, Differentially private continual monitoring of heavy hitters from distributed streams, Springer Berlin Heidelberg, (2012), 140-159.   Google Scholar

[25]

R. Kalman, A new approach to linear filtering and prediction problem, Journal of Basic Engineering, 82 (1960), 35-45.  doi: 10.1115/1.3662552.  Google Scholar

[26]

G. KellarisS. PapadopoulosX. Xiao and D. Papadias, Differentially private event sequences over infinite streams, Proc. of the VLDB Endowment, 7 (2014), 1155-1166.  doi: 10.14778/2732977.2732989.  Google Scholar

[27]

D. Kifer and B.-R. Lin, Towards an axiomatization of statistical privacy and utility, Proc. of ACM PODS, (2010), 147-158.  doi: 10.1145/1807085.1807106.  Google Scholar

[28]

C. LiM. HayV. RastogiG. Miklau and A. Mcgregor, Optimizing linear counting queries under differential privacy, Twenty-Ninth ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems, (2010), 123-134.   Google Scholar

[29]

J. Li, S. Cheng, Z. Cai, J. Yu, C. Wang and Y. Li, Approximate holistic aggregation in wireless sensor networks, 2015 IEEE 35th International Conference on Distributed Computing Systems, (2015). doi: 10.1109/ICDCS.2015.86.  Google Scholar

[30]

Y. Liang and Z. Cai and Q. Han and Y. Li, Location privacy leakage through sensory data, Security and Communication Networks, (2017), Article ID 7576307, 12 pages. doi: 10.1155/2017/7576307.  Google Scholar

[31]

J. Mao, W. Tian, Y. Zhang, J. Cui, H. Ma, J. Bian, J. Liu and J. Zhang, Co-Check: Collab-orative outsourced data auditing in multicloud environment, Security and Communication Networks, (2017), Article ID 2948025, 13 pages doi: 10.1155/2017/2948025.  Google Scholar

[32]

J. MaoY. ZhangP. LiT. LiQ. Wu and J. Liu, A Position-aware Merkle Tree for Dynamic Cloud Data Integrity Verification, Soft Computing, 21 (2017), 2151-2164.  doi: 10.1007/s00500-015-1918-8.  Google Scholar

[33]

H. MichaelR. VibhorM. Gerome and D. Suciu, Boosting the accuracy of differentially private histograms through consistency, Proceedings of the Vldb Endowment, 3 (2010), 1021-1032.   Google Scholar

[34]

J. SunY. Fang and X. Zhu, Privacy and emergency response in e-healthcare leveraging wireless body sensor networks, IEEE Wireless Communications, 17 (2010), 66-73.  doi: 10.1109/MWC.2010.5416352.  Google Scholar

[35]

B. Thomas, A framework for generating network-based moving objects, Geoinformatica, 6 (2002), 153-180.   Google Scholar

[36]

Q. Wang, Y. Zhang, X. Lu and Z. Wang, RescueDP: Real-time spatio-temporal crowdsourced data publishing with differential privacy, IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, (2016). doi: 10.1109/INFOCOM.2016.7524458.  Google Scholar

[37]

X. XiaoG. BenderH. Michael and G. Johannes, iReduct: differential privacy with reduced relative errors, ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June, (2011), 229-240.   Google Scholar

[38]

J. XuZ. ZhangX. XiaoY. Yang and G. Yu, Differentially private histogram publication, IEEE International Conference on Data Engineering, (2012), 32-43.   Google Scholar

[39]

L. ZhangZ. Cai and X. Wang, FakeMask: A Novel Privacy Preserving Approach for Smartphones, IEEE Transactions on Network and Service Management, 13 (2016), 335-348.  doi: 10.1109/TNSM.2016.2559448.  Google Scholar

[40]

X. ZhengZ. CaiJ. YuC. Wang and Y. Li, Follow but no track: Privacy preserved profile publishing in cyber-physical social systems, IEEE Internet of Things Journal, 4 (2017), 1868-1878.  doi: 10.1109/JIOT.2017.2679483.  Google Scholar

[41]

CTR Data, Available from: https://www.kaggle.com/c/avazu-ctr-prediction. Google Scholar

[42]

Capital Bikeshare Data, Available from: https://www.capitalbikeshare.com/system-data. Google Scholar

Figure 1.  The aggregate time-series data publishing scenario
Figure 2.  A high-level overview of ADP
Figure 3.  Utility comparison when $\epsilon$ changes
Figure 4.  Utility comparison with and without Adaptive $\omega$
Figure 5.  MAE and QoP of different grouping mechanisms
[1]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[3]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[4]

Hai-Feng Huo, Shi-Ke Hu, Hong Xiang. Traveling wave solution for a diffusion SEIR epidemic model with self-protection and treatment. Electronic Research Archive, , () : -. doi: 10.3934/era.2020118

[5]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[6]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020050

[7]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[8]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[9]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

[10]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

 Impact Factor: 

Metrics

  • PDF downloads (113)
  • HTML views (1752)
  • Cited by (0)

[Back to Top]