基于R树的差分隐私轨迹保护方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112560084A(43)申请公布日2021.03.26(21)申请号202011426209.6(22)申请日2020.12.11(71)申请人南京航空航天大学地址210016江苏省南京市秦淮区御道街29号(72)发明人皮德常袁水莲赵晓东(51)Int.Cl.G06F21/62(2013.01)G06F16/22(2019.01)权利要求书2页说明书8页附图2页(54)发明名称基于R树的差分隐私轨迹保护方法(57)摘要本发明公开了基于R树的差分隐私轨迹保护方法，包括：基于R树索引结构提出轨迹相似树结构，实现对轨迹数据的空间存储、查询处理；结合差分隐私技术构建DP‑轨迹相似树，对节点中的移动对象统计值添加噪音，抵御背景知识攻击，实现保护数据隐私的目的；对于轨迹数据中存在的其他推理攻击问题，在构建DP‑轨迹相似树时，通过差分隐私对轨迹中的其他数据添加拉普拉斯噪音，进而抵御攻击；对于添加的拉普拉斯噪音会导致轨迹相似树上的噪音数据结果存在不一致的情况，对算法进行一致性处理。本发明的优点是：基于R树索引结构提出了一种新型的轨迹相似树结构，该结构可以保留轨迹的时空特性并实现轨迹的高效检索。在轨迹相似树结构基础上，提出了满足差分隐私的轨迹数据保护方法。根据轨迹的语义信息，利用差分隐私抵御信息推理攻击。CN112560084ACN112560084A权利要求书1/2页1.基于R树的差分隐私轨迹保护方法，其主要特征包括如下步骤：(1.1)构建轨迹相似树：通过比较两条移动对象轨迹之间的相似性来代替R‑树最小边界矩形的方法建立轨迹相似树，轨迹相似性包括计算轨迹序列相似程度以及度量Fréchet距离，另外，轨迹相似树节点中存储的是轨迹序列；(1.2)构建DP‑轨迹相似树：利用差分隐私将(1.1)中的轨迹相似树构建成DP‑轨迹相似树，对该树上的移动对象统计值和位置数据外的其他数据均添加拉普拉斯噪音，抵御轨迹的其他信息推理攻击，从而保护轨迹数据中蕴含的用户隐私；(1.3)数据一致性约束：针对添加噪音导致轨迹相似树上的噪音数据结果存在数据不一致的情况，对轨迹数据进行一致性约束。2.根据权利要求1所述的基于R树的差分隐私轨迹保护方法，其特征在于，步骤(1.1)构建轨迹相似树，实现方法包括：(2.1)计算不同轨迹之间的轨迹序列的相似程度，即不同轨迹之间相同轨迹序列占总的轨迹序列的百分比，轨迹序列的相似程度计算公式如下：其中，Ti表示第i条轨迹，p＝(p1p2...pn)表示轨迹序列。(2.2)计算不同轨迹之间的Fréchet距离，将轨迹之间的Fréchet距离较小的划分到同一个区域。Fréchet距离的计算方式如下：其中，α和β表示单位区间的重参数化函数，t表示时间点，d表示欧氏距离。3.根据权利要求1所述的基于R树的差分隐私轨迹保护方法，其特征在于，步骤(1.2)构建DP‑轨迹相似树，实现方法包括：(3.1)构建轨迹相似树：首先，依据上述介绍的轨迹相似树的建立规则，将数据构造为轨迹相似树的索引结构。接着，利用差分隐私性质将差分隐私预算ε依据轨迹相似树的高度均分成为若干等份，均分后的大小为(3.2)遍历轨迹相似树并添加噪声：对轨迹相似树进行层次遍历，依次遍历轨迹相似树上每一层的所有节点，对节点的数据类型进行判断，如果数据类型是移动对象的位置数据，统计该轨迹段上移动对象的数量，并对该数值添加拉普拉斯噪音；如果数据类型是其他数据，那么统计相应数据的数量，并且也对该数值添加拉普拉斯噪音。DP‑轨迹相似树通过如上操作可以确保移动对象的轨迹隐私不被泄露。4.根据权利要求1所述的基于R树的差分隐私轨迹保护方法，其特征在于，步骤(1.3)数据一致性约束，实现方法包括：(4.1)一致性约束条件：由于在轨迹相似树的每个节点中添加的随机噪音是独立的，导致加噪后的数据不符合一致性约束，从而使得加噪后的数据可用性相对较差。本发明通过一致性约束提高加噪数据的可用性。对于给定的轨迹相似树，需满足下面两个限制条件保证加入噪音后的数据的可用性：对于轨迹相似树上的任意节点pi，该节点并非根节点，节点pi上的移动对象的数量值应当不高于其父亲节点上的移动对象数量值；对于轨迹相似树上的任意节点pj，该节点并非叶子节点，都有节点pj上的移动对象数量值应当等于其所有孩子2CN112560084A权利要求书2/2页节点上的移动对象的数量值之和；(4.2)调整DP‑轨迹相似树节点中移动对象的统计值：为使本发明的噪音数据满足(4.1)中的条件，采用一致性约束方法调整DP‑轨迹相似树节点上移动对象的统计值。3CN112560084A说明书1/8页基于R树的差分隐私轨迹保护方法技术领域[0001]本发明涉及基于R树的差分隐私轨迹保护