计算机科学 ›› 2018, Vol. 45 ›› Issue (11): 210-219.doi: 10.11896/j.issn.1002-137X.2018.11.033

• 软件与数据库技术 • 上一篇    下一篇

方向感知的路网移动对象范围查询算法

董天阳, 尚跃辉, 程强   

  1. (浙江工业大学计算机科学与技术学院 杭州310023)
  • 收稿日期:2017-11-22 发布日期:2019-02-25
  • 作者简介:董天阳(1977-),男,博士,副教授,CCF会员,主要研究方向为虚拟现实、大数据与人工智能,E-mail:dty@zjut.edu.cn(通信作者);尚跃辉(1992-),女,硕士生,CCF会员,主要研究方向为智能交通、空间数据库,E-mail:18758594584@163.com;程 强(1990-),男,硕士生,主要研究方向为智能交通、数据挖掘。
  • 基金资助:
    本文受国家自然科学基金项目(61672464,61572437),浙江省重点研发计划项目(2017C01013)资助。

Direction-aware Moving Object Range Query Algorithm in Road Network

DONG Tian-yang, SHANG Yue-hui, CHENG Qiang   

  1. (School of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)
  • Received:2017-11-22 Published:2019-02-25

摘要: 路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。

关键词: 范围查询, 方向感知, 路网, 移动对象

Abstract: The range query on moving objects in road network is one of the classical query methods in spatial query processing,which has been widely used in many fields.However,there are still some shortcomings in the existing moving object range query methods in road networks.On the one hand,most of them only consider the network distance,but pay less attention to the movement direction of moving objects in road networks.On the other hand,a few query me-thods considering the movement direction are based on Euclidean space and can’t not be applied to large-scale road network to determine whether moving objects move toward query point.Aiming at the problem of accurately and efficiently finding moving objects toward the query point in large and complex road network,this paper proposed a direction-aware moving object range query algorithm in road network.In this method,R-tree and simple grid are taking as underlying index support,and an efficient determination method of moving object toward query point in road network is exploited,so as to efficiently query the moving object toward query point.At last,this paper designed experiments in terms of the query range,the number of moving object and the number of grid partition to evaluate the performance of the proposed algorithm.The experimental results show that the algorithm can achieve good query performance even in the case of large-scale complex road network under the condition that the index configuration is reasonable.

Key words: Direction-aware, Moving object, Range query, Road network

中图分类号: 

  • TP392
