Differential Privacy-Based skyline Query in Road Network Environment

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

Abstract

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

CLC Number:

TP393.1

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.

Figures/Tables 13

Table 1

Fig.1

Fig.2

Fig.3

Table 2

Table 3

Table 4

Object table"

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）	｛ $∅$ ｝

Table 4

Table 5

Fig.4

Table 6

Table 7

Fig.5

Fig.6

References 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