Locally Differentially Private Truth Discovery Over Data Streams

Data inconsistency often arises from multiple observed sensory data due to varying participant reliability for crowdsensing systems. Truth discovery, which includesWeight EstimationandTruth Aggregation, for estimating participant reliability weights and aggregating uploaded values from inconsistent observations respectively, has emerged as an effective solution to address this issue. While local differential privacy (LDP) provides strong privacy guarantees by allowing participants to perturb their data locally before submission, existing LDP-based studies are either designed for static scenarios or compromise on privacy and accuracy trade-off for data streams, satisfying only weaker versions of LDP or mere differential privacy. To effectively and efficiently obtain truths over streams under rigorous LDP, we proposeNANOwhich is locally differeNtially privAte truth discovery via updatiNg time stamp determinatiOn. The main idea lies in its integration of Laplacian noise for privacy protection and inherent Gaussian noise representing natural data variability for effective weight and truth estimations, coupled with the adaptive determination of updating time stamps. InNANO, to obtain theWeight EstimationandTruth Aggregationunder LDP, we design a mixed noise-aware truth discovery methodMixTDby modeling the mixed noise. To capture the dynamic nature of weight and truth evolutions, we develop a changing-aware updating time stamp determination methodCUDto selectively re-conduct truth discovery at specific time stamps. We also introduce a dynamic privacy budget management strategy, which accumulates unused budgets from skipped updates for critical timestamps. In this way,Weight EstimationandTruth Aggregationare limited to critical time stamps, which significantly reduces the privacy budget segmentation and computational costs. We demonstrate thatNANOprovides rigorous LDP guarantees while achieving bounded utility and computational complexity. Extensive experimental results over four real-world datasets and three synthetic datasets showcase thatNANOoutperforms the state-of-the-arts by at least 20% improvement with negligible extra efficiency loss.