• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Query consistency constraints of differential privacy

JIA Jun-jie,CHEN Hui,MA Hui-fang,MU Yu-xiang   

  1. (School of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

     
  • Received:2019-07-13 Revised:2019-08-30 Online:2020-01-25 Published:2020-01-25

Abstract:

Aiming at the inconsistency phenomenon of range query in differential privacy histogram publishing, we study the local optimal linear unbiased estimation algorithm LBLUE that needs iterative adjustment and propose a CA algorithm that does not need iteration and satisfies the consistency constraint query. Consistency adjustment is performed on a full k-ary range tree with Laplace noise: the TDICE algorithm is first used for top-down inconsistency estimation, and then the BUCE algorithm is used for bottom-up consistency estimation, so as to obtain a full k-ary range tree with differential privacy, which meets consistency constraint query. The histogram data satisfying the consistency constraint query is published after traversal. Proof and experimental analysis show that the query range after consistency adjustment satisfies the consistency constraint query. It has higher accuracy than Boost-2 algorithm and LBLUE algorithm, and higher time efficiency than LBLUE algorithm.
 

Key words: differential privacy, Laplace mechanism, sensitivity, consistency constraint query