A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy

ZHU Yi-bo; FANG Xian-jin; ZHANG Peng-fei; SUN Li; JIANG Rong

doi:10.12263/DZXB.20250021

您当前的位置：

首页 >

文章列表页 >

A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy

PAPERS | 更新时间：2025-08-18

- A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy
- ACTA ELECTRONICA SINICA Vol. 53, Issue 5, Pages: 1541-1558(2025)
- 作者机构：
  
  1.安徽理工大学计算机科学与工程学院，安徽淮南 232001
  2.安徽理工大学煤炭无人化开采数智技术全国重点实验室，安徽淮南 232001
  3.云南财经大学云南省服务计算重点实验室，云南昆明 650221
  4.华北电力大学控制与计算机工程学院，北京 102206
- 作者简介：
- 基金信息：
  
  Foundation of Yunnan Key Laboratory of Service Computing(YNSC24116);Anhui Provincial Major Science and Technology Project(18030901025);National Natural Science Foundation of China(61572034;62202164)
- DOI：10.12263/DZXB.20250021
  CLC： TP309;
- Received：06 January 2025，
  
  Revised：2025-04-03，
  
  Published：25 May 2025
- 稿件说明：
移动端阅览
朱伊波, 方贤进, 张朋飞, 等. 本地差分隐私下面向离群点的真值发现算法研究[J]. 电子学报, 2025, 53(05): 1541-1558.

ZHU Yi-bo, FANG Xian-jin, ZHANG Peng-fei, et al. A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy[J]. Acta Electronica Sinica, 2025, 53(05): 1541-1558.
朱伊波, 方贤进, 张朋飞, 等. 本地差分隐私下面向离群点的真值发现算法研究[J]. 电子学报, 2025, 53(05): 1541-1558. DOI：10.12263/DZXB.20250021

ZHU Yi-bo, FANG Xian-jin, ZHANG Peng-fei, et al. A Study of Truth Discovery Algorithms for Forward Outliers Under Local Differential Privacy[J]. Acta Electronica Sinica, 2025, 53(05): 1541-1558. DOI：10.12263/DZXB.20250021

摘要

近年来，随着智能移动设备的普及和强大的传感能力，移动群智感知（Mobile CrowdSensing，MCS）已成为大规模感知城市动态的一种有潜力的技术.MCS中一个核心问题是如何从众多工人提交的嘈杂的感知数据中发现“真值”.同时，真值发现过程中不可避免地面临隐私泄露问题.为应对这一挑战，研究者通常结合本地差分隐私（Local Differential Privacy，LDP）技术，通过对工人数据添加随机噪声实现隐私保护.然而，由于拉普拉斯分布的随机性和无界性，可能会注入大量噪声，从而产生离群点.此外，现有研究往往未能充分建模为满足LDP保护而注入的拉普拉斯噪声，导致求得的“真值”精度低，且现有的真值发现方法通常仅适用于离散值或无法严格满足LDP约束的问题.针对上述问题，本文提出一种基于LDP的面向离群点的真值发现算法LEADER.该算法首先对工人提交的数据添加拉普拉斯噪声，以确保工人隐私不被泄露.然后针对离群点问题，采用Huber损失函数作为度量距离，降低离群点对真值估计结果的影响.最后通过引入数据度量方法，优化工人和任务重要性权重分配，并根据提交值之间的相似性对工人进行分组，从而有效保护工人隐私的同时提高估计“真值”的精度.理论分析表明，LEADER算法在严格满足LDP约束的前提下，能够有效处理连续型数据，并实现高精度的真值发现.此外，与非隐私下的真值发现方法相比，LEADER算法在通信开销和计算开销方面保持相近.在两个真实数据集和一个合成数据集上的实验结果表明，LEADER算法的表现显著优于现有对比算法，噪声“真值”精度提升了至少18%.

Abstract

In recent years

with the widespread adoption of intelligent mobile devices and their powerful sensing capabilities

mobile crowdsensing (MCS) has emerged as a promising method for large-scale sensing of urban dynamics. A key challenge in MCS is discovering the truth from the noisy sensory data submitted by numerous workers. However

the process of truth discovery inevitably raises privacy concerns. To address these challenges

researchers frequently integrate local differential privacy (LDP) techniques by adding random noise to workers’ data for privacy protection. Nonetheless

the randomness and unbounded nature of Laplace noise may inject excessive noise

resulting in outliers. Additionally

existing research often fails to adequately model the Laplace noise injected to satisfy LDP protection

resulting in low truth accuracy. Moreover

the current truth discovery methods are typically only applicable to discrete data

or cannot strictly satisfy the LDP constraints. To address the above issues

this paper proposes LEADER

an outlier-oriented truth discovery algorithm under LDP. First

the algorithm adds Laplace noise to workers’ data to ensure privacy protection. Second

it addresses outliers by adopting the Huber loss function to measure distances

mitigating their impact on truth estimation. Finally

through a data-driven metric approach

