基于差分隐私的路网环境skyline查询

Differential Privacy-Based skyline Query in Road Network Environment

路网中的skyline查询在智慧交通、兴趣点发现和位置服务等领域具有重要的应用价值,但存在查询效率较低、未考虑查询结果的隐私性等问题。有鉴于此,文中提出了一种基于差分隐私的路网环境下skyline查询方法。首先,针对路网环境下的初始数据集数据量大和数据复杂的特点,对数据集进行预处理,利用基于距离属性划分的skyline层和路网Voronoi图的性质提出了3个剪枝规则,基于剪枝规则给出了路网环境下的数据集剪枝算法,从而有效地过滤掉大量冗余数据;其次,针对过滤后的数据集,利用网格索引的存储方式来节省存储空间,并设计了基于网格索引的skyline扩展树,基于扩展树和相应的剪枝规则提出了查询全局候选skyline点集的算法;最后,针对查询结果集,利用差分隐私预算分配模型来分配隐私预算,并基于信息散度进行结果集发布,有效提高了数据信息的隐私性。实验结果表明:所提出的查询方法的准确率在99%以上;其在数据集规模较大情况下的查询效率相较于传统skyline查询方法提升10%以上;在总差分隐私预算为0.01、0.10、0.50和1.00时,所提出的隐私预算分配方法的相对误差均低于等差分配和等比分配方法。

The skyline query in road networks has important application value in the fields such as intelligent transportation,point of interest discovery,and location services.In order to solve the problem of low efficiency of skyline queries in road network environment and the lack of privacy of query results,a differential privacy-based skyline query method in road network environment is proposed.In this method,first,aiming at the characteristics of large data amount and complex data in the initial dataset of road network environment,the dataset is preprocessed,and three pruning rules are proposed based on the properties of the skyline layer divided by distance attributes and the Voronoi diagram of the road network.Next,based on the pruning rules,a dataset pruning algorithm in road network environment is proposed,which can effectively filter out a large amount of redundant data.Then,for the filtered dataset,a storage method of grid index is utilized to save the storage space.Furthermore,a skyline extension tree based on grid index is designed,and an algorithm for querying global candidate skyline point sets is proposed based on the extension tree and the corresponding pruning rules.Finally,for the query result set,a differential privacy budget allocation model is employed to allocate privacy budgets,and a result set publishing algorithm based on information divergence is proposed,thus effectively improving the privacy of data information.Experimental results show that the proposed query method achieves a query accuracy of more than 99%.It improves the query efficiency by more than 10%,as compared with the traditional skyline query methods in larger datasets.When the total differential privacy budget is 0.01,0.10,0.50 and 1.00,the relative error of the proposed privacy budget allocation method is lower than that of the equal difference and equal ratio allocation methods.