Abstract: Many areas are now experiencing data streams that contain privacy-sensitive information. Although the sharing and release of these data are of great commercial value, if these data are released directly, the private user information in the data will be disclosed. Therefore, how to continuously generate publishable histograms (meeting privacy protection requirements) based on sliding data stream windows has become a critical issue, especially when sending data to an untrusted third party. Existing histogram publication methods are unsatisfactory in terms of time and storage costs, because they must cache all elements in the current sliding window (SW). Our work addresses this drawback by designing an efficient online histogram publication (EOHP) method for local differential privacy data streams. Specifically, in the EOHP method, the data collector first crafts a histogram of the current SW using an approximate counting method. Second, the data collector reduces the privacy budget by using the optimized budget absorption mechanism and adds appropriate noise to the approximate histogram, making it possible to publish the histogram while retaining satisfactory data utility. Extensive experimental results on two different real datasets show that the EOHP algorithm significantly reduces the time and storage costs and improves data utility compared to other existing algorithms.

一种基于局部差分隐私的数据流高效在线直方图发布算法

[1]Cormode G, Jha S, Kulkarni T, et al., 2018. Privacy at scale: local differential privacy in practice. Proc Int Conf on Management of Data, p.1655-1658.

[2]Datar M, Gionis A, Indyk P, et al., 2002. Maintaining stream statistics over sliding windows. SIAM J Comput, 31(6):1794-1813.

[3]Duchi JC, Jordan MI, Wainwright MJ, 2013. Local privacy and statistical minimax rates. Proc IEEE 54^th Annual Symp on Foundations of Computer Science, p.429-438.

[4]Dwork C, 2008. Differential privacy: a survey of results. Proc 5^th Int Conf on Theory and Applications of Models of Computation, p.1-19.

[5]Dwork C, Roth A, 2014. The algorithmic foundations of differential privacy. Found Trends Theor Comput Sci, 9(3-4):211-407.

[6]Dwork C, Naor M, Pitassi T, et al., 2010. Differential privacy under continual observation. Proc 42^nd ACM Symp on Theory of Computing, p.715-724.

[7]Erlingsson Ú, Pihur V, Korolova A, 2014. RAPPOR: randomized aggregatable privacy-preserving ordinal response. Proc ACM SIGSAC Conf on Computer and Communications Security, p.1054-1067.

[8]Erlingsson Ú, Feldman V, Mironov I, et al., 2019. Amplification by shuffling: from local to central differential privacy via anonymity. Proc 30^th Annual ACM-SIAM Symp on Discrete Algorithms, p.2468-2479.

[9]Errounda FZ, Liu Y, 2018. Continuous location statistics sharing algorithm with local differential privacy. Proc IEEE Int Conf on Big Data, p.5147-5152.

[10]Fan LY, Xiong L, 2013. An adaptive approach to real-time aggregate monitoring with differential privacy. IEEE Trans Knowl Data Eng, 26(9):2094-2106.

[11]Joy S, Paulraj RL, Punith M, et al., 2023. A Raspberry Pi based smart security patrol robot. Proc 7^th Int Conf on Computing Methodologies and Communication, p.1140-1145.

[12]Kairouz P, Oh S, Viswanath P, 2014. Extremal mechanisms for local differential privacy. Proc 27^th Int Conf on Neural Information Processing Systems, p.2879-2887.

[13]Kim H, Ben-Othman J, Mokdad L, 2019. UDiPP: a framework for differential privacy preserving movements of unmanned aerial vehicles in smart cities. IEEE Trans Veh Technol, 68(4):3933-3943.

[14]Kim H, Ben-Othman J, Mokdad L, et al., 2020. Research challenges and security threats to AI-driven 5G virtual emotion applications using autonomous vehicles, drones, and smart devices. IEEE Netw, 34(6):288-294.

[15]Labs J, Terry S, 2020. Privacy in the coronavirus era. Genet Test Mol Biomark, 24(9):535-536.

[16]Lee S, Lee S, Kim H, 2023. Differential security barriers for virtual emotion detection in maritime transportation stations with cooperative mobile robots and UAVs. IEEE Trans Intell Trans Syst, 24(2):2461-2471.

[17]Liu H, Liu JY, Chen F, et al., 2022. Progressive residual learning with memory upgrade for ultrasound image blind super-resolution. IEEE J Biomed Health Inform, 26(9):4390-4401.

[18]Liu Z, Li J, Chen XF, et al., 2020. Fuzzy logic-based adaptive point cloud video streaming. IEEE Open J Comput Soc, 1:121-130.

[19]Liu Z, Zhan C, Cui Y, et al., 2021. Robust edge computing in UAV systems via scalable computing and cooperative computing. IEEE Wirel Commun, 28(5):36-42.

[20]Narayanan A, Shmatikov V, 2008. Robust de-anonymization of large sparse datasets. Proc IEEE Symp on Security and Privacy, p.111-125.

[21]Nguyên TT, Xiao XK, Yang Y, et al., 2016. Collecting and analyzing data from smart device users with local differential privacy. https://arxiv.org/abs/1606.05053

[22]Qin Z, Yang Y, Yu T, et al., 2016. Heavy hitter estimation over set-valued data with local differential privacy. Proc ACM SIGSAC Conf on Computer and Communications Security, p.192-203.

[23]Ren XB, Shi L, Yu WR, et al., 2022. LDP-IDS: local differential privacy for infinite data streams. Proc Int Conf on Management of Data, p.1064-1077.

[24]Sultani ZN, Ghani RF, 2015. Kinect 3D point cloud live video streaming. Proc Comput Sci, 65:125-132.

[25]Thakurta AG, Vyrros AH, Vaishampayan US, et al., 2018. Emoji Frequency Detection and Deep Link Frequency. Patent No. 9894089 B2, US.

[26]Wang Q, Zhang Y, Lu X, et al., 2018. Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy. IEEE Trans Depend Secure Comput, 15(4):591-606.

[27]Wang S, Sinnott R, Nepal S, 2018. Privacy-protected statistics publication over social media user trajectory streams. Future Gener Comput Syst, 87:792-802.

[28]Wang XJ, Liu Z, Liu AX, et al., 2023. A near-optimal protocol for continuous tag recognition in mobile RFID systems. IEEE/ACM Trans Netw, 32(2):1303-1318.

[29]Yang G, Xia CT, Bai YL, 2018. Algorithm for differential privacy histogram for real-time data flow. J Nanjing Univ Posts Telecommun (Nat Sci Ed), 38(2):69-77 (in Chinese).

[30]Ye QQ, Hu HB, Meng XF, et al., 2019. PrivKV: key-value data collection with local differential privacy. Proc IEEE Symp on Security and Privacy, p.317-331.

[31]Zhang XJ, Chen R, Xu JL, et al., 2014. Towards accurate histogram publication under differential privacy. Proc SIAM Int Conf on Data Mining, p.587-595.