留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向分布式列式存储的轨迹大数据k近邻查询

余列冰 向隆刚 孙尚宇 关雪峰 吴华意

余列冰, 向隆刚, 孙尚宇, 关雪峰, 吴华意. 面向分布式列式存储的轨迹大数据k近邻查询[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
引用本文: 余列冰, 向隆刚, 孙尚宇, 关雪峰, 吴华意. 面向分布式列式存储的轨迹大数据k近邻查询[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
YU Liebing, XIANG Longgang, SUN Shangyu, GUAN Xuefeng, WU Huayi. kNN Query Processing for Trajectory Big Data Based on Distributed Column-Oriented Storage[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
Citation: YU Liebing, XIANG Longgang, SUN Shangyu, GUAN Xuefeng, WU Huayi. kNN Query Processing for Trajectory Big Data Based on Distributed Column-Oriented Storage[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136

面向分布式列式存储的轨迹大数据k近邻查询

doi: 10.13203/j.whugis20200136
基金项目: 

国家重点研发计划 2018YFB2100603

国家自然科学基金 41771474

国家自然科学基金 41930107

详细信息

kNN Query Processing for Trajectory Big Data Based on Distributed Column-Oriented Storage

Funds: 

The National Key Research and Development Program of China 2018YFB2100603

the National Natural Science Foundation of China 41771474

the National Natural Science Foundation of China 41930107

More Information
  • 摘要: 针对轨迹大数据的高效点-轨迹k近邻(point to trajectory k nearest neighbor, P2T_kNN)查询处理需求,提出了一种融合时空剖分和轨迹分段的轨迹组织方法,其核心思想是在对轨迹作时间剖分的基础上,利用离散全球网格系统(discrete global grid system, DGGS)在空间上进行再次剖分,从而利用两次剖分得到的时空单元编码来索引落入其中的轨迹片段。在此基础上利用分布式列式存储技术设计了面向轨迹大数据的P2T_kNN查询处理框架,提出了一种顾及轨迹数据空间分布的自适应空间单元搜索算法,即通过分析轨迹数据在给定时间约束下的空间分异特征,动态调整空间单元的搜索步长,从而提升了轨迹稀疏区域的处理效率。针对亿级轨迹的实验结果表明,该方法适用于轨迹大数据的P2T_kNN查询处理,在轨迹稠密与稀疏区域的平均查询响应时间均小于1 s。
  • 图  1  P2T_kNN查询处理框架

    Figure  1.  Framework of P2T_kNN Query Processing

    图  2  轨迹数据时空分段组织及分布式存储

    Figure  2.  Spatiotemporal Segmentation Organization and Distributed Storage of Trajectory Data

    图  3  时空串接编码结构

    Figure  3.  Structure of Spatiotemporal Concatenated Encoding

    图  4  获取给定空间单元的8个相邻空间单元

    Figure  4.  8 Adjacent Spatial Cells of a Specific Spatial Cell

    图  5  由时空范围获取索引表对应的行键区间集合

    Figure  5.  Row Key Range Set Corresponding to Index Table from Spatiotemporal Range

    图  6  k为3时不同步长空间单元的搜索过程

    Figure  6.  Searching Process of Asynchronous Step Size When k Is 3

    图  7  不同时间约束下的P2T_kNN查询实验

    Figure  7.  P2T_kNN Query Experiments Under Different Time Constraints

    图  8  时间约束为1 d的查询对比实验

    Figure  8.  Query Comparison Experiment with Time Constraint of 1 d

    图  9  k值为10且k率为1时的查询耗时分布图

    Figure  9.  Distribution of Query Time When k Value Is 10 and k Rate Is 1

    图  10  不同k率下的查询耗时

    Figure  10.  Query Time at Different k Rates

    表  1  近邻查询相关工作比较

    Table  1.   Comparison Between Related Works on Nearest Neighbor Query

    统计项 输入 输出 扩展性 时空支持 平台
    P2T_kNN 时间约束、空间点 Top-k近邻轨迹 可扩展 时空 NoSQL
    文献[7-8] 空间点 Top-k近邻轨迹 不可扩展 空间 单机
    MD-HBase[10-11]、G-HBase[12] 空间点 Top-k近邻点 可扩展 空间 NoSQL
    GeoMesa[14-15]、GeoWave[16-17] 时间范围、空间点 Top-k近邻点 可扩展 时空 NoSQL
    THBase[19] 时间范围、空间点 Top-k近邻轨迹 可扩展 时空 NoSQL
    下载: 导出CSV
  • [1] 高强, 张凤荔, 王瑞锦, 等. 轨迹大数据: 数据处理关键技术研究综述[J]. 软件学报, 2017, 28(4): 959-992 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201704015.htm

    Gao Qiang, Zhang Fengli, Wang Ruijin, et al. Trajectory Big Data: A Review of Key Technologies in Data Processing[J]. Journal of Software, 2017, 28(4): 959-992 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201704015.htm
    [2] Zheng Y. Trajectory Data Mining: An Overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 1-41 http://pure.ltu.se/portal/en/publications/trajectory-data-mining(47e55f7e-db63-4ee4-a2a8-917c82999856)/export.html
    [3] 李德仁, 邵振峰, 于文博, 等. 基于时空位置大数据的公共疫情防控服务让城市更智慧[J]. 武汉大学学报∙信息科学版, 2020, 45(4): 475-488 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH202004001.htm

    Li Deren, Shao Zhenfeng, Yu Wenbo, et al. Public Epidemic Prevention and Control Services Based on Big Data of Spatiotemporal Location Make Cities more Smart[J]. Geomatics and Information Science of Wuhan University, 2020, 45(4): 475-488 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH202004001.htm
    [4] 李晓旭, 于亚新, 张文超, 等. Coteries轨迹模式挖掘及个性化旅游路线推荐[J]. 软件学报, 2018, 29(3): 587-598 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201803005.htm

    Li Xiaoxu, Yu Yaxin, Zhang Wenchao, et al. Mining Coteries Trajectory Patterns for Recommending Personalized Travel Routes[J]. Journal of Software, 2018, 29(3): 587-598 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201803005.htm
    [5] Chen Z, Shen H T, Zhou X, et al. Searching Trajectories by Locations: An Efficiency Study[C]//ACM SIGMOD International Conference on Management of Data, Indianapolis, Indiana, USA, 2010
    [6] Qi S, Bouros P, Sacharidis D, et al. Efficient Point-Based Trajectory Search[C]//International Symposium on Spatial and Temporal Databases, Hong Kong, China, 2015
    [7] Tang L A, Zheng Y, Xie X, et al. Retrieving k-Nearest Neighboring Trajectories by a Set of Point Locations[C]//International Symposium on Spatial and Temporal Databases, Minneapolis, MN, USA, 2011
    [8] Han J, Haihong E, Le G, et al. Survey on NoSQL Database[C]//International Conference on Pervasive Computing, San Francisco, USA, 2011
    [9] 李绍俊, 杨海军, 黄耀欢, 等. 基于NoSQL数据库的空间大数据分布式存储策略[J]. 武汉大学学报∙信息科学版, 2017, 42(2): 163-169 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201702004.htm

    Li Shaojun, Yang Haijun, Huang Yaohuan, et al. Geo-spatial Big Data Storage Based on NoSQL Database[J]. Geomatics and Information Science of Wuhan University, 2017, 42(2): 163-169 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201702004.htm
    [10] Nishimura S, Das S, Agrawal D, et al. MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware Services[C]//The 12th International Conference on Mobile Data Management, Lulea, Sweden, 2011
    [11] Nishimura S, Das S, Agrawal D, et al. MD-HBase: Design and Implementation of an Elastic Data Infrastructure for Cloud-Scale Location Services[J]. Distributed and Parallel Databases, 2013, 31(2): 289-319 doi:  10.1007/s10619-012-7109-z
    [12] van Le H, Takasu A. G-HBase: A High Performance Geographical Database Based on HBase[J]. IEICE Transactions on Information and Systems, 2018, 101(4): 1 053-1 065 http://www.researchgate.net/publication/324133897_G-HBase_A_High_Performance_Geographical_Database_Based_on_HBase
    [13] Apache HBase Team. Apache HBase TM Reference Guide[EB/OL]. [2019-12-18]. https: //hbase.apache.org/book.html
    [14] Fox A, Eichelberger C, Hughes J N, et al. Spatiotemporal Indexing in Non-relational Distributed Databases[C]//International Conference on Big Data, Santa Clara, CA, USA, 2013
    [15] Hughes J N, Annex A, Eichelberger C N, et al. GeoMesa: A Distributed Architecture for Spatio-temporal Fusion[C]// Geospatial Informatics, Fusion, and Motion Video Analytics, Washington, USA, 2015
    [16] Fecher R, Whitby M A. Optimizing Spatiotemporal Analysis Using Multidimensional Indexing with Geo- Wave[C]// Free and Open Source Software for Geospatial Conference Proceedings, Chicago, USA, 2017
    [17] Whitby M A, Fecher R, Bennight C. GeoWave: Utilizing Distributed Key-value Stores for Multidimensional Data[C]//Gertz M. Advances in Spatial and Temporal Databases. Switzerland: Springer, 2017
    [18] Haverkort H, van Walderveen F. Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves[J]. Computational Geometry, 2010, 43(2): 131-147 doi:  10.1016/j.comgeo.2009.06.002
    [19] Qin J, Ma L, Niu J. THBase: A Coprocessor-Based Scheme for Big Trajectory Data Management[J]. Future Internet, 2019, 11(1): 10 doi:  10.3390/fi11010010
    [20] Zheng Yu, Zhou Xiaofang. Computing with Spatial Trajectories[M]. New York: Springer, 2011
    [21] Chang F, Dean J, Ghemawat S, et al. Bigtable: A Distributed Storage System for Structured Data[J]. ACM Transactions on Computer Systems, 2008, 26(2): 1-26 http://www.mendeley.com/research/distributed-storage-system-structured-data/
    [22] Sahr K, White D, Kimerling A J, et al. Geodesic Discrete Global Grid Systems[J]. Cartography and Geographic Information Science, 2003, 30(2): 121-134 doi:  10.1559/152304003100011090
    [23] Google. S2 Geometry[EB/OL]. [2019-12-18]. https://s2geometry.io/
    [24] Uber. H3[EB/OL]. [2019-12-18]. https://uber.github.io/h3
  • [1] 曹布阳, 冯华森, 梁峻浩, 李响.  利用Hilbert曲线与Cassandra技术实现时空大数据存储与索引 . 武汉大学学报 ● 信息科学版, 2021, 46(5): 620-629. doi: 10.13203/j.whugis20200367
    [2] 涂伟, 曹劲舟, 高琦丽, 曹瑞, 方志祥, 乐阳, 李清泉.  融合多源时空大数据感知城市动态 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1875-1883. doi: 10.13203/j.whugis20200535
    [3] 李帆, 夏吉喆, 黄赵, 李晓明, 李清泉.  顾及停留位置特征提取的个人位置预测方法 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1970-1980. doi: 10.13203/j.whugis20200068
    [4] 乐鹏, 吴昭炎, 上官博屹.  基于Spark的分布式空间数据存储结构设计与实现 . 武汉大学学报 ● 信息科学版, 2018, 43(12): 2295-2302. doi: 10.13203/j.whugis20180034
    [5] 向隆刚, 王德浩, 龚健雅.  大规模轨迹数据的Geohash编码组织及高效范围查询 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
    [6] 李绍俊, 杨海军, 黄耀欢, 周芹.  基于NoSQL数据库的空间大数据分布式存储策略 . 武汉大学学报 ● 信息科学版, 2017, 42(2): 163-169. doi: 10.13203/j.whugis20140774
    [7] 刘汇慧, 阚子涵, 孙飞, 段倩, 唐炉亮, 吴华意.  采用轨迹大数据探测短时非营运行为 . 武汉大学学报 ● 信息科学版, 2016, 41(9): 1192-1198. doi: 10.13203/j.whugis20150569
    [8] 陈迪, 朱欣焰, 周春辉, 苏科华.  区域分片下的分布式空间查询处理与并行调度方法 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 892-896.
    [9] 陈静, 向隆刚, 朱欣焰.  分布式异构栅格数据的集成管理研究 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1094-1096.
    [10] 马娟, 方源敏, 赵文亮, 冯瑜瑾.  利用空间微分块与动态球策略的k近邻搜索算法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(3): 358-362.
    [11] 王宗跃, 马洪超, 徐宏根, 邬建伟.  LiDAR点云数据的分布式组织及其并行获取方法 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 936-939.
    [12] 王培超, 朱欣焰, 苏科华, 陈静.  分布式空间数据标记语言的研究与实现 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 659-662.
    [13] 蓝贵文, 黄全义, 周晓青.  一种面向WFS服务的分布式空间连接查询优化策略 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 654-658.
    [14] 肖晖, 杨必胜.  一种改进的基于道路网络距离的K近邻查询算法 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.
    [15] 边馥苓, 谭喜成.  适应于分布式虚拟地理环境服务的对等网络模型研究 . 武汉大学学报 ● 信息科学版, 2007, 32(11): 1028-1033.
    [16] 梅琨, 边馥苓.  分布式网络环境下地理信息元数据框架研究 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 356-359.
    [17] 朱庆, 周艳.  分布式空间数据存储对象 . 武汉大学学报 ● 信息科学版, 2006, 31(5): 391-394.
    [18] 李浩松, 朱欣焰, 李京伟, 陈军.  WebGIS空间数据分布式缓存技术研究 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1092-1095.
    [19] 关佶红, 陈晓龙, 陈俊鹏, 周水庚.  基于移动Agent的分布式地理信息查询 . 武汉大学学报 ● 信息科学版, 2003, 28(1): 39-44.
    [20] 郑晔, 郭仁忠, 贺彪, 马丁, 李晓明, 赵志刚.  利用映射-归约的分布式区域对象可视查询方法 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20210133
  • 加载中
图(10) / 表(1)
计量
  • 文章访问数:  959
  • HTML全文浏览量:  246
  • PDF下载量:  94
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-31
  • 刊出日期:  2021-05-05

面向分布式列式存储的轨迹大数据k近邻查询

doi: 10.13203/j.whugis20200136
    基金项目:

    国家重点研发计划 2018YFB2100603

    国家自然科学基金 41771474

    国家自然科学基金 41930107

    作者简介:

    余列冰,硕士,主要从事地理时空数据存储与计算研究。liebingyu@whu.edu.cn

    通讯作者: 孙尚宇,博士。shangyu_sun@whu.edu.cn
  • 中图分类号: P208

摘要: 针对轨迹大数据的高效点-轨迹k近邻(point to trajectory k nearest neighbor, P2T_kNN)查询处理需求,提出了一种融合时空剖分和轨迹分段的轨迹组织方法,其核心思想是在对轨迹作时间剖分的基础上,利用离散全球网格系统(discrete global grid system, DGGS)在空间上进行再次剖分,从而利用两次剖分得到的时空单元编码来索引落入其中的轨迹片段。在此基础上利用分布式列式存储技术设计了面向轨迹大数据的P2T_kNN查询处理框架,提出了一种顾及轨迹数据空间分布的自适应空间单元搜索算法,即通过分析轨迹数据在给定时间约束下的空间分异特征,动态调整空间单元的搜索步长,从而提升了轨迹稀疏区域的处理效率。针对亿级轨迹的实验结果表明,该方法适用于轨迹大数据的P2T_kNN查询处理,在轨迹稠密与稀疏区域的平均查询响应时间均小于1 s。

English Abstract

余列冰, 向隆刚, 孙尚宇, 关雪峰, 吴华意. 面向分布式列式存储的轨迹大数据k近邻查询[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
引用本文: 余列冰, 向隆刚, 孙尚宇, 关雪峰, 吴华意. 面向分布式列式存储的轨迹大数据k近邻查询[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
YU Liebing, XIANG Longgang, SUN Shangyu, GUAN Xuefeng, WU Huayi. kNN Query Processing for Trajectory Big Data Based on Distributed Column-Oriented Storage[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
Citation: YU Liebing, XIANG Longgang, SUN Shangyu, GUAN Xuefeng, WU Huayi. kNN Query Processing for Trajectory Big Data Based on Distributed Column-Oriented Storage[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 736-745. doi: 10.13203/j.whugis20200136
  • 随着导航定位技术的进步、移动互联网的发展和智能终端的普及,人们能够愈加方便地获取并记录关于人、车、动物与自然现象(如台风、雨云)等移动对象的轨迹数据[1]。目前,交通行业(如优步、滴滴出行等)和开放街道地图(OpenStreetMap,OSM)等众源门户已经汇聚了大量轨迹数据,且其规模与日俱增,已形成轨迹大数据。海量的轨迹数据为人们理解自然和社会的变化规律提供了前所未有的信息,促进了基于位置的社交网络、智能交通系统和城市计算的发展[2]。轨迹大数据携带的时空信息也催生了许多基于轨迹的应用,如传染病潜在接触人员追溯[3]、个性化路线推荐[4]、路网生成与更新等。

    在上述应用中,人们通常希望查询在某一时间范围内经过指定地点附近的轨迹。例如,在传染病潜在接触人员追溯中,需要查询近期经过疫情暴发地附近的人员或车辆轨迹,更进一步地,可能需要查询与这些人员或车辆轨迹存在时空相关性的轨迹,以追溯潜在的接触人员;当游客前往陌生景点时,希望查询最近经过该景点附近的轨迹,将其路线作为下一步的出行参考[5];在利用轨迹生成或更新局部路网时,需要获取最近一段时间内经过相应范围的轨迹。显然,上述应用需要根据地理空间位置从大规模轨迹数据集中高效查询出带有时间约束的最近邻轨迹。因此,本文面向轨迹大数据,利用分布式存储技术研究具有一定时间约束的点-轨迹k近邻(point to trajectory k nearest neighbor,P2T_kNN)查询处理问题。

    目前,已有学者对P2T_kNN查询处理进行了研究。文献[6-7]使用R树或全局堆[7]等数据结构设计了高效的P2T_kNN查询算法。然而,这些研究只关注轨迹的空间语义,难以满足带时间约束的P2T_kNN查询需求。更重要的是,这些方法侧重于算法设计,仅适用于集中式存储方案。为满足大规模时空数据的存储及查询需求,越来越多的研究试图在非关系型数据库(not only SQL,NoSQL)[8]上建立时空数据引擎,充分利用其非固化模式与分布式存储来实现时空数据的高效存储与查询[9]。MD-HBase[10-11]和G-HBase[12]借助Z阶曲线在HBase[13]之上建立了高效的空间索引,支持空间点数据的快速k近邻查询,但是对时间语义的支持不足。GeoMesa[14-15]和GeoWave[16-17]利用空间填充曲线[18](space-filling curve,SFC)对高维时空数据进行降维处理,从而建立了面向分布式键值存储的统一时空引擎,支持时空点数据的快速k近邻查询,但其对时间约束的处理仍不够灵活。此外,这些时空数据引擎仅支持传统的点-点k近邻查询处理,难以直接应用于P2T_kNN查询。THBase[19]基于HBase的协处理机制,提供了轨迹数据的存储及P2T_kNN查询处理方案,但是并没有考虑轨迹数据的空间分异性给查询带来的不利影响,数据稀疏区域的查询性能较低。综上所述,本文工作与现有工作的异同见表 1

    表 1  近邻查询相关工作比较

    Table 1.  Comparison Between Related Works on Nearest Neighbor Query

    统计项 输入 输出 扩展性 时空支持 平台
    P2T_kNN 时间约束、空间点 Top-k近邻轨迹 可扩展 时空 NoSQL
    文献[7-8] 空间点 Top-k近邻轨迹 不可扩展 空间 单机
    MD-HBase[10-11]、G-HBase[12] 空间点 Top-k近邻点 可扩展 空间 NoSQL
    GeoMesa[14-15]、GeoWave[16-17] 时间范围、空间点 Top-k近邻点 可扩展 时空 NoSQL
    THBase[19] 时间范围、空间点 Top-k近邻轨迹 可扩展 时空 NoSQL

    鉴于现有工作在面对大规模轨迹数据时,难以进行高效、带有任意时间约束的P2T_kNN查询处理,本文利用分布式列式存储技术设计了面向大规模轨迹数据的k近邻查询处理框架,提出了一种融合时空剖分和轨迹分段的轨迹组织方法,在此基础上实现了一种顾及轨迹数据空间分异性的自适应空间单元搜索算法。本文方法一方面借助于轨迹数据的时空分段与降维编码,充分利用列式存储数据库的高效键值检索能力,另一方面通过感知轨迹数据在给定时间约束下的空间分异特征,动态调整近邻查询的空间单元搜索步长。

    • 本文主要关注对于轨迹数据,具有一定时间约束的P2T_kNN查询处理问题,首先给出相关的形式化定义。

      定义1  轨迹:移动对象在地理空间中经过的路径由一系列按时间顺序排列的轨迹点表示,T = { p1pcard (T)},其中pi = (xiyiti),xiyiti分别表示轨迹点的经度、纬度和采样时间,且在一条轨迹中,∀1 ≤ i < j ≤ card (T),均有ti < tj

      定义2  点-轨迹距离[20]:点p到轨迹T的点-轨迹距离是pT中所有轨迹点的最小距离,即:

      $$D\left( {p, T} \right) = {\rm{mi}}{{\rm{n}}_{q \in T}}d\left( {p, q} \right)$$ (1)

      其中,d (∙)为两点之间的距离函数,在欧氏空间中一般取Lp范数。

      定义3  时间约束集合:由互不相交的时间区间构成的集合,W = { W1Wcard(W) },其中Wi =(tistie),tis < tiets表示时间区间的开始,te表示时间区间的结束,且∀1 ≤ i < j ≤ card (W),tie < tjs

      定义4  点-轨迹k近邻(P2T_kNN)查询:给定时间约束集合W,空间点p,近邻数k,待查询轨迹集合ST,P2T_kNN查询是从ST中检索出一个有序集合QT,满足如下条件:

      1)card (QT) = k

      2)∀ TQT,均有TST

      3)∀ TiQT,设p = (xpyptp) ∈ Ti,且是使Ti成为第i条近邻轨迹的轨迹点,那么Ǝ WjW,使得tpWj

      4)设TiTj分别是QT的第i条和第j条轨迹,如果1 ≤ i < jk,那么D (pTi) ≤ D (pTj);

      5)∀ TμSTTμQTTνQT,均有D (pTμ)> D (pTν)。

      在上述P2T_kNN查询问题的定义中,条件3)保证满足时间约束条件,条件4)说明QT是按点-轨迹距离排序的集合,而条件5)指出距离查询点p最近的k条轨迹一定在输出结果之中。需要说明的是,时间约束集合W可以包含任意数量的时间区间,这对轨迹数据的周期性对比分析具有重要意义,如查询过去1个月每天同一小时内前k条近邻轨迹的分布和移动信息,用于挖掘蕴含其中的规律或异常。

    • BigTable是第一个面向列的存储模型,采用了基于内存表和SSTable的存储技术[21]。与模式固化的关系型数据库相比,列式存储具有自由模式表达和分布式组织等特征,支持海量存储、高并发访问和弹性扩展。因此,本文基于分布式列式存储技术设计了面向P2T_kNN查询的处理框架,如图 1所示。在轨迹数据组织方面,数据表以轨迹标识符为行键来存储整条轨迹,而索引表以时空剖分形成的单元编码为行键来存储落入对应时空范围内的轨迹片段;在近邻查询处理方面,首先基于空间的递归剖分机制确定搜索空间单元的起点和步长,然后依据时空编码从索引表检索出候选的轨迹片段,最后进行过滤和排序处理,以得到满足查询条件的轨迹标识符,据此从数据表中获取完整的k条近邻轨迹。

      图  1  P2T_kNN查询处理框架

      Figure 1.  Framework of P2T_kNN Query Processing

      将高维轨迹数据存储于分布式列式存储数据库中,并服务于高效P2T_kNN查询处理,面临的首要问题是如何保证轨迹数据的时空聚集性,即时空邻近的轨迹在数据库中也应聚簇存储,以降低查询过程中的随机磁盘访问代价。为此,本文提出了一种融合时空剖分和轨迹分段的轨迹组织方法,首先对轨迹对象在时间上进行剖分,然后对每个时间分区内的子轨迹,利用离散全球网格系统(discrete global grid system,DGGS)[22]在空间上进行二次剖分,最终对由两次剖分得到的时空单元进行编码,以此索引落在其中的轨迹片段,从而实现高时空聚合的轨迹数据组织。

    • 考虑到轨迹数据的时空跨度较大,本文提出了一种基于轨迹片段的数据组织方法,即对完整的轨迹对象在时间和空间维度上进行两次剖分,以得到轨迹片段,最终以轨迹片段为单位对轨迹数据进行存储与管理。图 2示意了轨迹对象的时空剖分方法,步骤如下:

      图  2  轨迹数据时空分段组织及分布式存储

      Figure 2.  Spatiotemporal Segmentation Organization and Distributed Storage of Trajectory Data

      1)在时间维度上进行分割,将一条轨迹的轨迹点划分到不同的时间Bin中,落在同一时间Bin内的轨迹点即构成了一条子轨迹;

      2)在同一时间Bin内,利用递归四叉剖分的DGGS在指定层级对全球地表空间进行剖分,从而形成覆盖范围相同的空间单元,落在同一空间单元内且属于同一条轨迹的轨迹点即构成了一个轨迹片段;

      3)按时空邻近性,将轨迹片段存储于分布式集群的不同节点中。

    • 一方面,轨迹片段总是与时空单元关联,另一方面,列式存储数据库仅支持一维索引。因此,本文进一步研究时空单元的降维编码问题。SFC是一种常用的降维手段,也易于扩展到多维。由于时间维与空间维在量纲与尺度上的巨大差异,利用SFC进行时空一体的三维降维将带来严重的死空间问题。因此,本文提出时空分治的串接编码方法,具体是使用二维的Z阶曲线来编码由DGGS剖分得到的空间单元,然后与时间编码进行串接。为了适配不同时空侧重的查询类型,本文提出了3种时空串接的单元编码方案。其中,时间编码可根据具体应用选取年、月、周、日、时、分、秒等不同的最小编码粒度,而空间单元的编码精度与DGGS剖分时指定的层级相关。层级越高,则递归剖分的次数越多,全球范围内空间单元的数量也越多,每个空间单元所覆盖的地理范围越小。空间单元的编码精度用log2m表示,其中,m表示最大的编码值,如图 2所示的DGGS剖分得到的空间单元编码精度为4。时空串接编码方案如图 3所示。

      图  3  时空串接编码结构

      Figure 3.  Structure of Spatiotemporal Concatenated Encoding

      1)时空(temporal-spatial,TS)编码,将顺序时间编码(即按时间粒度由大到小顺序排列的时间编码)与空间上的Z阶曲线编码串接。该编码顺序适用于时间约束以最小时间编码粒度为单位的P2T_kNN查询。

      2)空时(spatial-temporal,ST)编码,将空间上的Z阶曲线编码串接顺序时间编码。该编码方案仅适用于时间跨度很小的轨迹数据集,在实践中一般很少用到。

      3)时空时(temporal-spatial-temporal,TST)编码,该编码方案可以有不同的串接顺序。如前置时间编码为年月日,后置时间编码为时,从而将同一天内的轨迹数据聚集在一起,适用于时间约束以天为单位的P2T_kNN查询;又如前置时间编码为年月时,后置时间编码为日,从而将同一个月每天某个相同小时内的数据聚集在一起,因而适用于时间约束为一个或几个月每天同一小时的P2T_kNN查询。

    • P2T_kNN查询算法主要通过不断搜索相关时空单元,直到获取满足时间约束且与查询点近邻的k条轨迹,或达到所设定的最大查询空间范围阈值。空间单元的编码精度对P2T_kNN查询的性能有重要影响:在数据稀疏区域,低精度编码意味着更大的空间单元,在相同搜索次数下可以覆盖更广的范围,使得近邻搜索的效率更高;在数据稠密区域,所需搜索的空间范围小,高精度编码更为合适,以避免取出大量假阳性轨迹片段。

      为了兼顾不同密度区域的近邻搜索效率,本文提出了一种顾及数据空间分布的自适应空间单元搜索算法,即通过感知轨迹数据在给定时间约束下的空间分异特征,动态调整近邻查询的空间单元搜索步长。这样便可将轨迹数据存储于某一较高的空间单元编码精度下,在处理数据稀疏区域时,算法可以根据空间的递归剖分机制,利用上层更大步长的空间单元来进行近邻搜索。

    • P2T_kNN查询算法可分为搜索和过滤两个阶段。在搜索阶段,通过搜索查询点周围的空间单元,得到距离查询点最近且满足时间约束的、属于k条不同轨迹的轨迹片段,包括如下几个子任务:

      1)计算点到空间单元的距离。设查询空间点qk = (xqyq),空间单元c = (x1y1x2y2),其中,(x1y1)为左下角点,(x2y2)为右上角点,且qk不在空间单元c内,即xq < x1xq > x2yq < y1yq > y2。则空间点qk到空间单元c的距离为:

      $$ D\left( {{q_k}, c} \right) = \left\{ {\begin{array}{*{20}{l}} {{\rm{min}}\left( {\left| {\begin{array}{*{20}{c}} {{y_q} - {y_1}} \end{array}} \right|, \left| {\begin{array}{*{20}{c}} {{y_q} - {y_2}} \end{array}} \right|} \right), {x_1} \le {x_q} \le {x_2}}\\ {{\rm{min}}\left( {\left| {\begin{array}{*{20}{c}} {{x_q} - {x_1}} \end{array}} \right|, \left| {\begin{array}{*{20}{c}} {{x_q} - {x_2}} \end{array}} \right|} \right), {y_1} \le {y_q} \le {y_2}}\\ {{\rm{min}}\left( {{d_{bl}}, {d_{ul}}, {d_{ur}}, {d_{br}}} \right), 其他} \end{array}} \right. $$ (2)

      式中,dbl=d(qk,(x1y1)),dul=d(qk,(x1y2)),dur=d(qk,(x2y2)),dbr=d(qk,(x2y1))。

      2)获取给定空间单元的8个相邻空间单元编码。以图 4中编码为26的空间单元为例说明在Z阶曲线中获取相邻空间单元的方法,由进制转换可得(26)10 = (011010)2,将其分解到经纬度方向,则经度方向二进制编码为011,纬度方向二进制编码为100。此时,若需获取其左上方相邻空间单元的编码表示,则由空间相对位置可知,需要在经度方向减1得010,纬度方向加1得101,再对其进行交叉编码即可得(011001)2 = (25)10。其余7个方向相邻空间单元编码的计算方式类似。

      图  4  获取给定空间单元的8个相邻空间单元

      Figure 4.  8 Adjacent Spatial Cells of a Specific Spatial Cell

      3)由空间单元及时间约束集合获取索引表中对应的行键区间集合。首先将空间单元对应的空间范围及查询的时间约束集合转化为索引表的行键区间集合,然后使用非关系数据库接口来获取轨迹片段。其转化过程如图 5所示。

      图  5  由时空范围获取索引表对应的行键区间集合

      Figure 5.  Row Key Range Set Corresponding to Index Table from Spatiotemporal Range

      在精过滤阶段,取出落在以查询点为圆心、以查询点到搜索阶段最远轨迹片段距离为半径的圆形区域内,并满足时间约束的所有轨迹片段。最终结合两阶段的查询结果,得到距离查询点最近的k条轨迹的标识符,即可从数据表中取出完整的轨迹数据(算法1)。

    • 在轨迹数据密集区域,算法1可以实现高效的P2T_kNN查询,但是在数据稀疏区域,算法1的查询性能将急剧下降。这是由于在数据稀疏区域,落在查询点附近空间单元内且符合时间约束的轨迹片段数量很少,甚至为零,使得获取k条近邻轨迹需要搜索非常大的空间范围。在这种情况下,需要查询的空间单元数量呈指数级增长,使得相对于数据密集区域,其数据库访问次数大大增加,从而降低了查询效率。为了定量研究轨迹大数据的空间分异性给P2T_kNN查询带来的不利影响,本文引入空间单元的k率来对此进行分析。

      定义5空间单元的k率:给定时间约束集合W = {W1Wcard(W)},空间单元c=(x1y1x2y2),近邻数k,轨迹集合ST满足∀TiST,Ǝ p =(xpyptp) ∈ Ti,使得x1xpx2y1ypy2tpWj,且WjW。则空间单元的k率为:

      $${P_k} = \frac{{{\rm{card}}\left( {{S_T}} \right)}}{k}$$ (3)

      在空间单元k率的基础上,本文设计了一种能够感知轨迹数据在给定时间约束下的空间分异特征,并动态调整空间单元搜索步长的近邻查询算法,从而在数据疏密程度不同的区域均可实现高效的P2T_kNN查询。具体来说,在搜索阶段开始之前,先根据给定查询点周围及时间约束集合内的数据疏密程度,确定合适k率的空间单元步长,再用此步长进行搜索。

      图 6展示了k为3时不同步长的空间单元搜索过程(设图 6中所有轨迹点都落在给定的时间约束集合内),其中,红色矩形框代表以底层空间单元为步长的搜索过程,阴影部分区域代表以其父空间单元为步长的搜索过程。1个父空间单元对应4个子空间单元,从而将4次单行键的索引表访问合并为1次连续行键区间的索引表访问,有效减少了索引表访问次数,提升了查询效率。显然,在k值更大且数据十分稀疏的区域中,效果提升将更加明显。

      图  6  k为3时不同步长空间单元的搜索过程

      Figure 6.  Searching Process of Asynchronous Step Size When k Is 3

      根据轨迹数据在时间约束下的空间分布确定搜索空间单元的步长时,有如下两个子任务:

      1)获取当前空间单元的父空间单元。在Z阶曲线中,将子空间单元编码的二进制表示去掉最后两位,即可得到父空间单元的编码。如精度为6的空间单元(26)10 = (011010)2,由于其父空间单元精度为4,将其二进制编码去掉最后两位,即可得其父空间单元编码为(0110)2 = (6)10

      2)根据精度为m1的空间单元编码确定精度为m2的空间单元编码区间(m1 < m2)。在确定合适搜索步长的空间单元后,可能得到精度较低(以m1表示)的空间单元编码,但是在索引表中,数据是以固定的较高精度(以m2表示)存储的。为了从索引表中取出精度为m1的空间单元对应范围内的轨迹片段,需将其编码转化为精度为m2的空间单元的编码区间。在Z阶曲线中,其转化过程如下:所求区间的起始值在精度为m1的空间单元编码值二进制表示后补足m2-m1个0,结束值补足m2-m1个1。

      算法的详细过程为:首先,确定查询空间点所在的空间单元;然后,通过并行方式计算该空间单元内轨迹对象的数量,并判断其k率,若未达到指定k率,则获取当前空间单元的父空间单元,并重复上述操作,直到其k率满足要求为止。

    • 为了验证本文提出的P2T_kNN查询框架及处理算法的有效性,利用Apache HBase 1.4.9搭建了原型系统,运行在由3个节点组成的集群上,包括1个HMaster节点和2个Region Server节点,每个节点均配有CentOS 7.5.1804操作系统、3.60 GHz Intel Core i7-7700 CPU、32 GB内存,以及6 TB 5425 RPM硬盘。实验数据为中国湖北省武汉市2015-05-01-2018-05-31的103 905 394条出租车轨迹,平均每条轨迹包含约97个轨迹点,共719.1 GB。

      实验数据库由1个数据表和3个空间编码精度均为40的索引表构成,分别对应3种不同的编码方案:编码Ⅰ为TS编码,编码顺序为年月日时+空间编码,编码Ⅱ为TST编码,编码顺序为年月日+空间编码+时,编码Ⅲ为TST编码,编码顺序为年月时+空间编码+日。在本文实验中,输入的查询时间约束和查询点均基于有效时空范围随机生成,而查询响应时间为1 000次查询的平均响应时间。

    • 为了验证不同时空串接编码方案所适用的查询场景,分别在时间约束为1 h、1 d以及1个月每天同一小时的情况下,基于3个不同编码的索引表进行了查询处理,实验结果见图 7

      图  7  不同时间约束下的P2T_kNN查询实验

      Figure 7.  P2T_kNN Query Experiments Under Different Time Constraints

      图 7可得,编码Ⅰ、Ⅱ、Ⅲ分别适用于时间约束为1 h、1 d和1个月每天同一小时的查询。这是由编码的时空聚集性决定的,以编码Ⅱ为例,它将同一天落在相邻空间单元内的轨迹片段聚簇存储,对于时间限制为1 d的查询,可极大地减少磁盘随机读取的次数,从而降低查询的输入输出延时。对于时间限制为1 h或1个月每天同一小时的查询,编码Ⅱ将取出大量的假阳性轨迹片段,增加后续过滤的负担,从而降低查询效率。同样,编码Ⅰ和编码Ⅲ分别将落在相邻空间单元内1 h和1个月每天同一小时的轨迹片段聚簇进行存储,从而分别适用于各自的查询场景。

    • 为了验证本文提出的数据分布自适应空间单元搜索算法的性能增益,在编码Ⅱ的索引表上进行了时间约束为1 d的查询对比实验。实验结果见图 8。从图 8中可以得出:利用本文所提出的自适应空间单元搜索算法,查询响应时间可以从9 s左右缩短到500 ms以内,且其响应时间对k值变化的敏感度更低,这主要得益于k率的引入,使得搜索空间单元的步长选取同时考虑了轨迹数据的空间分布和k值输入。

      图  8  时间约束为1 d的查询对比实验

      Figure 8.  Query Comparison Experiment with Time Constraint of 1 d

      图 9k值为10且k率为1时的查询响应时间分布图。从图 9中可以看出,在未采用自适应空间单元搜索算法的情况下,P2T_kNN查询只能在数据稠密区域(武汉市中心区域)达到良好的效果,而在数据稀疏区域,由于需要搜索的实际空间范围增大,需要搜索大量的小空间单元,导致频繁的数据库读取操作,使得其查询响应时间迅速上升。使用本文提出的自适应空间单元搜索算法可以动态调整空间单元的搜索步长,从而有效减少数据稀疏区域的搜索次数,使得P2T_kNN查询在整个武汉市区域内均能达到良好的效果。

      图  9  k值为10且k率为1时的查询耗时分布图

      Figure 9.  Distribution of Query Time When k Value Is 10 and k Rate Is 1

    • 为了定量研究轨迹大数据的空间分异性对于P2T_kNN查询性能的影响,在编码Ⅱ的索引表上进行了时间约束为1 d不同k率设定下的查询实验。从图 10的实验结果中可以得出,随着k率的增加,查询性能逐渐上升,在k率达到0.5之后,查询响应时间逐渐趋于平衡。这是由于随着k率的上升,空间单元的搜索步长变大,减少了数据稀疏区域的搜索次数。当然,k率的取值不能过大,否则会使得每个空间单元内的数据过多,从而增加数据读取和过滤的负担。从本文的实验结果中可以得出,在k率取值在0.5~2.0时,查询均具有良好的效果。

      图  10  不同k率下的查询耗时

      Figure 10.  Query Time at Different k Rates

    • 为了高效处理轨迹大数据的P2T_kNN查询,本文提出了面向分布式列式存储数据库的近邻查询处理框架及其搜索算法。该框架首先基于时空剖分单元对轨迹进行分段组织,并利用时空串接编码实现轨迹片段的时空聚簇存储;其次设计了一种能够感知轨迹数据在给定时间约束下的空间分异特征,并动态调整空间单元搜索步

      长的近邻搜索算法,极大地提升了数据稀疏区域的处理效率。实验结果表明,本文所设计的时空串接编码能够适用于不同时间约束的查询场景,且提出的自适应空间单元搜索算法无论在数据稠密还是稀疏区域都具有优异的表现,针对亿级轨迹数据集的实验结果表明,千次随机查询的平均响应时间优于1 s。

      本文提出的自适应搜索策略适用于任何基于递归剖分的DGGS,具有较强的可扩展性,可无缝对接其他的剖分框架,如S2 Geometry[23]、H3[24]等。尽管本文提出的自适应空间单元搜索算法考虑了轨迹数据的空间分异特征,但是其时空单元的编码长度固定在某一精度上。下一步将研究基于时空分异特征的轨迹大数据编码与组织方法,以及相应的P2T_kNN优化查询技术。

参考文献 (24)

目录

    /

    返回文章
    返回