Research on Location-based Skyline Queries Processing in Road Network

doi:10.19678/j.issn.1000-3428.0060559

Abstract

Abstract: Location-based skyline queries can quickly return the expected information from massive data according to the user's needs and the user's location.However, the existing road network technologies require enormous calculations of road network distance and dominant relations between data points, which reduces the query efficiency.To solve the problem, an algorithm named DSR for inverted index query is proposed based on road network data points.The algorithm can get the final result by calculating the road network distance of a small number of data points, which greatly reduces the cost of calculating road network distance.The determination of the dominant relations between data points is also accelerated, and the query efficiency is improved.On this basis, the dynamic maintenance of the algorithm in the case of data point update is given.DSR can quickly calculate Skyline set only by maintaining a small amount of data.The experimental results show that compared with SSI, BSS and other algorithms, this algorithm displays higher query efficiency, and its performance grows with the data size.

Key words: Skyline query, road network, data point update, inverted index, query processing

摘要： 基于位置的路网Skyline查询可根据用户的需求及用户所处的位置，从大量数据中快速返回给用户期望的数据，但已有的道路网络技术需要计算大量的路网距离及数据点间支配关系的运算，导致查询效率较低。提出一种基于路网数据点的倒排索引查询算法DSR。通过计算少量数据点的路网距离求得最终结果，减小路网距离计算的代价，从而加快数据点间支配关系的判定，提升查询效率。在此基础上，在数据点更新情况下给出算法的动态维护，仅通过维护少量数据，DSR即可以快速地计算出Skyline集合。实验结果表明，与SSI、BSS等算法相比，该算法具有较高的查询效率，且时间性能明显提升。

关键词: Skyline查询, 路网, 数据点更新, 倒排索引, 查询处理

CLC Number:

TP391

BAI Mei, CHANG Shihan, WANG Xite. Research on Location-based Skyline Queries Processing in Road Network[J]. Computer Engineering, 2022, 48(1): 127-134.

白梅, 苌仕涵, 王习特. 基于位置的路网Skyline查询处理研究[J]. 计算机工程, 2022, 48(1): 127-134.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0060559

http://www.ecice06.com/EN/Y2022/V48/I1/127

Figures/Tables 11

References

[1] HUANG Y K, CHANG C, LEE C.Continuous distance-based Skyline queries in road networks[J].Pergamon, 2012, 37(7):611-613.
[2] SAFAR M, EL-AMIN D, TANIAR D.Optimized Skyline queries on road networks using nearest neighbors[J].Personal and Ubiquitous Computing, 2011, 15(8):845-856.
[3] 李松, 窦雅男, 郝晓红, 等.道路网环境下K-支配空间Skyline查询方法[J].计算机研究与发展, 2020, 57(1):227-239. LI S, DOU Y N, ZHANG X H, et al.K-domination space Skyline query method in road network environment[J].Computer Research and Development, 2020, 57(1):227-239.(in Chinese)
[4] CHOMICKI J, GODFREY P, GRYZ J, et al.Skyline with presorting[EB/OL].[2020-12-10].https://www.researchgate.net/publication/4053418.
[5] 董雷刚, 刘国华.组合Skyline的求解与更新算法[J].计算机工程, 2017, 43(6):195-201, 206. DONG L G, LIU G H.Solving and updating algorithm of combined Skyline[J].Computer Engineering, 2017, 43(6):195-201, 206.(in Chinese)
[6] LI Q Y, ZHU Y Y.Skyline cohesive group queries in large road-social networks[C]//Proceedings of the 36th IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2020:397-408.
[7] DENG K, ZHOU X F, SHEN H T.Multi-source Skyline query processing in road networks[C]//Proceedings of the 23rd IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2011:796-805.
[8] MIAO X Y, GAO Y J, GAO S, et al.On efficiently answering why-not range-based Skyline queries in road networks[J].IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9):1697-1711.
[9] 李佳佳, 臧寅旭, 刘向宇, 等.面向时间依赖路网的空间索引方法[J].计算机工程, 2019, 45(5):127-134. LI J J, ZANG Y X, LIU X Y, et al.Spatial index method for time-dependent road network[J].Computer Engineering, 2019, 45(5):127-134.(in Chinese)
[10] HUANG Z Y, LU H.Continuous Skyline queries for moving objects[J].IEEE Transactions on Knowledge and Data Engineering, 2006, 18(12):1645-1658.
[11] LI R H, QIN L, YE F H, et al.Finding Skyline communities in multi-valued networks[J].The VLDB Journal, 2020, 29(6):1407-1432.
[12] LI R, YU J X, MAO R.Efficient core maintenance in large dynamic graphs[J].IEEE Transactions on Knowledge and Data Engineering, 2014, 26(10):2453-2465.
[13] LIN X, XU J L, HU H B.Range-based Skyline queries in mobile environments[J].IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4):835-849.
[14] 周剑刚, 秦小麟, 张珂珩, 等.基于道路网多移动用户动态Skyline查询[J].计算机科学, 2019, 46(9):73-78. ZHOU J G, QIN X L, ZHANG K Y, et al.Dynamic Skyline query of multiple mobile users based on road network[J].Computer Science, 2019, 46(9):73-78.(in Chinese)
[15] XU J L, TANG X Y, HU H B, et al.Privacy-conscious location-based queries in mobile environments[J].IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3):313-326.
[16] TAO Y, PAPADIAS D.Maintaining sliding window Skylines on data streams[J].IEEE Transactions on Knowledge and Data Engineering, 2006, 18(3):377-391.
[17] HUANG Y K, KAINZ W.Within Skyline query processing in dynamic road networks[J].ISPRS International Journal of Geo-Information, 2017, 6(5):137-150.
[18] LIU B, CHAN C Y.ZINC:efficient indexing for Skyline computation[J].Proceedings of the VLDB Endowment, 2010, 4(3):197-207.
[19] ZHONG R, LI G, TAN K L, et al.G-Tree:an efficient and scalable index for spatial search on road networks[J].IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8):2175-2189.

Please choose a citation manager

Content to export