计算机科学 ›› 2018, Vol. 45 ›› Issue (11): 210-219.doi: 10.11896/j.issn.1002-137X.2018.11.033
董天阳, 尚跃辉, 程强
DONG Tian-yang, SHANG Yue-hui, CHENG Qiang
摘要: 路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。
中图分类号:
[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 |
|