AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (6.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Streaming Histogram Publication over Weighted Sliding Windows Under Differential Privacy

School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243032, China, and also with Institute for Artificial Intelligence, Hefei Comprehensive National Science Center, Hefei 230088, China
Baosight Software (Anhui) Co. Ltd., Ma’anshan 243000, China
School of Electrical Engineering and Computer Science, Washington State University, Pullman 99164, WA, USA
Show Author Information

Abstract

Continuously publishing histograms in data streams is crucial to many real-time applications, as it provides not only critical statistical information, but also reduces privacy leaking risk. As the importance of elements usually decreases over time in data streams, in this paper we model a data stream by a sequence of weighted sliding windows, and then study how to publish histograms over these windows continuously. The existing literature can hardly solve this problem in a real-time way, because they need to buffer all elements in each sliding window, resulting in high computational overhead and prohibitive storage burden. In this paper, we overcome this drawback by proposing an online algorithm denoted by Efficient Streaming Histogram Publishing (ESHP) to continuously publish histograms over weighted sliding windows. Specifically, our method first creates a novel sketching structure, called Approximate-Estimate Sketch (AESketch), to maintain the counting information of each histogram interval at every time instance; then, it creates histograms that satisfy the differential privacy requirement by smartly adding appropriate noise values into the sketching structure. Extensive experimental results and rigorous theoretical analysis demonstrate that the ESHP method can offer equivalent data utility with significantly lower computational overhead and storage costs when compared to other existing methods.

Keywords

differential privacyrandomized algorithmstreaming data publicationweighted sliding windowapproximate statisticsdata usabilitycomputational complexity

References

[1]

A. McAfee and E. Brynjolfsson, Big data: The management revolution, Harv. Bus. Rev., vol. 90, no. 10, pp. 60–68, 2012.
Google Scholar
[2]

X. Wang, Z. Liu, Y. Gao, X. Zheng, Z. Dang, and X. Shen, A near-optimal protocol for the grouping problem in RFID systems, IEEE Trans. Mobile Comput., vol. 20, no. 4, pp. 1257–1272, 2021.
Crossref Google Scholar
[3]

Z. Hu and D. Li, Improved heuristic job scheduling method to enhance throughput for big data analytics, Tsinghua Science and Technology, vol. 27, no. 2, pp. 344–357, 2022.
Crossref Google Scholar
[4]

R. Pan, Z. Li, J. Cao, H. Zhang, and X. Xia, Electrical load tracking scheduling of steel plants under time-of-use tariffs, Comput. Ind. Eng., vol. 137, p. 106049, 2019.
Crossref Google Scholar
[5]

A. Belhassena and H. Wang, Trajectory big data processing based on frequent activity, Tsinghua Science and Technology, vol. 24, no. 3, pp. 317–332, 2019.
Crossref Google Scholar
[6]

C. Zhan, H. Hu, Z. Liu, Z. Wang, and S. Mao, Multi-UAV-enabled mobile-edge computing for time-constrained IoT applications, IEEE Internet Things J., vol. 8, no. 20, pp. 15553–15567, 2021.
Crossref Google Scholar
[7]

D. Wei, H. Ning, F. Shi, Y. Wan, J. Xu, S. Yang, and L. Zhu, Dataflow management in the internet of things: Sensing, control, and security, Tsinghua Science and Technology, vol. 26, no. 6, pp. 918–930, 2021.
Crossref Google Scholar
[8]

I. Lee and K. Lee, The internet of things (IoT): Applications, investments, and challenges for enterprises, Bus. Horiz., vol. 58, no. 4, pp. 431–440, 2015.
Crossref Google Scholar
[9]

J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, Internet of things (IoT): A vision, architectural elements, and future directions, Future Gener. Comput. Syst., vol. 29, no. 7, pp. 1645–1660, 2013.
Crossref Google Scholar
[10]

M. A. Khan and K. Salah, IoT security: Review, blockchain solutions, and open challenges, Future Gener. Comput. Syst., vol. 82, pp. 395–411, 2018.
Crossref Google Scholar
[11]

Z. Liu, Q. Li, X. Chen, C. Wu, S. Ishihara, J. Li, and Y. Ji, Point cloud video streaming: Challenges and solutions, IEEE Netw., vol. 35, no. 5, pp. 202–209, 2021.
Crossref Google Scholar
[12]

Z. Liu, C. Zhan, Y. Cui, C. Wu, and H. Hu, Robust edge computing in UAV systems via scalable computing and cooperative computing, IEEE Wirel. Commun., vol. 28, no. 5, pp. 36–42, 2021.
Crossref Google Scholar
[13]

Z. Liu, J. Li, X. Chen, C. Wu, S. Ishihara, Y. Ji, and L. Li, Fuzzy logic-based adaptive point cloud video streaming, IEEE Open J. Comput. Soc., vol. 1, pp. 121–130, 2020.
Crossref Google Scholar
[14]
C. Xiang, W. Cheng, C. Lin, X. Zhang, D. Liu, X. Zheng, and Z. Li, LSTAloc: A driver-oriented incentive mechanism for mobility-on-demand vehicular crowdsensing market, IEEE Trans. Mobile Comput.
[15]

A. Cela, T. Jurik, R. Hamouche, R. Natowicz, A. Reama, S. I. Niculescu, and J. Julien, Energy optimal real-time navigation system, IEEE Intell. Transp. Syst. Mag., vol. 6, no. 3, pp. 66–79, 2014.
Crossref Google Scholar
[16]
H. Yi, H. Jung, and S. Bae, Deep neural networks for traffic flow prediction, in Proc. 2017 IEEE Int. Conf. Big Data and Smart Computing, Jeiu, Republic of Korea, 2017, pp. 328–331.
[17]

L. Zhao, K. Yang, Z. Tan, X. Li, S. Sharma, and Z. Liu, A novel cost optimization strategy for SDN-enabled UAV-assisted vehicular computation offloading, IEEE Trans. Intell. Transp. Syst., vol. 22, no. 6, pp. 3664–3674, 2020.
Crossref Google Scholar
[18]

C. Wu, Z. Liu, F. Liu, T. Yoshinaga, Y. Ji, and J. Li, Collaborative learning of communication routes in edge-enabled multi-access vehicular environment, IEEE Trans. Cognit. Commun. Netw., vol. 6, no. 4, pp. 1155–1165, 2020.
Crossref Google Scholar
[19]

B. Almadani, B. Saeed, and A. Alroubaiy, Healthcare systems integration using real time publish subscribe (RTPS) middleware, Comput. Electr. Eng., vol. 50, pp. 67–78, 2016.
Crossref Google Scholar
[20]
C. B. Rjeily, G. Badr, A. H. El Hassani, and E. Andres, Medical data mining for heart diseases and the future of sequential mining in medical field, in Machine Learning Paradigms, G. A. Tsihrintzis, D. N. Sotiropoulos, and L. C. Jain, eds. Cham, Switzerland: Springer, 2019, pp. 71–99.
Crossref
[21]
C. Xu, Y. Chen, and R. Bie, Sequential pattern mining in data streams using the weighted sliding window model, in Proc. 2009 15 th Int. Conf. Parallel and Distributed Systems, Shenzhen, China, 2009, pp. 886–890.
Crossref
[22]

P. S. M. Tsai, Mining frequent itemsets in data streams using the weighted sliding window model, Exp. Syst. Appl., vol. 36, no. 9, pp. 11617–11625, 2009.
Crossref Google Scholar
[23]

G. Lee, U. Yun, and K. H. Ryu, Sliding window based weighted maximal frequent pattern mining over data streams, Exp. Syst. Appl., vol. 41, no. 2, pp. 694–708, 2014.
Crossref Google Scholar
[24]

D. H. Vu, K. M. Muttaqi, A. P. Agalgaonkar, and A. Bouzerdoum, A multi-feature based approach incorporating variable thresholds for detecting price spikes in the national electricity market of Australia, IEEE Access, vol. 9, pp. 13960–13969, 2021.
Crossref Google Scholar
[25]
M. Yu, L. Wang, G. Xie, and T. Chu, Stabilization of networked control systems with data packet dropout via switched system approach, in Proc. 2004 IEEE Int. Conf. Robotics and Automation, Taipei, China, 2004, pp. 362–367.
[26]

J. Jiang, H. Wang, and W. Li, A trust model based on a time decay factor for use in social networks, Comput. Electr. Eng., vol. 85, p. 106706, 2020.
Crossref Google Scholar
[27]

F. Liu, T. Yang, J. Zhou, W. Deng, Q. Yu, P. Zhang, and G. Cheng, Spatial variability and time decay of rock mass mechanical parameters: A landslide study in the Dagushan open-pit mine, Rock Mech. Rock Eng., vol. 53, no. 7, pp. 3031–3053, 2020.
Crossref Google Scholar
[28]

A. Erramilli, O. Narayan, and W. Willinger, Experimental queueing analysis with long-range dependent packet traffic, IEEE/ACM Trans. Netw., vol. 4, no. 2, pp. 209–223, 1996.
Crossref Google Scholar
[29]

Y. Ren, Z. Zeng, T. Wang, S. Zhang, and G. Zhi, A trust-based minimum cost and quality aware data collection scheme in P2P network, Peer Peer Netw. Appl., vol. 13, no. 6, pp. 2300–2323, 2020.
Crossref Google Scholar
[30]
A. Golatkar, A. Achille, and S. Soatto, Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence, in Proc. 33 rd Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, pp. 10678–10688.
[31]

J. Xu, Z. Zhang, X. Xiao, Y. Yang, G. Yu, and M. Winslett, Differentially private histogram publication, VLDB J., vol. 22, no. 6, pp. 797–822, 2013.
Crossref Google Scholar
[32]

X. Zhang, C. Shao, and X. Meng, Accurate histogram release under differential privacy, (in Chinese), J. Comput. Res. Dev., vol. 53, no. 5, pp. 1106–1117, 2016.
Google Scholar
[33]

H. Tang, G. Yang, and Y. Bai, Histogram publishing algorithm based on adaptive privacy budget allocation strategy under differential privacy, (in Chinese), Appl. Res. Comput., vol. 37, no. 7, pp. 1952–1957&1963, 2020.
Google Scholar
[34]

D. Chen, Y. Li, J. Chen, H. Bi, and X. Ding, Differential privacy via Haar wavelet transform and Gaussian mechanism for range query, Comput. Intell. Neurosci., vol. 2022, pp. 8139813, 2022.
Crossref Google Scholar
[35]

S. Zhang and X. Li, Differential privacy medical data publishing method based on attribute correlation, Sci. Rep., vol. 12, no. 1, p. 15725, 2022.
Crossref Google Scholar
[36]

F. Lin, Y. Wu, Y. Wang, and L. Sun, Differentially private statistical publication for two-dimensional data stream, (in Chinese), J. Comput. Appl., vol. 35, no. 1, pp. 88–92, 2015.
Google Scholar
[37]

X. J. Zhang and X. F. Meng, Streaming histogram publication method with differential privacy, (in Chinese), J. Softw., vol. 27, no. 2, pp. 381–393, 2016.
Google Scholar
[38]
X. Wu, N. Tong, Z. Ye, and Y. Wang, Histogram publishing algorithm based on sampling sorting and greedy clustering, in Proc. 1 st Int. Conf. Blockchain and Trustworthy Systems, Guangzhou, China, 2020, pp. 81–91.
Crossref
[39]

L. Sun, C. Ge, X. Huang, Y. Wu, and Y. Gao, Differentially private real-time streaming data publication based on sliding window under exponential decay, Comput. Mater. Con., vol. 58, no. 1, pp. 61–78, 2019.
Crossref Google Scholar
[40]

G. Yang, T. Dong, X. Fang, and S. Su, Association data release with the randomised response based on Bayesian networks, Int. J. Comput. Sci. Eng., vol. 20, no. 1, pp. 120–129, 2019.
Crossref Google Scholar
[41]

L. Fan and L. Xiong, An adaptive approach to real-time aggregate monitoring with differential privacy, IEEE Trans. Knowl. Data Eng., vol. 26, no. 9, pp. 2094–2106, 2014.
Crossref Google Scholar
[42]
C. Dwork, Differential privacy: A survey of results, in Proc. 5 th Int. Conf. Theory and Applications of Models of Computation, Xi’an, China, 2008, pp. 1–19.
Crossref
[43]
F. Esponda, Negative surveys, arXiv preprint arXiv: math/0608176v1, 2006.
[44]

H. Jiang, W. Luo, and Z. Zhang, A privacy-preserving aggregation scheme based on immunological negative surveys for smart meters, Appl. Soft Comput., vol. 85, p. 105821, 2019.
Crossref Google Scholar
[45]

W. Yang, X. Chen, Z. Xiong, Z. Xu, G. Liu, and X. Zhang, A privacy-preserving aggregation scheme based on negative survey for vehicle fuel consumption data, Inf. Sci., vol. 570, pp. 526–544, 2021.
Crossref Google Scholar
[46]
H. Jiang and W. Luo, Multi-question negative surveys, in Proc. 3 rd Int. Conf. Data Mining and Big Data, Shanghai, China, 2018, pp. 503–512.
Crossref
[47]
H. Liao, A study of negative surveys with background knowledge, in Proc. 2019 IEEE 9 th Int. Conf. Electronics Information and Emergency Communication, Beijing, China, 2019, pp. 301–302.
Crossref
[48]

H. Jiang, W. Luo, B. Duan, and C. Wu, Enhancing the privacy of negative surveys using negative combined categories, Appl. Soft Comput., vol. 96, p. 106578, 2020.
Crossref Google Scholar
[49]
F. D. McSherry, Privacy integrated queries: An extensible platform for privacy-preserving data analysis, in Proc. 2009 ACM SIGMOD Int. Conf. Management of Data, Providence, RL, USA, 2009, pp. 19–30.
Crossref
[50]
The UK Government, The UK car accident dataset, https://data.gov.uk/dataset/road-accidents-safety-data, 2014.
[51]
Taxi & Limousine Commission, NYC yellow taxi trip dataset, https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page, 2019.
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1674-1693
DOI: 10.26599/TST.2023.9010083
Cite this article:
Wang X, Mo L, Zheng X, et al. Streaming Histogram Publication over Weighted Sliding Windows Under Differential Privacy. Tsinghua Science and Technology, 2024, 29(6): 1674-1693. https://doi.org/10.26599/TST.2023.9010083

414

Views

68

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 17 May 2023
Revised: 10 July 2023
Accepted: 01 August 2023
Published: 20 June 2024
© The Author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return