文献类型：期刊文献

中文题名：基于层次结构的隐私多维分析查询算法

英文题名：Answering private multidimensional analytical queries with hierarchical structure

作者：张啸剑[1];周丹[1];徐雅鑫[1];林东岱[2];纪守领[3];孟小峰[4]

第一作者：张啸剑

机构：[1]河南财经政法大学计算机与信息工程学院,郑州450002;[2]中国科学院信息工程研究所,北京100093;[3]浙江大学计算机科学与技术学院,杭州310027;[4]中国人民大学信息学院,北京100872

第一机构：河南财经政法大学计算机与信息工程学院

年份：2023

卷号：53

期号：6

起止页码：1111-1131

中文期刊名：中国科学:信息科学

外文期刊名：Scientia Sinica(Informationis)

收录：CSTPCD;;Scopus;北大核心:【北大核心2020】；CSCD:【CSCD2023_2024】；

基金：国家自然科学基金(批准号:62072156,91746115,61502146,91646203)资助项目。

语种：中文

中文关键词：多维分析查询;层次结构;本地化差分隐私;本地扰动;随机应答机制

外文关键词：multidimensional analytical queries;hierarchical structure;local differential privacy;local perturbation;random response mechanism

摘要：基于本地化差分隐私的多维分析查询(multi-dimensional analytical query,MDA)已得到了研究者的广泛关注.现有基于最优局部哈希(optimal local Hashing,OLH)机制与层次树结构的扰动方法存在泄露根结点隐私的风险.针对现有结合层次树结构的本地扰动机制不足,提出了一种有效且满足本地化差分隐私的MDA查询算法H4MDA (hierarchical structure for MDA),该算法充分利用层次树的横向与纵向结构特征设计了3种基于用户分组策略的本地扰动算法HGRR,LGRR-FD,LGRR.算法HGRR结合层次树横向结构与GRR机制本地扰动用户元组数据,通过摈弃根结点组合来响应MDA查询.不同于HGRR,LGRR-FD算法利用层次树的纵向结构与GRR机制扰动本地数据,同时通过添加假数据来避免叶子结点的隐私泄露.LGRR算法通过摈弃叶子结点层纵向扰动本地数据.收集者结合LGRR的扰动结果利用局部一致性处理技术重构层次树最后两层,通过添加虚拟叶子结点来响应MDA查询,而虚拟叶子结点计数之和等于其父节点计数.HGRR,LGRR-FD,LGRR算法与现有扰动算法在3种数据集上实验结果表明,其响应MDA查询的精度优于同类算法.
Given a relational table T whose tuples are distributed among n users,we study differentially private algorithms for answering multidimensional analytical(MDA) queries over T.Existing solutions to this problem mostly employ hierarchical trees and optimal local hashing(OLH) mechanisms to index and perturb users' tuples,respectively.However,OLH with hierarchical trees,cannot prevent privacy leakage of root node combinations.To remedy the shortcomings of the existing solutions,this paper proposes a locally differentially private algorithm called hierarchical structure for MDA(H4MDA) to answer MDA queries.With H4MDA,we first propose a horizontal Generalized Random Response(HGRR) mechanism to perturb users' tuples,which refrains from combining root nodes to prevent privacy leaks.To take full advantage of the vertical structure of the tree,we further propose,in contrast to HGRR,a longitudinal GRR mechanism with fake data(LGRR-FD) to perturb users' tuples.The LGRR-FD reports the noise result with fake data to the collector to prevent the privacy disclosure of the leaf nodes.In addition,we propose another longitudinal GRR(LGRR) mechanism that discards the leaf node level to report the noise tuples.To improve the utility of MDA queries,based on LGRR reports,the collector uses the local consistency technique to reconstruct the leaf level visited by some MDA queries.A theoretical analysis and extensive experiments show that our algorithms can effectively improve the utility of MDA queries and outperform existing solutions.