Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (9): 73-78.doi: 10.11896/j.issn.1002-137X.2019.09.009

Special Issue: Database Technology

• NDBC 2018 • Previous Articles     Next Articles

Dynamic Skyline Query for Multiple Mobile Users Based on Road Network

ZHOU Jian-gang1, QIN Xiao-lin1, ZHANG Ke-heng2, XU Jian-qiu1   

  1. (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)1;
    (NARI Group Corporation Limited Company,Nanjing 210003,China)2
  • Received:2018-07-10 Online:2019-09-15 Published:2019-09-02

PDF (PC)

969

Abstract: With the development of wireless communication and positioning technology,the road network Skyline query has become increasingly important in location-based services.However,the spatial attributes involved in the existing road network Skyline research only consider distance,and do not consider the influence of changes in the positions and speeds of multiple mobile users on the user’s movement time.When the user’s movement state is changed,the Skyline results need to be dynamically adjusted and re-planned.This paper analyzed the incidence relation between the user’s motion state and the query,proposed the query processing algorithm EI,and divided the query process into two steps.Firstly,the initial Skyline result set is determined by the collaborative filtering extension method according to time,and the data set is pruned.The user’s movement status,as soon as the user’s speed changes,quickly adjusts the Skyline set according to the entry point.Finally,the algorithm is tested on the real road network,and is compared with the existing algorithms N3S and EDC.The results show that EI algorithm can efficiently solve the dynamic Skyline query problem of multiple mobile users based on road network.

Key words: Incidence relation, Motion state, Road network, Skyline query

CLC Number: 

  • TP311
