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

doi:10.12141/j.issn.1000-565X.220728

华南理工大学学报(自然科学版) ›› 2024, Vol. 52 ›› Issue (6): 120-127.doi: 10.12141/j.issn.1000-565X.220728

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

李松(), 王赫, 张丽平

哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080

收稿日期:2022-11-03 出版日期:2024-06-25 发布日期:2023-11-08
作者简介:李松（1977—），男，博士，教授，主要从事空间数据库研究。E-mail： lisongbeifen@163.com
基金资助:
国家自然科学基金资助项目(62072136);黑龙江省自然科学基金资助项目(LH2023F031);国家重点研发计划项目(2020YFB1710200)

Differential Privacy-Based skyline Query in Road Network Environment

LI Song(), WANG He, ZHANG Liping

School of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，Heilongjiang，China

Received:2022-11-03 Online:2024-06-25 Published:2023-11-08
About author:李松（1977—），男，博士，教授，主要从事空间数据库研究。E-mail： lisongbeifen@163.com
Supported by:
the National Natural Science Foundation of China(62072136);the Natural Science Foundation of Heilongjiang Province(LH2023F031);the National Key Research and Development Program of China(2020YFB1710200)

摘要/Abstract

摘要：

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

关键词: 路网环境, skyline查询, 网格索引扩展树, 差分隐私, 噪声机制

Abstract:

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.

Key words: road network environment, skyline query, grid-indexed extended tree, differential privacy, noise mechanism

中图分类号:

TP393.1

李松, 王赫, 张丽平. 基于差分隐私的路网环境skyline查询[J]. 华南理工大学学报(自然科学版), 2024, 52(6): 120-127.