[1]GUTTMAN A.R-trees:a dynamic index structure for spatial searching[C]∥International Conference on Management of Data.1984:47-57.
[2]SELLIS T,ROUSSOPOULOS N,FALOUTSOS C,et al.The R+-Tree:A Dynamic Index for Multi-Dimensional Objects[C]∥International Conference on Very Large Data Bases.1987:507-518.
[3]BECKMANN N,KRIEGEL H,SCHNEIDER R,et al.The R*-tree:an efficient and robust access method for points and rectangles[J].ACM Sigimod Record,1990,19(2):322-331.
[4]KAMEL I,FALOUTSOS C.Hilbert R-tree:An Improved R-tree using Fractals[C]∥International Conference onVery Large Data Bases.1994:500-509.
[5]ARGE L,DE BERG M,HAVERKORT H J,et al.The Priority R-Tree:A Practically Efficient and Worst-Case-Optimal R-Tree[C]∥Proceedings of SIGMOD International Conference on Management of Data.2004:347-358.
[6]KORN F,SIDIROPOULOS N,FALOUTSOS C,et al.Fast Nearest Neighbor Search in Medical Image Databases[C]∥International Conference on Very Large Data Bases.1996:215-226.
[7]BERCHTOLD S,ERTL B,KEIM D A,et al.Fast nearest neighbor search in high-dimensional space[C]∥InternationalConfe-rence on Data Engineering.1998:209-218.
[8]ZHENG B,LEE D L.Semantic Caching in Location-Dependent Query Processing[C]∥Symposium on Large Spatial Databases.2001:97-113.
[9]SHARIFZADEH M,SHAHABI C.VoR-Tree:R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries[C]∥Proceedings of the Vldb Endowment.2010:1231-1242.
[10]JENSEN C S,LIN D,OOI B C.Query and update efficient B+-tree based indexing of moving objects[C]∥Proceedings of the Thirtieth International Conference on Very Large Data.2004:768-779.
[11]PAPADIAS D,ZHANG J,MAMOULIS N,et al.Query Pro- cessing in Spatial Network Databases[J].Vldb,2003,29:802--813.
[12]KOLAHDOUZAN M,SHAHABI C.Voronoi-based k nearest neighbor search for spatial network databases[C]∥Proceedings of the ThirtiethInternational Conference on Very Large Data Bases.2004:840-851.
[13]HUANG X,JENSEN C S,šALTENIS S.The Islands Approach to Nearest Neighbor Querying in Spatial Networks[C]∥International Conference on Lecture Notes in Computer Science.2006,3633:73-90.
[14]HUANG X,JENSEN C S,LU H,et al.S-GRID:A versatile approach to efficient query processing in spatial networks[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2007:93-111.
[15]HONG S,CHANG J.A new k-NN query processing algorithm based on multicasting-based cell expansion in location-based services[J].Journal of Convergence,2013,4(4):1-6.
[16]WANG H,ZIMMERMANN R.Location-based query processing on moving objects in road networks[C]∥Proceedings ofInternational Conference on Very Large Data Bases (VLDB 2007).2007:321-332.
[17]PATROUMPAS K,SELLIS T.Monitoring Orientation of Mo- ving Objects around Focal Points[C]∥Symposium on Large Spatial Databases.2009:228-246.
[18]LI G,FENG J,XU J.Desks:Direction-aware spatial keyword search[C]∥IEEE 28th International Conference on Data Engineering (ICDE).2012:474-485.
[19]YI S,RYU H,SON J,et al.View field nearest neighbor:A novel type of spatial queries[J].Information Sciences,2014,275(3):68-82.
[20]LEE M J,CHOI D W,KIM S Y,et al.The direction-constrained k nearest neighbor query[J].GeoInformatica,2016,20(3):471-502.
[21]LU B L,CUI X Y,LIU N.Bichromatic Reverse Nearest k Neighbor Query Processing on Road Network[J].Journal of Chinese Mini-Micro Computer Systems,2015,36(2):266-270.(in Chinese)
卢秉亮,崔晓玉,刘娜.路网中双色反向k近邻查询处理[J].小型微型计算机系统,2015,36(2):266-270.
[22]LEE K W,CHOI D W,CHUNG C W.Dart:An efficient method for direction-aware bichromatic reverse k nearest neighbor queries[M]∥Advances in Spatial and Temporal Databases.Sprin-ger Berlin Heidelberg,2013:295-311.
[23]LI G L,FENG J H,XU J.DESKS:Direction-aware spatial keyword search[C]∥2012 IEEE 28th International Conference on Data Engineering.Washington:IEEE,2012:474-485.
[24]BRINKHOFF T.A framework for generating network-based moving objects[J].GeoInformatica,2002,6(2):153-180.
[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] 李冰荣, 皮德常, 候梦如.
基于CNN和LSTM的移动对象目的地预测
Destination Prediction of Moving Objects Based on Convolutional Neural Networks and Long-Short Term Memory
计算机科学, 2021, 48(4): 70-77. https://doi.org/10.11896/jsjkx.200200024
[3] 刘泽邦, 陈荦, 杨岸然, 李思捷.
面向矢量线数据的直线形状空间检索方法
Space Retrieval Method to Retrieve Straight Line for Vector Line Data
计算机科学, 2021, 48(11A): 117-123. https://doi.org/10.11896/jsjkx.210100084
[4] 熊亭, 戚湧, 张伟斌.
基于DCGRU-RF模型的路网短时交通流预测
Short-term Traffic Flow Prediction Based on DCGRU-RF Model for Road Network
计算机科学, 2020, 47(5): 84-89. https://doi.org/10.11896/jsjkx.190100213
[5] 韩京宇, 许梦婕, 朱曼.
路网上基于时空锚点的移动对象群体和个体运动监测方法
Detecting Group-and-individual Movements of Moving Objects Based on Spatial-Temporal Anchors of Road-network
计算机科学, 2020, 47(11): 294-303. https://doi.org/10.11896/jsjkx.191100083
[6] 阮子瑞,阮中远,沈国江.
基于交通路网的TASEP模型的扩展研究
Study of TASEP Model Based on Road Networks
计算机科学, 2020, 47(1): 265-269. https://doi.org/10.11896/jsjkx.181202418
[7] 张彤,秦小麟.
时间依赖路网上的移动对象K近邻查询算法
K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks
计算机科学, 2020, 47(1): 79-86. https://doi.org/10.11896/jsjkx.181102231
[8] 周剑刚, 秦小麟, 张珂珩, 许建秋.
基于道路网的多移动用户动态Skyline查询
Dynamic Skyline Query for Multiple Mobile Users Based on Road Network
计算机科学, 2019, 46(9): 73-78. https://doi.org/10.11896/j.issn.1002-137X.2019.09.009
[9] 孙中锋, 王静.
用于基于方面情感分析的RCNN-BGRU-HN网络模型
RCNN-BGRU-HN Network Model for Aspect-based Sentiment Analysis
计算机科学, 2019, 46(9): 223-228. https://doi.org/10.11896/j.issn.1002-137X.2019.09.033
[10] 徐哲, 刘亮, 秦小麟, 秦伟萌.
带关系属性的空间关键词并行查询处理算法
Distributed Spatial Keyword Query Processing Algorithm with Relational Attributes
计算机科学, 2019, 46(6A): 402-406.
[11] 李佳佳, 沈盼盼, 夏秀峰, 刘向宇.
时间依赖路网中反向 k近邻查询
Reverse k Nearest Neighbor Queries in Time-dependent Road Networks
计算机科学, 2019, 46(1): 232-237. https://doi.org/10.11896/j.issn.1002-137X.2019.01.036
[12] 张怀峰, 皮德常, 董玉兰.
iBTC:一种基于独立森林的移动对象轨迹聚类算法
iBTC:A Trajectory Clustering Algorithm Based on Isolation Forest
计算机科学, 2019, 46(1): 251-259. https://doi.org/10.11896/j.issn.1002-137X.2019.01.039
[13] 王波涛,梁伟,赵凯利,钟汉辉,张玉圻.
基于HBase的支持频繁更新与多用户并发的R树
R-tree for Frequent Updates and Multi-user Concurrent Accesses Based on HBase
计算机科学, 2018, 45(7): 42-52. https://doi.org/10.11896/j.issn.1002-137X.2018.07.007
[14] 宫海彦,耿生玲.
复杂障碍空间中基于移动对象运动规律的不确定轨迹预测
Prediction of Uncertain Trajectory Based on Moving Object Motion in Complex Obstacle Space
计算机科学, 2018, 45(6A): 130-134.
[15] 郭帅,刘亮,秦小麟.
用户偏好约束的空间关键词范围查询处理方法
Spatial Keyword Range Query with User Preferences Constraint
计算机科学, 2018, 45(4): 182-189. https://doi.org/10.11896/j.issn.1002-137X.2018.04.031
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!