| 摘要: |
| 基于本地化差分隐私多关系表示上的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种多关系数据集上进行比较, 实验结果表明其响应查询算法优于同类算法. |
| 关键词: 本地化差分隐私 多表星形连接查询 层次结构 纵向节点组合 随机应答机制 |
| DOI：10.13328/j.cnki.jos.007152 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金(62072156) |
|
| Multi-table Star-JOIN Queries Based on Local Differential Privacy |
|
ZHANG Xiao-Jian1, CAO Xiao-Jie1, WANG Ning2, MENG Xiao-Feng3
|
|
1.College of Computer and Information Engineering, Henan University of Economics and Law, Zhengzhou 450046, China;2.Faculty of Information Science and Engineering, Ocean University of China, Qingdao 266100, China;3.School of Information, Renmin University of China, Beijing 100872, China
|
| Abstract: |
| 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 diverse multi-relational datasets, experimental outcomes demonstrate the superiority of the LPRR-JOIN algorithm in query response performance. |
| Key words: local differential privacy multi-table Star-JOIN query hierarchical structure longitudinal-path node combination random response mechanism |