the algorithm optimizes the weight allocation for worker and task importance and groups workers based on the similarity of their submitted values. These enhancements enable LEADER to improve the accuracy of estimated truths while maintaining privacy protection. Theoretical analysis demonstrates that LEADER strictly satisfies LDP constraints

effectively handles continuous data

and achieves high-accuracy truth discovery. Furthermore

compared to non-private truth discovery methods

the LEADER algorithm maintains comparable communication and computational overhead. Experimental results on two real-world datasets and a synthetic dataset indicate that the LEADER algorithm significantly outperforms existing methods

achieving at least an 18% improvement in the accuracy of the noisy truth.

关键词

Keywords

references

蒋伟进 , 王海娟 , 周为 , 等 . 基于自适应连续时间的群智感知轨迹隐私保护方案 [J ] . 电子学报 , 2023 , 51 ( 10 ): 2894 - 2901 .

JIANG W J , WANG H J , ZHOU W , et al . Track privacy protection scheme based on adaptive continuous time in crowdsensing [J ] . Acta Electronica Sinica , 2023 , 51 ( 10 ): 2894 - 2901 . (in Chinese)

童咏昕 , 袁野 , 成雨蓉 , 等 . 时空众包数据管理技术研究综述 [J ] . 软件学报 , 2017 , 28 ( 1 ): 35 - 58 .

TONG Y X , YUAN Y , CHENG Y R , et al . Survey on spatiotemporal crowdsourced data management techniques [J ] . Journal of Software , 2017 , 28 ( 1 ): 35 - 58 . (in Chinese)

ZHANG P F , CHENG X , SU S , et al . Area coverage-based worker recruitment under geo-indistinguishability [J ] . Computer Networks , 2022 , 217 : 109340 .

WANG T C , LV C M , WANG C T , et al . A secure truth discovery for data aggregation in mobile crowd sensing [J ] . Security and Communication Networks , 2021 , 2021 : 2296386 .

LI Q , LI Y L , GAO J , et al . Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation [C ] // Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data . New York : ACM , 2014 : 1187 - 1198 .

AHMAD JALALI N , CHEN H S . Federated learning incentivize with privacy-preserving for IoT in edge computing in the context of B5G [J ] . Cluster Computing , 2024 , 28 . DOI: 10.1007/s10586-024-04788-7 http://dx.doi.org/10.1007/s10586-024-04788-7 .

陈红松 , 孟彩霞 , 刘书雨 . 基于经验小波变换的基因关联隐私保护实验研究 [J ] . 湖南大学学报(自然科学版) , 2020 , 47 ( 2 ): 125 - 133 .

CHEN H S , MENG C X , LIU S Y . Privacy protection experimental research on genes association ranking based on empirical wavelet transform [J ] . Journal of Hunan University (Natural Sciences) , 2020 , 47 ( 2 ): 125 - 133 . (in Chinese)

FENG J , WU Y F , SUN H , et al . Panther: Practical secure two-party neural network inference [J ] . IEEE Transactions on Information Forensics and Security , 2025 , 20 : 1149 - 1162 .

叶青青 , 孟小峰 , 朱敏杰 , 等 . 本地化差分隐私研究综述 [J ] . 软件学报 , 2018 , 29 ( 7 ): 1981 - 2005 .

YE Q Q , MENG X F , ZHU M J , et al . Survey on local differential privacy [J ] . Journal of Software , 2018 , 29 ( 7 ): 1981 - 2005 . (in Chinese)

HUANG W , ZHOU S J , ZHU T Q , et al . Improving Laplace mechanism of differential privacy by personalized sampling [C ] // 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) . Piscataway : IEEE , 2020 : 623 - 630 .

LI T P , WANG L , PENG D H , et al . Causal discovery evaluation framework in the absence of ground-truth causal graph [J ] . IEEE Access , 2024 , 12 : 136502 - 136514 .

FANG X S , WANG X Z , SHENG Q Z , et al . Generalizing truth discovery by incorporating multi-truth features [J ] . Computing , 2024 , 106 ( 5 ): 1557 - 1583 .

BAI J , GUI J S , HUANG G S , et al . UAV-supported intelligent truth discovery to achieve low-cost communications in mobile crowd sensing [J ] . Digital Communications and Networks , 2024 , 10 ( 4 ): 837 - 852 .

WANG H , LIU A F , XIONG N N , et al . TVD-RA: A truthful data value discovery-based reverse auction incentive system for mobile crowdsensing [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 4 ): 5826 - 5839 .

KANG Y C , LIU A F , XIONG N N , et al . DTD: An intelligent data and bid dual truth discovery scheme for MCS in IIoT [J ] . IEEE Internet of Things Journal , 2024 , 11 ( 2 ): 2507 - 2519 .

LOHRER A , KAZEMPOUR D , HÜNEMÖRDER M , et al . CoMadOut: A robust outlier detection algorithm based on CoMAD [J ] . Machine Learning , 2024 , 113 ( 10 ): 8061 - 8135 .

