基于非均匀四叉树的位置大数据差分隐私划分发布方法

IR > 计算机与通信学院

	基于非均匀四叉树的位置大数据差分隐私划分发布方法
	晏燕; 高鑫; 王冰倩; 丛一鸣
	2023-05-26
专利权人	兰州理工大学
公开日期	2023-05-26
授权国家	中国
专利类型	授权发明
摘要	基于非均匀四叉树的位置大数据差分隐私划分发布方法，主要解决现有位置信息发布方法综合性能差的缺陷，提高位置大数据的发布隐私保护强度和范围计数查询精度。首先通过分析待发布位置大数据集合的分布特性确定划分结构与划分深度，对于不满足均匀性条件的二维区域按照深度优先原则进行非均匀四叉树迭代划分，直到满足算法的停止条件；然后按照“先纵向几何分配，再横向比例调整”的原则为划分结构中的各个子区域分配差分隐私预算，先根据非均匀四叉树的划分深度计算各层应当分配的几何隐私预算值，再根据同一棵子树内四个节点的密度比例进行隐私预算的局部调整；最后将各个划分区域内的原始统计值与差分隐私噪声相加，得到最终的发布数据。
申请日期	2020-02-23
优先权日	2020-02-23
预估到期日	2040-02-23
语种	中文
专利状态	授权
申请号	CN202010110059.1
公开（公告）号	CN111339091B
IPC 分类号	G06F16/22 ; G06F16/2458 ; G06F16/29 ; G06F17/18
专利代理人	董斌
代理机构	兰州振华专利代理有限责任公司
CPC分类号	G06F16/2246 ; G06F16/2462 ; G06F16/29 ; G06F17/18 ; Y02D30/70
权利要求	1.基于非均匀四叉树结构的位置大数据差分隐私划分发布方法，其特征在于，包括： (1)根据待发布位置大数据集合确定划分结构与划分深度：设定划分停止的条件为：当前区域内不包含位置点信息，或者当前区域范围小于划分尺寸的下限，或者当前区域内位置点分布状态满足设定的均匀条件；如果待发布位置大数据集合不满足上述停止条件，则将其分解为只包含经度坐标和只包含纬度坐标的两个集合，分别从经度方向和纬度方向将整个位置大数据集覆盖的空间范围平均分割为m个子区域，并计算经度和纬度方向的概率分布密度；选择概率分布密度大于设定阈值的第一个经度值和纬度值作为划分点，将当前区域分割为四个大小不等的子区域；按照深度优先原则遍历四个子区域，并迭代上述划分过程直到满足划分停止条件； (2)为各划分区域分配差分隐私预算：按照“先纵向几何分配，再横向比例调整”的原则，首先根据步骤(1)得到的划分深度计算各层应当分配的几何隐私预算值；然后在非均匀四叉树划分结构的每一层中，根据同一棵子树内四个节点的密度比例进行隐私预算的局部调整； (3)根据差分隐私模型生成位置大数据统计发布信息；首先根据步骤(1)得到的非均匀四叉树划分结构统计各子区域范围内的位置点数量；然后根据步骤(2)得到的各区域差分隐私预算计算对应区域应当添加的Laplace噪声值；最后将所有划分区域的原始统计值与差分隐私噪声相加，得到最终的位置大数据统计发布信息；其中步骤(1)包括设定划分停止条件(一)：当前节点内不包含任何位置点；设定划分停止条件(二)：当前节点的覆盖范围小于划分尺寸下限MinSize＝0.0005，对应50m×50m的矩形区域；设定划分停止条件(三)：当前节点内位置点的分布状态满足设定的区域均匀条件SDR≤3，并根据下式计算区域均匀条件(SDR)：其中xi和yi是区域内某个位置点的经纬度坐标；x和y代表该区域所有位置点的经度和纬度平均值；设置初始划分结构为空集合；设置初始划分深度h＝0；将待发布位置大数据集合覆盖的空间区域设置为当前节点；如果当前节点不满足任意设定的停止条件，则将其分解为一个只包含所有经度信息的集合LX和一个只包含所有纬度信息的集合LY；同时沿经度方向和纬度方向将LX和LY覆盖的空间范围平均分割为m＝1000个子区域，并统计各区域内的位置点分布密度PDDXi和PDDYi，(i＝1,2,...,m)；设定经度方向和纬度方向的密度阈值如下式，选择概率分布密度大于阈值的第一个经度值和纬度值作为划分点，将当前节点分割为四个大小不等的子区域；将上述四个子区域加入划分结构，划分深度h＝h+1；依次将上述四个子区域设置为当前节点，按照深度优先原则对当前节点迭代执行后续划分步骤，直到满足任意某个设定的划分停止条件；其中步骤(2)具体包括：以上得到的非均匀四叉树划分深度h，按照下式计算各层应当分配的差分隐私几何预算值：其中ε是差分隐私模型的总体隐私预算值，ε0代表非均匀四叉树划分最深层的叶子结点分配的差分隐私预算值，εh代表根节点分配的差分隐私预算值；遍历得到的划分结构中的所有节点，对于满足区域均匀条件并停止划分的节点，将其差分隐私预算调整为：遍历得到的非均匀四叉树划分结构的所有层，在每一层中根据同一棵子树内四个节点的密度比例进行隐私预算的进一步调整：其中εi代表节点的原有隐私预算值，ratei为该节点在当前子树内的密度比例，各所述节点的密度为各所述节点中位置点的数量；是调整以后该节点的隐私预算值；其中步骤(3)包括：遍历生成的非均匀四叉树划分结构中的各个节点，逐一统计各节点覆盖范围内的位置点数量f(T)i，(i＝1,2,...N)；根据得到的各节点差分隐私预算值，计算对应节点应当添加的差分隐私噪声值S＝1是设定的敏感度；将各节点的位置点数量与其对应的差分隐私噪声值相加，得到节点的发布统计值
引用专利	CN107145796A;CN109726587A;US20090282122A1
被引用专利数量	0
简单法律状态	有效
文献类型	专利
条目标识符	https://ir.lut.edu.cn/handle/2XXMBERH/107666
专题	计算机与通信学院
推荐引用方式 GB/T 7714	晏燕,高鑫,王冰倩,等. 基于非均匀四叉树的位置大数据差分隐私划分发布方法[P]. 2023-05-26.