基于道路网的多移动用户动态Skyline查询

doi:10.11896/j.issn.1002-137X.2019.09.009

计算机科学 ›› 2019, Vol. 46 ›› Issue (9): 73-78.doi: 10.11896/j.issn.1002-137X.2019.09.009

所属专题：数据库技术

• 第35届中国数据库学术会议 • 上一篇下一篇

基于道路网的多移动用户动态Skyline查询

周剑刚¹, 秦小麟¹, 张珂珩², 许建秋¹

(南京航空航天大学计算机科学与技术学院南京210016)¹;
(南瑞集团有限公司南京210003)²

收稿日期:2018-07-10 出版日期:2019-09-15 发布日期:2019-09-02
通讯作者: 秦小麟(1953-),男,教授,博士生导师,主要研究方向为空间与时间数据库、分布式数据管理与安全等,E-mail:qinxcs@nuaa.edu.cn
作者简介:周剑刚(1993-),男,硕士,CCF会员,主要研究方向为移动对象数据库、分布式数据管理等,E-mail:jiangangzhou@nuaa.edu.cn;张珂珩(1973-),男,硕士,主要研究方向为数据库、大数据分析;许建秋(1982-),男,博士,副教授,主要研究方向为移动对象数据库、空间数据库技术等。
基金资助:
国家自然科学基金(61373015,61300052,61728204),国家电网公司总部科技资助项目

Dynamic Skyline Query for Multiple Mobile Users Based on Road Network

ZHOU Jian-gang¹, QIN Xiao-lin¹, ZHANG Ke-heng², XU Jian-qiu¹

(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)¹;
(NARI Group Corporation Limited Company,Nanjing 210003,China)²

Received:2018-07-10 Online:2019-09-15 Published:2019-09-02

摘要/Abstract

摘要： 随着无线通信和定位技术的发展,道路网Skyline查询在基于位置的服务等方面越来越重要。但现有的道路网Skyline研究所涉及的空间属性仅考虑距离,并未考虑多个移动用户位置和速度的变化对用户运动时间的影响,当用户运动状态发生变化时,需要动态地调整Skyline结果,进行重新规划。文中分析了用户运动状态与查询间的关联关系,提出了查询处理算法EI,将查询过程分为两步:1)根据时间,通过协同过滤扩展方法确定初始Skyline结果集,并对数据集进行剪枝;2)监测用户的运动状态,一旦用户速度发生变化,就快速根据出入点信息动态调整Skyline集。最后,在真实路网上对算法进行了实验,并将其与现有算法N3S和EDC进行了比较,结果表明EI算法可以高效解决基于道路网的多移动用户动态Skyline查询问题。

关键词: Skyline查询, 道路网, 关联关系, 运动状态

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

中图分类号:

TP311

周剑刚, 秦小麟, 张珂珩, 许建秋. 基于道路网的多移动用户动态Skyline查询[J]. 计算机科学, 2019, 46(9): 73-78. https://doi.org/10.11896/j.issn.1002-137X.2019.09.009

ZHOU Jian-gang, QIN Xiao-lin, ZHANG Ke-heng, XU Jian-qiu. Dynamic Skyline Query for Multiple Mobile Users Based on Road Network[J]. Computer Science, 2019, 46(9): 73-78. https://doi.org/10.11896/j.issn.1002-137X.2019.09.009

参考文献

[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.

相关文章 15

[1]	朱润泽, 秦小麟, 刘嘉琛. 基于查询对象的路网Skyline查询中Why-not问题的研究 Study on Why-not Problem in Skyline Query of Road Network Based on Query Object 计算机科学, 2021, 48(6): 57-62. https://doi.org/10.11896/jsjkx.200700016
[2]	王妍, 韩笑, 曾辉, 刘荆欣, 夏长清. 边缘计算环境下服务质量可信的任务迁移节点选择 Task Migration Node Selection with Reliable Service Quality in Edge Computing Environment 计算机科学, 2020, 47(10): 240-246. https://doi.org/10.11896/jsjkx.190900054
[3]	朱航江,朱帆,潘振福,朱永利. 运动状态与尺度估计的核相关目标跟踪方法 Visual Object Tracking Method with Motion Estimation and Scale Estimation 计算机科学, 2017, 44(Z11): 193-198. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.040
[4]	余未,郑吉平,王海翔,王永阁,陈嘉良,江顺青. 空间Skyline查询处理:应用、研究与挑战 Spatial Skyline Queries:Applications,Research and Challenges 计算机科学, 2017, 44(2): 1-16. https://doi.org/10.11896/j.issn.1002-137X.2017.02.001
[5]	梁莹莹,黄岚,王喆. 一种基于关联关系的有向网络关键节点挖掘算法 Key Nodes Mining Algorithm Based on Association with Directed Network 计算机科学, 2017, 44(12): 23-27. https://doi.org/10.11896/j.issn.1002-137X.2017.12.004
[6]	李青,肖迎元,王晓晔,李玉坤. 无线传感器网络中基于聚簇结构的Skyline查询方法 Clustering Architecture-based Skyline Query Processing in Wireless Sensor Networks 计算机科学, 2017, 44(10): 177-181. https://doi.org/10.11896/j.issn.1002-137X.2017.10.033
[7]	王宁任红伟. 网络表格间的快照关系发现 Detecting Snapshots for Web Tables 计算机科学, 2015, 42(7): 5-11. https://doi.org/10.11896/j.issn.1002-137X.2015.07.002
[8]	石林宾,余正涛,严馨,宋海霞,洪旭东. 基于半监督图聚类的项目主题模型构建方法 Project Topic Model Construction Based on Semi-supervised Graph Clustering 计算机科学, 2015, 42(5): 119-123. https://doi.org/10.11896/j.issn.1002-137X.2015.05.024
[9]	施常月,秦小麟,许建秋,胡彩平. 基于位置范围的道路网skyline查询 Location Range-based Skyline Query in Road Networks 计算机科学, 2014, 41(9): 190-195. https://doi.org/10.11896/j.issn.1002-137X.2014.09.036
[10]	闫林,宋金朋. 数据集的粒化树及其建模应用 Granular Trees Based on Different Data Sets and their Modeling Applications 计算机科学, 2014, 41(3): 258-262.
[11]	于雷,辛晓越,卢志泳,陈志鹏,刘宁. 基于SVM的人体运动状态检测 SVM-based Method and System for Recognition of Human Movement 计算机科学, 2013, 40(Z6): 166-168.
[12]	王海翔,郑吉平,宋保利. 无线传感器网络中的Skyline查询处理技术 Skyline Query Processing in Wireless Sensor Networks 计算机科学, 2013, 40(8): 14-23.
[13]	汤志俊,樊明锁,何贤芒,陈华辉,董一鸿. 位置不确定移动对象的连续概率反Skyline查询 Continuous Probabilistic Reverse Skyline Query on Moving Objects with Uncertainty 计算机科学, 2013, 40(7): 147-152.
[14]	赵平,马春光,高训兵,朱蔚. 路网环境下基于Voronoi图的位置隐私保护方法 Protecting Location Privacy with Voronoi Diagram over Road Networks 计算机科学, 2013, 40(7): 116-120.
[15]	付世昌，董一鸿，陈华辉，钱江波. 基于道路网络不确定移动对象的连续概率Skyline查询 Continuous Probabilistic Skyline Queries Based on Road Network for Uncertain Moving Object 计算机科学, 2011, 38(7): 152-156.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于道路网的多移动用户动态Skyline查询

Dynamic Skyline Query for Multiple Mobile Users Based on Road Network

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0