基于本地化差分隐私的多表星形连接查询  

Multi-table Star-JOIN Queries Based on Local Differential Privacy

作　　者：张啸剑 曹小杰 王宁[2] 孟小峰[3] ZHANG Xiao-Jian;CAO Xiao-Jie;WANG Ning;MENG Xiao-Feng(College of Computer and Information Engineering,Henan University of Economics and Law,Zhengzhou 450046,China;Faculty of Information Science and Engineering,Ocean University of China,Qingdao 266100,China;School of Information,Renmin University of China,Beijing 100872,China)

机构地区：[1]河南财经政法大学计算机与信息工程学院,河南郑州450046 [2]中国海洋大学信息科学与工程学部,山东青岛266100 [3]中国人民大学信息学院,北京100872

出　　处：《软件学报》2025年第2期830-850,共21页Journal of Software

基　　金：国家自然科学基金(62072156)。

摘　　要：基于本地化差分隐私多关系表示上的Star-JOIN查询已得到研究者广泛关注.现有基于OLH机制与层次树结构的Star-JOIN查询算法存在根节点泄露隐私风险、τ-截断机制没有给出如何选择合适τ值等问题.针对现有算法存在的不足,提出一种有效且满足本地化差分隐私的Star-JOIN查询算法LPRR-JOIN(longitudinal path random response for join).该算法充分利用层次树的纵向路径结构与GRR机制,设计一种纵向本地扰动算法LPRR,该算法以所有属性纵向路径上的节点组合作为扰动值域.每个用户把自身元组映射到相应节点组合中,再利用GRR机制对映射后的元组进行本地扰动.为了避免事实表上存在的频率攻击,LPRR-JOIN算法允许每个用户利用阈值τ本地截断自身元组个数,大于τ条元组删减、小于τ条元组补充.为了寻找合适的τ值,LPRR-JOIN算法利用τ-截断带来的偏差与扰动方差构造总体误差函数,通过优化误差目标函数获得τ值;其次结合用户分组策略获得τ值的总体分布,再利用中位数获得合适的τ值.LPRR-JOIN算法与现有算法在3种多关系数据集上进行比较,实验结果表明其响应查询算法优于同类算法.Star-JOIN queries based on local differential privacy(LDP)have attracted a lot of attention from researchers in recent years.Existing Star-JOIN queries based on the OLH mechanism and hierarchical tree structures face issues such as privacy leakage risks at the root node and the lack of guidance on selecting an appropriateτvalue for theτ-truncation mechanism.To remedy the shortcomings of the existing algorithms,this study proposes an effective Star-JOIN query algorithm,longitudinal path random response for join(LPRR-JOIN),to satisfy the requirements of LDP.In the LPRR-JOIN algorithm,full advantage is taken of the longitudinal path structure of the hierarchical tree and the GRR mechanism to propose an algorithm called LPRR to perturb users’tuples.This algorithm utilizes the combinations of nodes along the longitudinal paths of all attributes as the perturbation domain.In the LPRR-JOIN algorithm,tuples are mapped by each user to corresponding node combinations,followed by local perturbation of the mapped tuples using the GRR mechanism.To guard against frequency attacks on the fact table,the algorithm permits users to locally truncate the count of their tuples based on a thresholdτ,where tuples are deleted if their count exceedsτand supplemented if it falls belowτ.Two solutions are proposed within LPRR-JOIN to compute the optimalτvalue.The first is to solve the optimization equation over bias caused byτ-truncation and perturbation variance due to LPRR.The second is to obtain the distribution ofτunder the constraints of LDP and compute the median value from the distribution.The LPRR-JOIN algorithm employs an overall error function constructed from the bias and perturbation variance resulting fromτ-truncation to derive an optimalτvalue through the optimization of the error objective function.Additionally,by integrating a user grouping strategy,the algorithm ascertains the overall distribution ofτvalues and identifies a suitableτvalue using the median.When compared with current algorithms across three dive

关 键 词：本地化差分隐私 多表星形连接查询 层次结构 纵向节点组合 随机应答机制 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]