LI Song, WANG He, ZHANG Liping. Differential Privacy-Based skyline Query in Road Network Environment[J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(6): 120-127.

图/表 13

表1

图1

图2

图3

表2

表3

表4

对象表"

o	g（m，n）	e	（价格，等级）	支配对象集
o₁	g（1，1）	e₆	（100，3）	｛ $∅$ ｝
o₂	g（2，2）	e₁	（70，4）	｛o₁，o₃｝
o₃	g（2，2）	e₁	（80，3）	｛o₁｝
o₅	g（2，0）	e₁₇	（50，2）	｛ $∅$ ｝

表4

表5

图4

表6

表7

图5

图6

参考文献 19

1	BORZSONYI S， KOSSMANN D， STOCKER K ．The skyline operator［C］∥Proceedings of the 17th International Conference on Data Engineering．Heidelberg：IEEE，2001：421-430．
2	PAPADIAS D， TAO Y， FU G，et al ．Progressive skyline computation in database systems［J］．ACM Tran-sactions on Database Systems，2005，30（1）：41-82．
3	SHARIFZADEH M， SHAHABI C ．The spatial skyline queries［C］∥Proceedings of the 32nd International Conference on Very Large Data Bases．Seoul：VLDB，2006：751-762．
4	SON W， HWANG S W， AHN H K ．MSSQ：Manhattan spatial skyline queries［J］．Information Systems，2014，40：67-83．
5	DENG K， ZHOU X， SHEN H T ．Multi-source skyline query processing in road networks［C］∥Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering．Istanbul：IEEE，2007：796-805．
6	CAI Z， CUI X， SU X，et al ．Continuous road network-based skyline query for moving objects［J］．IEEE Transactions on Intelligent Transportation Systems，2020，22（12）：7383-7394．
7	ZHENG J， JIANG S， CHEN J，et al ．Dynamic skyline maintaining strategies for moving query points in road networks［J］．Journal of Internet Technology，2019，20（5）：1359-1369．
8	李松，窦雅男，郝晓红，等．道路网环境下K-支配空间Skyline查询方法［J］．计算机研究与发展，2020，57（1）：227-239．
	LI Song， DOU Yanan， HAO Xiaohong，et al ．The method of the K-dominant space skyline query in road network［J］．Journal of Computer Research and Development，2020，57（1）：227-239．
9	CHOI J H， HAO F， KIM Y S，et al ．Optimization of dominance testing in skyline queries using decision trees［J］．IEEE Access，2021，9：130170-130184．
10	PAPADIAS D， TAO Y， FU G，et al ．An optimal and progressive algorithm for skyline queries［C］∥Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data．San Diego：ACM，2003：467-478．
11	CAI Z， CUI X， SU X，et al ．Speed and direction aware skyline query for moving objects［J］．IEEE Transactions on Intelligent Transportation Systems，2022，23（4）：300-311．
12	李松，王冠群，郝晓红，等．面向推荐系统的多目标决策优化算法［J］．西安交通大学学报，2022，56（8）：104-112．
	LI Song， WANG Guanqun， HAO Xiaohong，et al ．A multi-objective decision optimization algorithm for recommendation system［J］．Journal of Xi’an Jiaotong University，2022，56（8）：104-112．
13	古万荣，谢贤芬，张子烨，等．面向非随机缺失数据的协同过滤评分方法［J］．华南理工大学学报（自然科学版），2021，49（1）：47-57．
	GU Wanrong， XIE Xianfen， ZHANG Ziye，et al ．Collaborative score prediction method for non-random missing data［J］．Journal of South China University of Technology （Natural Science Edition），2021，49（1）：47-57．
14	FU X， MIAO X， XU J，et al ．Continuous range-based skyline queries in road networks［J］．World Wide Web，2017，20（6）：1443-1467．
15	LI C， GU Y， QI J，et al ．SkyCell：a space-pruning based parallel skyline algorithm［J/OL］．（2021-07-21）［2022-10-08］．．
16	DWORK C ．Differential privacy［C］∥Proceedings of the 33rd International Conference on Automata，Languages and Programming - Volume Part II．Berlin：Springer，2006：1-12．
17	XU J， ZHANG Z， XIAO X，et al ．Differentially private histogram publication［J］．The VLDB Journal，2013，22（6）：797-822．
18	ZENG C， NAUGHTON J F， CAI J Y ．On differentially private frequent itemset mining［J］．Proceedings of the VLDB Endowment，2012，6（1）：25-36．
19	YUAN G， ZHANG Z， WINSLETT M，et al ．Low-rank mechanism：optimizing batch queries under differential privacy［J/OL］．（2012-12-11）［2022-10-08］．．

数据点	距离/km	价格/元		距离/km	价格/元
p₁	4	400	p₇	8	260
p₂	30	390	p₈	34	20
p₃	24	380	p₉	20	210
p₄	14	340	p₁₀	40	200
p₅	36	300	p₁₁	28	120
p₆	26	280	p₁₂	16	60

e	n_i	n_j	g（m，n）	路网距离
e₁	n₁	n₂	g（2，2）	30
e₂	n₁	n₅	g（2，1）	15
e₅	n₅	n₄	g（2，2）	15
e₆	n₁	n₆	g（3，1）	33
e₁₀	n₅	n₁₀	g（3，0）	40
e₁₇	n₅	n₁₁	g（2，0）	15

n_i	g（m，n）
n₁	g（2，1）
n₅	g（2，1）

数据点数量	查询时间/ms
数据点数量	BSS算法	DPRS算法	SSI算法
500	5.82	0.91	0.76
1 000	42.58	1.76	0.89
1 500	61.45	3.11	1.06
2 000	85.70	5.67	2.36
2 500	283.65	7.32	4.61
3 000	721.62	8.67	7.17

数据集大小/10³	CPU运行时间/s
数据集大小/10³	Cd_ε -SQ算法	SkyCell算法	DPRS算法
10	5.21	3.82	2.86
50	14.25	7.21	5.27
100	23.86	12.54	10.12
150	28.27	17.23	15.14
200	34.48	21.10	19.33

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

Differential Privacy-Based skyline Query in Road Network Environment

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 19

相关文章 0

编辑推荐

Metrics

本文评价

对象数量/10³	访问的单元格数量
对象数量/10³	Cd_ε -SQ算法	SkyCell算法	DPRS算法
50	166	51	34
100	180	50	34
150	166	50	38
200	174	46	33
250	174	50	33