RIAHI-MADVAR M , NASERSHARIF B , AZIRANI A A . Subspace outlier detection in high dimensional data using ensemble of PCA-based subspaces [C ] // 2021 26th International Computer Conference, Computer Society of Iran (CSICC) . Piscataway : IEEE , 2021 : 1 - 5 .

YANG P , WANG D , WEI Z J , et al . An outlier detection approach based on improved self-organizing feature map clustering algorithm [J ] . IEEE Access , 2019 , 7 : 115914 - 115925 .

GAO X , YU J H , ZHA S , et al . An ensemble-based outlier detection method for clustered and local outliers with differential potential spread loss [J ] . Knowledge-Based Systems , 2022 , 258 : 110003 .

刘财辉 , 刘地金 . 离群点检测的邻近性方法综述 [J ] . 计算机工程与应用 , 2022 , 58 ( 21 ): 1 - 12 .

LIU C H , LIU D J . Survey of proximity methods for outlier detection [J ] . Computer Engineering and Applications , 2022 , 58 ( 21 ): 1 - 12 . (in Chinese)

KNORR E M , NG R T , TUCAKOV V . Distance-based outliers: Algorithms and applications [J ] . The VLDB Journal , 2000 , 8 ( 3 ): 237 - 253 .

RAMASWAMY S , RASTOGI R , SHIM K . Efficient algorithms for mining outliers from large data sets [C ] // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data . New York : ACM , 2000 : 427 - 438 .

SCHUBERT E , RENZ M , KRÖGER P . Generalized outlier detection with flexible kernel density estimates [C ] // Proceedings of the 14th SIAM International Conference on Data Mining . Philadelphia : SIAM , 2014 : 542 - 550 .

CÁRDENAS-MONTES M . Depth-based outlier detection algorithm [C ] // Hybrid Artificial Intelligence Systems . Cham : Springer International Publishing , 2014 : 122 - 132 .

SUN H P , DONG B X , WANG H , et al . Truth inference on sparse crowdsourcing data with local differential privacy [C ] // 2018 IEEE International Conference on Big Data (Big Data) . Piscataway : IEEE , 2018 : 488 - 497 .

LI Y L , MIAO C L , SU L , et al . An efficient two-layer mechanism for privacy-preserving truth discovery [C ] // Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . New York : ACM , 2018 : 1705 - 1714 .

HUANG Y X , LIU F , ZHAO J C , et al . An incentive-based differential privacy-preserving truth discovery over streaming data [C ] // GLOBECOM 2022 IEEE Global Communications Conference . Piscataway : IEEE , 2022 : 4848 - 4853 .

SUN P , WANG Z B , WU L T , et al . Towards personalized privacy-preserving incentive for truth discovery in mobile crowdsensing systems [J ] . IEEE Transactions on Mobile Computing , 2022 , 21 ( 1 ): 352 - 365 .

ZHANG P F , CHENG X , SU S , et al . PrivTDSI: A local differentially private approach for truth discovery via sampling and inference [J ] . IEEE Transactions on Big Data , 2023 , 9 ( 2 ): 471 - 484 .

ZHANG P F , CHENG X , SU S , et al . Effective truth discovery under local differential privacy by leveraging noise-aware probabilistic estimation and fusion [J ] . Knowledge-Based Systems , 2023 , 261 . DOI: 1016/j.knosys.2022.110213 http://dx.doi.org/1016/j.knosys.2022.110213 .

XIONG P , LI G R , LIU H Z , et al . Decentralized privacy-preserving truth discovery for crowd sensing [J ] . Information Sciences , 2023 , 632 : 730 - 741 .

XU G W , LI H W , XU S M , et al . Catch you if you deceive me: Verifiable and privacy-aware truth discovery in crowdsensing systems [C ] // Proceedings of the 15th ACM Asia Conference on Computer and Communications Security . New York : ACM , 2020 : 178 - 192 .

DWORK C , MCSHERRY F , NISSIM K , et al . Calibrating noise to sensitivity in private data analysis [C ] // Theory of Cryptography . Berlin : Springer , 2006 : 265 - 284 .

DWORK C , ROTH A . The algorithmic foundations of differential privacy [J ] . Foundations and Trends in Theoretical Computer Science , 2013 , 9 ( 3/4 ): 211 - 487 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Privacy Protection Method for K-modes Clustering Data with Local Differential Privacy

Differentially Private with Sparse and Smooth Self-Distillation

Blockchain-Based Hierarchical Federated Learning System

Related Author

ZHU Geng-ming

MAO Xin-jun

YUAN Liu-jie

ZHANG Shao-bo

Geng-ming ZHU

Xin-jun MAO

Liu-jie YUAN

Shao-bo ZHANG

Related Institution

Key Laboratory of Software Engineering for Complex Systems, National University of Defense Technology

School of Computer Science and Engineering, Hunan University of Science and Technology

School of Computer Science and Engineering， Hunan University of Science and Technology

Key Laboratory of Software Engineering for Complex Systems， National University of Defense Technology

School of Information, Renmin University of China

⁰