[1]BORZSONYI S,STOCKER K,KOSSMANN D.The SkylineOperator[C]//Proceedings 17th International Conference on Data Engineering.2001:421-430.
[2]CHOMICKI J,GODFREY P,GRYZ J,et al.Skyline with presorting[C]//International Conference on Data Engineering.IEEE,2004.
[3]PAPADIAS D.An Optimal and Progressive Algorithm for Skyline Queries[C]//Acm Sigmod International Conference on Management of Data.ACM,2003.
[4]SHARIFZADEH M,SHAHABI C.The Spatial Skyline Que-ries[C]//International Conference on Very Large Data Bases.DBLP,2006.
[5]SHARIFZADEH M,SHAHABI C,KAZEMI L.Processing spatial Skyline queries in both vector spaces and spatial network databases[J].Acm Transactions on Database Systems,2009,34(3):1-45.
[6]DENG K,ZHOU X,SHEN H T.Multi-source Skyline QueryProcessing in Road Networks[C]//IEEE 23rd International Conference on Data Engineering,2007(ICDE 2007).IEEE,2007.
[7]BRINKHOFF T.A Framework for Generating Network-Based Moving Objects[J].Geoinformatica,2002,6(2):153-180.
[8]ENDRES M.A Survey on Selectivity Estimation for Preference Database Queries[J].Databases and Information Systems,2014,270(8):159-172.
[9]KUNG H T,LUCCIO F,PREPARATA F P.On Finding the Maxima of a Set of Vectors[J].Journal of the Association for Computing Machinery,1975,22(4):469-476.
[10]WANG Y,SHI Z,WANG J,et al.Skyline Preference QueryBased on Massive and Incomplete Dataset[J].IEEE Access,2017,5(99):3183-3192.
[11]LIN X,YUAN Y,WANG W,et al.Stabbing the sky:efficient skyline computation over sliding windows[C]//International Conference on Data Engineering.IEEE,2005.
[12]CHEEMA M,LIN X,ZHANG W,et al.A safe zone based approach for monitoring moving skyline queries[C]//International Conference on Extending Database Technology.2013.
[13]JIANG S,ZHENG J,CHEN J,et al.Efficient Computation of Continuous Range Skyline Queries in Road Networks//Intelligent Computing Methodologies.Springer International Publishing,2016:520-532.
[14]GENG M,AREFIN M S,MORIMOTO Y.A Spatial Skyline Query for a Group of Users Having Different Positions[J].Journal of Software,2014,9(11):137-142.
[15]SON W,HWANG S W,AHN H K.MSSQ:Manhattan spatial skyline queries[C]//International Symposium on Spatial & Temporal Databases.Springer,Berlin,Heidelberg,2011.
[16]SAFAR M,EL-AMIN D,TANIAR D.Optimized Skyline que-ries on road networks using nearest neighbors[J].Personal & Ubiquitous Computing,2011,15(8):845-856.
[17]JANG S,YOO J.Processing Continuous Skyline Queries inRoad Networks[C]//International Symposium on Computer Science and ITS Applications.IEEE,2008:353-356.
[18]ZHENG B,LEE K C K,LEE W C.Location-Dependent Skyline Query[J].Mdm,2008:148-155.
[19]HUANG Y K,CHANG C H,LEE C.Continuous distance-based Skyline queries in road networks[J].Information Systems,2012,37(7):611-633.
[20]BRINKOFF T.Generating Traffic Data[J].Bulletin of theTechnical Committee on Data Engineering IEEE Computer So-ciety,2003,26:2003.
[1] ZHU Run-ze, QIN Xiao-lin, LIU Jia-chen. Study on Why-not Problem in Skyline Query of Road Network Based on Query Object [J]. Computer Science, 2021, 48(6): 57-62.
[2] LIU Ze-bang, CHEN Luo, YANG An-ran, LI Si-jie. Space Retrieval Method to Retrieve Straight Line for Vector Line Data [J]. Computer Science, 2021, 48(11A): 117-123.
[3] XIONG Ting, QI Yong, ZHANG Wei-bin. Short-term Traffic Flow Prediction Based on DCGRU-RF Model for Road Network [J]. Computer Science, 2020, 47(5): 84-89.
[4] WANG Yan, HAN Xiao, ZENG Hui, LIU Jing-xin, XIA Chang-qing. Task Migration Node Selection with Reliable Service Quality in Edge Computing Environment [J]. Computer Science, 2020, 47(10): 240-246.
[5] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[6] ZHANG Tong,QIN Xiao-lin. K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks [J]. Computer Science, 2020, 47(1): 79-86.
[7] LI Jia-jia, SHEN Pan-pan, XIA Xiu-feng, LIU Xiang-yu. Reverse k Nearest Neighbor Queries in Time-dependent Road Networks [J]. Computer Science, 2019, 46(1): 232-237.
[8] MAO Ying-chi and CHEN Yang. Uncertain Vehicle Intersection Trajectory Prediction [J]. Computer Science, 2018, 45(3): 235-240.
[9] DONG Tian-yang, SHANG Yue-hui, CHENG Qiang. Direction-aware Moving Object Range Query Algorithm in Road Network [J]. Computer Science, 2018, 45(11): 210-219.
[10] ZHU Hang-jiang, ZHU Fan, PAN Zhen-fu and ZHU Yong-li. Visual Object Tracking Method with Motion Estimation and Scale Estimation [J]. Computer Science, 2017, 44(Z11): 193-198.
[11] YU Wei, ZHENG Ji-ping, WANG Hai-xiang, WANG Yong-ge, CHEN Jia-liang and JIANG Shun-qing. Spatial Skyline Queries:Applications,Research and Challenges [J]. Computer Science, 2017, 44(2): 1-16.
[12] LI Qing, XIAO Ying-yuan, WANG Xiao-ye and LI Yu-kun. Clustering Architecture-based Skyline Query Processing in Wireless Sensor Networks [J]. Computer Science, 2017, 44(10): 177-181.
[13] DAI Jia-zhu and HUA Liang. Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks [J]. Computer Science, 2016, 43(3): 137-144.
[14] YANG Xu-hua and ZHOU Shi-jie. Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting [J]. Computer Science, 2015, 42(Z6): 285-289.
[15] ZHANG Li-ping, JING Hai-dong, LI Song and CUI Huan-yu. Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network [J]. Computer Science, 2015, 42(8): 231-235.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.