CAJ | 학술논문

为解决现有基于网格结构的差分隐私二维空间数据划分发布方法可能引起局部划分过细导致查询精度低的问题，提出了基于kd-树的差分隐私二维空间数据划分发布方法—kd-PPDP算法（differentially privacy partitio-ning publication algorithm based on kd-tree）。算法采用了kd-树算法思想，通过启发式地识别网格化后数据分布情况并合并相邻近似网格单元来防止局部划分过细问题，从而减少所添加的噪声，提高查询精度。通过实验对比分析了kd-PPDP算法与现有基于网格结构的划分发布方法的查询误差以及时间效率，结果表明了该算法的有效性和可行性。
위해결현유기우망격결구적차분은사이유공간수거화분발포방법가능인기국부화분과세도치사순정도저적문제，제출료기우kd-수적차분은사이유공간수거화분발포방법—kd-PPDP산법（differentially privacy partitio-ning publication algorithm based on kd-tree）。산법채용료kd-수산법사상，통과계발식지식별망격화후수거분포정황병합병상린근사망격단원래방지국부화분과세문제，종이감소소첨가적조성，제고사순정도。통과실험대비분석료kd-PPDP산법여현유기우망격결구적화분발포방법적사순오차이급시간효솔，결과표명료해산법적유효성화가행성。
The existing differentially privacy two-dimensional dataset partitioning publication approaches might result in over-partitioning of certain local regions thus lower the query accuracy.To solve this problem,a new differentially pri-vacy partitioning publication algorithm based on kd-tree for two-dimensional dataset (kd-PPDP)was proposed.To re-duce the noise generated by the Laplace mechanism and improve the accuracy of query,the new approach which was in-spired by the core thought of kd-tree took the gridding data distribution into account and merged adjacent grid units with similar information heuristically to prevent local over-partitioning.The new approach was compared with the existing differentially privacy partitioning publication approachs based on grid structure in terms of query error and time complex-ity.Experimental results showed that the approach was feasible and effective.