Journal of South China University of Technology(Natural Science) >
Differential Privacy-Based skyline Query in Road Network Environment
Received date: 2022-11-03
Online published: 2023-11-08
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)
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.
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), 2024 , 52(6) : 120 -127 . DOI: 10.12141/j.issn.1000-565X.220728
| 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]. . |
/
| 〈 |
|
〉 |