-
随着越来越多的车辆轨迹数据被记载，海量、复杂的时空数据需要存储、索引，以满足分析、监控及其他应用目的。不同的应用场景对底层数据的管理设计有着不同的约束要求，针对特定的应用场景，对数据进行管理组织是未来面对海量数据进行高效查询的重要手段之一。例如，利用轨迹数据中的起止点（origin-destination，OD）信息可以进行城市功能区的识别[1-2]，但由于数据量及查询检索效率的限制，以往此类分析通常仅能基于较小规模的数据量，影响分析精度与覆盖面。除基于出租车轨迹的用地区域（商业、工作、居住）识别、行为模式识别的分析研究外，近年来一些学者所开展的城市中移动空气质量监测的相关研究也用到了车辆的时空轨迹数据[3]。这项研究将车载空气监测设备的数据与标准站的数据进行调校，整合时空范围查询和目标查询以满足数据校准需求，由于空气质量变化频繁，因此对数据管理与索引查询的效率要求进一步提高。
车辆轨迹数据属于时空大数据范畴，数据量大，内容复杂，如何高效地管理和检索海量轨迹数据是亟待解决的问题。传统集中式数据存储管理策略与串行式时空分析算法已不能很好地满足时空大数据高效存储和实时处理分析的需求。分布式数据库相比于传统数据库具有更强的可扩展性与容错性，其通过多个节点进行分布式存储、计算，提高了数据访问速度；通过增添存储节点实现存储容量的线性扩展；采用不同节点存储数据副本，提高了数据库的容错性。上述特性有助于时空轨迹大数据的管理与应用需求，因此，利用分布式系统进行时空大数据的存储是未来的重要技术之一，而相应的技术研究与实现是本文的研究重点。
时空大数据的重大挑战之一是其维数，经纬度、坐标点并没有先验顺序，而顺序本身对于列族数据库（Hbase、Cassandra）本地索引的词典顺序来说是必须的，增加额外的维度，如高程、时间等还会进一步带来如何索引高维数据的问题。空间填充曲线是解决此类问题的一种重要方法，同时也有各种利用树形索引进行数据查询管理的方法，此方法在传统数据库的存储设计中出现较为频繁，且已经形成了较为成熟完整的体系。从索引的构建过程和特性来看，目前常用的方法可以分为基于数据和基于空间[4]或称为面向目标和面向空间划分[5]的数据组织及编码方式。
传统数据库主要依赖于以B+树和R树为基础的索引结构。这些树形结构就是基于数据或称之为面向目标的数据组织及编码方式，整个树形结构的构造过程都受其所收到的数据输入驱动，随着后续数据的插入，整个树的结构也会需要进行相应的动态调整[6]。因此，在完成数据记录的全部插入之前，无法对其构建哈希索引，从而影响后续的数据查询效率。二维空间索引结构的变种和扩展是当前面向目标的数据组织方式的主要方法，这些索引都是使用数据轨迹的最小外包矩形（minimum bounding boxes，MBBs）作为指针来构造索引。这类索引都有与R树类似的数据结构，如3D R树[7]、一种可扩展的高效轨迹索引（a scalable and efficient trajectory index，SETI）[8]、开始/结束时间戳B树（start/end time stamp B-tree，SEB Tree）[9]、轨迹束树（trajectory-bundle tree，TB Tree）结构[10]等。当数据量快速增加或体量庞大时，会增加MBB的重叠面积，令索引的性能及效率下降[11]。此外，数据更新时，也要求索引结构同步更新，提高了维护代价[5, 12-13]。文章[14]提出了考虑地点和行驶时间来查找最符合条件的k条轨迹（top-k trajectories by locations and ranking by traveling time，k-TLT）查询方法，能够查询到最符合条件的k条轨迹，并试图通过剪枝算法及定义时间关键字技术提高索引效率。然而，其针对特定用途查询，适用范围有限。
基于空间或称之为面向空间划分的索引方法提前对空间进行划分，位置数据的索引值完全基于其索引空间的划分块，而与已插入或待插入数据无关。当针对高频及海量的数据更新与查询时，其效率高于树形结构[15]。得益于其简单的构造及所带来的高效性能，此类方法在最近几年得到了广泛应用，如GeoSOT[5]、GeoMesa[6]、四叉树[16]、Trip-Cube[17]、网格索引[18]等。文献[19]基于Hadoop，利用希尔伯特（Hilbert）空间曲线划分方法改进了GeoMesa索引结构；文献[19]提出的基于GeoMesa的TrajMesa方法使用剪枝算法提高了检索的效率；文献[20]针对路网与旅行时间预测，提出使用S2算法在Cassandra中对时空数据进行存储。文献[21]根据HBase存储特性设计了时空数据模型，并且研究了行键对时空查询的影响，将R树索引应用到Hadoop平台上，根据不同的时间间隔来划分时空数据，即便是同样的数据也会根据划分的尺度不同而重复地存储在不相同的索引下，对于不同的查询，再从不同的尺度索引中得到结果，通过冗余的存储提高查询效率。文献[22]提出了一种基于Spark分布式计算框架的时空查询与分析系统（spatiotemporal spark，ST-Spark），基于Cassandra设计了时空数据与索引模型，并将同一时空对象的数据按照时间顺序排列在同一个节点中，经纬度数据按照0.5°一格的方式转化为一维数据。该方法存储数据的空间粒度较为粗糙，数据降维方式较为简单，紧邻的数据会发生位置突变。一些学者所提出的基于活动轨迹的网格索引（grid index for activity trajectories，GAT）[23-24]轨迹片段组织方法将空间划分为不同层级的网格，并且构建了层级之间的倒置索引，以便记录移动目标经过的时空轨迹。
现有针对时空大数据的存储与索引的研究主要基于Hadoop，通过空间换时间的方式冗余存储多种尺度数据，多数采用会产生位置突变的数据降维方法，少数使用Hilbert曲线进行空间划分。本文融合多种方法，通过S2算法将多维时空数据降维存储到Cassandra中，并通过对行键的设计实现对时空大数据的快速索引、查询，以此完善海量时空数据在分布式数据库中存储、查询的应用。尽管本文的设计思路与文献[23]有类似之处，即采用的空间编码方法能够直接计算各个层级的数据，但通过优化设计，本文仅选取了两个层次分级以适配本文所采用的数据以及需要构建的数据索引，从而保证时空数据的时空近邻存储，以提高数据查询的效率。
-
Cassandra是一个具有高可拓展性的分布式数据库，采用对等体系结构，所以可以从任何节点对数据进行操作，添加或者删除节点并不会对整个数据库产生太大的影响。这保证了Cassandra数据库有很好的容错能力，如任一节点出现故障，可以通过其他节点对数据进行操作。这些特性使得Cassandra在高效运行的同时避免了数据丢失。表 1列举了后续讨论中所涉及的Cassandra数据模型中的一些基本概念。
表 1 Cassandra数据模型中的基本概念
Table 1. Terms Used in Cassandra Data Model
名称 概念 Column Cassandra中最基本的存储单元，用于存储某一列的信息 Primary key 主键，决定每一行数据的唯一性，由分区键和集群键组成 Partition key 分区键，根据Hash值存储数据到不同的物理区域中 Cluster key 集群键(聚簇键)，对于分区中的记录进行排序 对于车辆轨迹数据而言，每一列数据具有相似性，利用Cassandra数据库基于列存储和键值存储的特性可实现数据压缩，进而提高海量时空数据的存储效率。实际应用中的车辆轨迹随着时间不断被记载，数据增长速度较快，利用Cassandra数据库具有节点添加便捷和可扩展性好的特性，能够有效地解决车辆轨迹时空大数据的存储和索引问题。
本文提出了基于Cassandra数据库技术的车辆轨迹时空数据索引结构和相关的存储方案。图 1为数据存储示意图。
图 1 列存储样例
Figure 1. Column-Oriented Storage Example
-
Geohash是一种地理编码系统，其本质是一种分级的数据结构，以网格的形式划分空间，并将其编码为一小段字母和数字。Geohash采用的空间填充曲线是Z阶曲线，该曲线的生成原理构成了Geohash算法的理论基础。Geohash与Z阶曲线有如下相关性质：一个点邻近的（但不绝对）Hash字符串总是有公共前缀，并且公共前缀的长度越长，这两个点距离越近，如图 2所示的空间划分示例。
图 2 Z阶曲线（X轴是纬度数据，Y轴是经度数据）
Figure 2. Z-order Curve (Where X-axis Is Latitude and Y-axis Is Longitude)
Geohash是以4为底的空间索引，使用循环的四分区将连续的经纬度空间坐标转换为分层的离散网格。对于给定经纬度坐标，分别对经度和纬度进行处理，将地球的纬度区间[－90°，90°]和经度区间[－180°，180°]不断二分。如果给定坐标属于二分的右区间范围，则标记一个1，否则标记一个0，针对不同的编码层级，得到经纬度的二进制字符串。再遵循“偶数位放经度，奇数位放纬度”的原则，对经纬度字符串进行整合，最终二分产生如图 2所示的二进制位编码（32位编码）。尽管Geohash所采用的Z阶曲线具有局部邻近性，但它的编码不能有效反映距离突变的现象，如图 2所示，在“Z”字母的各个拐角都可能会出现空间距离的突变，而它们的编码表面上“邻近”。
Z阶曲线只是众多空间填充曲线中的一种，Giuseppe Peano发现了第一条连续的空间填充曲线（Peano曲线），它穿过单位正方形上的每个点：取一个正方形并且把它分成9个相等的小正方形，然后从左下角的正方形开始至右上角的正方形结束，依次把小正方形的中心用线段连接起来；下一步把每个小正方形分成9个相等的正方形，再将其中心连接起来；整个过程重复多次之后，可获得如图 3所示的Peano曲线。
图 3 Peano曲线
Figure 3. Peano Curve
依据同样的思想，Hilbert提出了一个更简单有效的变体，它不是将空间切分成9个同样大小的正方形，而是将其切分成4个同样大小的正方形（图 4为Hilbert曲线）。
图 4 Hilbert曲线
Figure 4. Hilbert Curve
Hilbert曲线及其离散逼近有着广泛的应用，因为它们在一维和二维空间之间提供了映射，其不仅具有连续性，而且曲线的某些部分与整个曲线相似，具有分形结构，可以很好地保留局部性[24]，其特征意味着在一维空间中彼此靠近的两个数据点折叠后也彼此靠近，而其他空间充填曲线，如蛇形曲线，在折叠后两个点的距离就会相对更远。S2是Google提供的一个开源的解决球面上各种几何问题的算法库，S2采用Hilbert曲线作为空间划分基础。相比于Z阶曲线，Hilbert曲线不会发生“空间突变”（即相邻数字编码的点空间不相邻）。
S2提供了31个不同的层级（从Level 0至Level 30）表示不同大小的区域，Level 0所表示的区域面积是地球表面积的六分之一，而Level 30所表示的最小面积为0.48 cm2，最大为0.93 cm2。S2算法通过5次变换将球面上的点转换成为Cell ID，Cell ID是球面上一个坐标点的编码或标识符。这5次变换分别是球面坐标转换、球面变平面、球面矩形投影修正、点与坐标轴点相互转换、坐标轴点与Hilbert曲线Cell ID相互转换。
在S2中通过球面坐标转换将经纬度转换成为三维空间坐标，即将（经度（lng），纬度（lat））转换成为（x，y，z）。而后是将球面转换成为平面，具体方法为：构建一个地球的外切正方体，从球心向外切正方体投影得到6个平面，从而把球面坐标映射为平面坐标，即（x，y，z）转换成为（face，u，v），其中face表示6个面的标识，而（u，v）为对应6个面之一的横纵坐标。由于投影是从球面到平面，同样角度的不同球面区域投影到平面的面积不一样，因此需要进行球面矩形投影的修正，修正后空间坐标转换成为（face，s，t），其中（s，t）表示对（u，v）进行投影修正后所产生的横纵坐标。
为了将所得到的点映射到所划分的区域中，首先将6个平面分别划分成为不同大小的正方形，而这些正方形不同的尺寸定义了先前叙述的不同层级。例如在Level 10层级，整个平面被划分为210×210个小正方形。任何一个小正方形可用横坐标i和纵坐标j来表示，如（s，t）落在正方形区域（i，j）中，则它在此平面上的标识为（face，i，j）。然后把坐标（i，j）转换成为Hilbert曲线的ID，与所对应的平面上的标识一同构成了地球表面上某个点的Cell ID。
式（1）表示了上述转换过程：
$$ S\left( {{\rm{lng}}, {\rm{lat}}} \right) \to f\left( {x, y, z} \right) \to g\left( {{\rm{face}}, u, v} \right) \to h\left( {{\rm{face}}, s, t} \right) \to H\left( {{\rm{face}}, i, j} \right) \to {\rm{Cell}}\;{\rm{ID}} $$ (1) -
区域的空间划分是可限定的，而时间是无限延伸的，轨迹数据会随着时间而无限增长，如将所有数据全部存储到一张表中，即使是采用分布式数据库，在时间维度上的无限延伸也会导致同一目标的大量轨迹数据在物理存储上近邻，从而带来查询的压力和相关的管理风险。例如，文献[3]的研究中所用的车辆轨迹数据一个月有1亿条记录。根据实际应用经验，本文选择以半年为分表尺度，即每半年一张新的数据表，根据分区键重新部署至各个节点，跨表查询可通过高级程序语言（如Python、C++、Java等）进行逻辑判断处理。
Cassandra数据库具有键值存储的特点，分区键和聚簇键共同组成表的主键。其中，分区键决定了数据存储在哪个节点上，具有相同分区键值的数据将位于同一节点上，在同一节点中，数据根据聚簇键顺序排列，并且分区键和聚簇键都可以是多个列值的组合，数据会依次根据聚簇键的各个列顺序物理分布到磁盘上。
针对实际应用中遇到的最为基础的两种查询模式“时空范围查询”及“按车辆标识符查询”，本文所设计的存储结构模型分别如图 5和图 6所示。时空范围查询的分区键用低一级的空间编码与时间段切片共同组成，聚簇键由高一级空间编码、时间戳与轨迹车辆的标识符组成，其他列值为余下存储数据；而车辆标识符查询则用车辆标识符与时间段切片共同组成分区键，聚簇键仅由时间戳组成，其他列值为轨迹的其他属性数据。
图 5 时空范围查询存储表结构
Figure 5. Storage Structure for Spatiotemporal Range Query
图 6 按车辆标识符查询存储表结构
Figure 6. Storage Structure for Query upon Vehicle ID
在实际应用中，用户通常可以根据车辆标识符查询功能获取指定时间范围内、指定车辆标识符的行驶轨迹；通过该轨迹数据能够得知其路线的MBB；利用该空间及时间作为查询键值，获取该时空范围内与指定车辆同时出现的其他所有轨迹数据。反之，用户也可以根据时空范围查询获取指定时空范围内的所有车辆轨迹，根据结果获取其车辆标识符，由此可以通过查询获取其轨迹数据，供后续研究分析之用。
-
该查询所对应的场景是某一时间段内经过某一空间区域的轨迹数据信息，轨迹数据的时空连续特性保证了轨迹点具有典型的时间和空间的近邻性，但是查询条件本身必须具有一定的灵活性以适合具体的需求，例如，选定的时间段与空间范围根据实际需求进行相关的调整，而所构建的索引却无法根据需求实时动态调整，因此空间索引与时间索引的划分粒度更多的是依据实际经验或根据应用场景本身的需求进行选择。
S2编码的码长越长，索引层级与精度也越高，相同位置区域在不同层级的S2编码拥有共同的前缀，相同层级相邻区域的S2编码也具有共同的前缀，前缀的匹配度越高，代表两者越接近。本文在设计数据表键值时利用了该特征，目的是保证相邻的数据对象在物理存储上能够相近。
尽管长编码能够带来精细的地域划分，但是存储、查询过程会频繁操作多个键值，增加索引次数，从而降低了读写性能。恰当尺度的空间划分、尽可能更少地执行键值查询操作，能够极大限度地降低数据存储的冗余结果。
针对本文应用场景，选取Level 15和Level 17两个层级的编码进行实验，具体的层级选择可以根据不同实际场景决定。Level 15的编码平均面积约为80 000 m²，平均边长约250 m（具体数值与地理位置相关），Level 17的编码平均面积约为5 000 m²，平均边长约60 m；时间划分以6 h为一段。
图 6为Cassandra数据库中存储的数据结构，大尺度层级Level 15的S2编码（Level 15 Cell ID）和时间划分切片共同组成复合的分区键，根据Cassandra数据库的特性，意味着某80 000 m²区域6 h范围内所有数据存储在分布式的某一节点上.在该节点上，数据依次根据小尺度层级Level 17的S2编码值（Level 17 Cell ID）、轨迹数据采集的时间戳，以及车辆标识符三者顺序物理存放，最后的键值列为经纬度坐标、车速、是否载客等各类型数据。这种设计的分区键保证了在大空间尺度和时间段范围的时空区域内数据位于同一数据节点上，同时在该节点内部通过小尺度空间编码、时间戳和车辆编码保证了数据物理存储的时空近邻，从而减少了数据库的读写操作，提升了查询效率。
查询时需给定查询空间范围（简称为Polygon）和时间范围起止点，具体算法步骤为：（1）确定Polygon左下角和右上角的经纬度坐标；（2）利用该坐标通过S2对应的接口得到覆盖该矩形区域指定编码层级的一组Cell ID，本文中需要获取Level 15和Level 17这两个层级的两组Cell ID；（3）计算起止时间点所跨越的时间段、时间戳范围（秒形式）；（4）两组Cell ID前缀匹配最大的层级对及时间段用于Cassandra中的CQL查询语句等值判断，时间戳范围则通过范围查询过滤；（5）查询的结果经过所给定Polygon的系列点坐标进行过滤得到最终结果。
-
此类查询所对应的应用场景是某一车辆目标在某时间段内的轨迹数据，扩展应用是对该段轨迹经过的时空区域进行二次时空范围查询，从而找出近邻轨迹。因此，该查询不需要对空间数据进行编码处理，并且轨迹间的近邻与否无从判断，也没有近邻的轨迹数据需要存放到同一节点的物理存储需求。时间段划分作为分区键使同一车辆的轨迹数据根据时间段分布到不同节点上，时间戳作为聚簇键顺序物理存储同一车辆的轨迹数据，即使同一车辆的轨迹数据可能会大量聚集，但由于单时间序列的线性存储，将不影响查询的效率。
图 6为Cassandra数据库中存储表的数据结构，车辆标识符和时间切片作为分区键，保证同一车辆6 h范围内的轨迹数据分布在同一节点上，时间戳作为聚簇键保证同一车辆的轨迹数据按时间顺序排列，最后的键值列为经纬度坐标和其他一些属性，如车速、空气质量监测值、是否载客等信息。设计分区键的原因为：在查询较长时间区间数据时，因为时间片的不同，可以实现分布式并行查询，从而使查询效率更为高效。
查询条件包括车辆标识符及时间范围的起止点，具体算法步骤为：（1）计算每个车辆起止时间点所跨越的时间段及时间戳范围（以秒为单位）；（2）车辆标识符及时间段采用Cassandra自带的CQL查询语句进行等值判断，而时间戳范围则直接应用于范围查询的过滤。
-
时空轨迹大数据是一系列带有时间戳标记的位置记录集合，不同的数据采集设备，不同的应用场景，其所附带的属性信息不尽相同。为满足各种应用的个性化场景需求，需要对所采集的数据内容进行预处理，本节将列举两种时空轨迹相关的应用场景下所获得的数据格式，以及对这类数据本身所必备的关键字段进行相关预处理的方案。表 2中的样例数据为2016年8月的行车数据，数据较为规范，属性丰富。此数据源有车机号、控制字、报警、空车、顶灯状态、高架、刹车、接收时间、GPS时间、经度、纬度、速度、方向、卫星个数共14个属性，位置点采集时间间隔约10 s，总记录数近7百万条。
表 2 强生出租车车载GPS数据
Table 2. Qiangsheng Taxi GPS Data
列号 列名 数据类型（精度范围） 中文备注 0 车机号 Small int 出租车标识，如12345 1 控制字 Var Char ‘A’ 2 报警 Int 1：报警；0：正常 3 空车 Int 1：空车；0：重车 4 顶灯状态 Char 定位状态A：收敛；V：不收敛顶灯状态0:营运；1:待运；2:电调；3:暂停；4:求助；5:停运 5 高架 Int 0：地面道路；1：高架 6 刹车 Int 0：无刹车；1：刹车 7 预留字段 8 接收时间 Char(19) 数据接收到时间，例如2016-03-01T00:00:14 9 GPS时间 Char(19) GPS定位的时间，例如2016-03-01T00:00:14 10 经度 decimal(10, 6) 十进制，小数点后保留6位 11 纬度 decimal(10, 6) 十进制，小数点后保留6位 12 速度 decimal(5, 1) 十进制，小数点后保留1位 13 方向 decimal(5, 1) 十进制，小数点后保留1位 14 卫星个数 tiny int 15 预留字段 表 3所描述的数据为车载监控设备[3]采集的空气监测设备传感数据及本文所需的相关字段。每台车载设备3 s采集一次数据。这些数据根据地面标准监测站的数据做校正之后可提供车辆所覆盖区域的空气质量的实时数据。该数据集包含了2020年从1月至3月在上海市范围内采集的2.8亿条车载空气监测记录。
表 3 车载空气监测设备传感数据
Table 3. Sensor Data of Mobile Air Quality Monitoring Devices
列号 列名 数据类型（精度范围） 中文备注 0 车机号 Small int 出租车标识字符，如B603-0066 1 经度 decimal(10, 6) 十进制，小数点后保留6位 2 纬度 decimal(10, 6) 十进制，小数点后保留6位 3 PM10监测值 decimal(5, 1) 十进制，小数点后保留1位 4 PM2_5监测值 decimal(5, 1) 十进制，小数点后保留1位 5 速度 tiny int 6 时间 Date 数据接收到时间
2019-12-04 00:00:00.001000+08:00两个数据集均包含车辆的唯一性标识符、所处空间位置的经纬度坐标，以及该数据点采样的时间戳。所提供的数据均按日存储，每日文件包含所有车辆当日的百万或千万级记录。
对于不同的应用有着不同的数据管理需求，但所面临的基本功能通常都包括根据车辆标识符及时间范围对车辆轨迹数据进行查询以及根据给定时空范围对车辆轨迹数据进行查询，这两种最基础的查询方式能够支撑大部分功能需求，其他需求能够通过扩展空间范围锁定小的数据集合之后用传统数据方法进行处理。相对于通过存储设计实现直接查询的方法而言，本文解决方案的代价更低。
根据本文所采用的基于空间划分的数据组织和编码方式，每一条记录与其时间序列前后数据的内容、位置均没有关系，而与其自身的空间位置相关，直接针对每一条记录进行S2编码得到两个层级的Cell ID作为全新字段即可。在实现过程中，进一步将日期时间类型的数据转换成秒的形式以提高存储查询效率；此外，由于获取的是数日数据，可以通过并行处理的方式同时对逐日文件进行批量编码，并且筛选出应用所需要的字段用于下一步的数据存储。
实验的系统环境为Ubuntu 18.04.3，开发语言为Python3.6.9，Cassandra版本为3.11.5。
-
表 2和表 3所示的数据集被用于验证本文方法的有效性以及效率。实验过程中，从表 2所示的数据集中随机提取了20万条出租车轨迹数据记录，对有无使用Cell ID进行查询时间对比实验。在使用Cell ID的实验场景中通过Cell ID进行查询，在未使用Cell ID的实验场景中通过经纬度进行查询。实验结果表明，引入Cell ID有效地提升了搜索的性能，通过线性拟合曲线（见图 7）可以得出如下结论：使用Cell ID的效率是未使用的7.45倍。
图 7 有无使用Cell ID根据区域的查询时间对比
Figure 7. Query Time Comparison in an Area with/Without Cell ID
在实际应用中，经常会遇到不间断地存储大规模时空数据的需求。数据存储的效率对于相关的应用系统有着极大的影响。为验证本文提出的存储方式的效率，将本文方法与传统关系型数据库MySQL进行数据实时存储时间对比。将上述数据集中所含的记录（20万条）存入两种数据库中，它们各自所消耗的存储时间见图 8。
图 8 存储时间对比
Figure 8. Comparison of Storing Time
从图 8中可以看出，在存储数据的过程中，MySQL随着数据量的增加，存储操作明显耗费了更多的时间。而本文所提出的方法具有优势，存储数据所耗费的时间更短。
针对查询的效率，利用了表 3所示的数据集，就车辆标识符查询的应用场景与传统关系型数据库MySQL进行比较。表 4和图 9揭示了在不同的数据量的场景之下，根据5个不同的车辆标识符，它们各自所消耗的查询时间。
表 4 查询消耗时间对比表
Table 4. Comparison of Querying Time
总数据量/万条 Cassandra查询时间/s MySQL查询时间/s 5个ID全时段数据量/万条 350 0.142 2.55 3.6 726 0.375 4.77 9.3 1 109 0.714 13.27 16.9 1 497 1.1 19.5 24.4 1 885 1.42 20.86 33.1 2 279.5 1.81 32.87 39.8 2 656.29 2.13 50.57 46 3 031 2.31 58.85 52 3 427.52 2.74 32.05 59.4 4 681.49 3.9 71.43 84.6 5 856.23 4.8 106.98 104.87 7 913.365 2 6.47 112.78 139.76 9 955.085 2 8.2 113.1 174 12 401.82 9.85 140.78 213.2 
图 9 查询时间比较图
Figure 9. Querying Time Comparison
从表 4和图 9所呈现的结果可以清晰地看出，本文所提出的方法相对于传统的关系数据库而言，在大规模的时空数据查询应用方面有更高的效率。在不同数据量的情况之下，本文方法查询所消耗的时间远比MySQL所消耗的时间少，图 9中的线性拟合结果证明MySQL所耗的查询时间（同等条件下）是本文方法的15倍之多，充分证明了本文方法的优势。
-
空气监测数据校准[3]研究需要根据车辆标识符以及时空范围进行查询。图 10展示了对同一区域不同时间段进行时空数据查询的结果，通过此类查询可对该区域内所采集的数据与标准监测站数据进行对比分析，对所采集的空气质量数据进行校对并发布。
图 10 时空范围查询结果
Figure 10. Results of Spatiotemporal Range Query
为了分析一个或几个特定车载设备所监测数据的偏差状态，需要通过对一个或多个车辆标识符进行数据查询并获取空气监测数据，如图 11所示。这些由车载设备检测得到的数据将被用于数据的校正过程。上述两种查询在给定的运行环境之下平均耗时0.614 s，高效的数据查询保障了相关应用的可行性。
图 11 按车辆标识符查询结果
Figure 11. Results of Query upon Vehicle ID
-
本文以高效处理时空轨迹大数据为目的，探索了如何为实际应用提供高效的时空轨迹大数据的存储、索引及查询方法。在分析了现有的方法并归纳它们的优缺点之后，本文提出了基于S2算法与非关系型数据库Cassandra融合设计表结构的解决方案，其中Hilbert曲线被用于实现空间编码。为了进一步提高数据的有效利用，本文提出了数据预处理的流程及方法。实际应用案例验证了本文所提出方法的有效性，其结果符合实际应用的预期。与现有时空数据存储和查询方案比较，本文所提出的方法可提供更高的效率。
后续研究将考虑数据的存储和分布式特点，进一步优化查询算法，提高其效率。在更多的时空大数据应用场景中使用本文所提出的方法，同时开展更全面的方法比较，例如，与PostgreSQL进行性能对比，以期拓展本文方法的改进空间，以及在集群环境下的应用，使其能适应更多的应用场景。
Hilbert Curve and Cassandra Based Indexing and Storing Approach for Large-Scale Spatiotemporal Data
-
摘要: 随着越来越多的轨迹数据被记载，各种应用场景下的海量、复杂数据需要高效的存储与索引。传统的关系型数据库难以满足海量轨迹数据的存储、扩展及特定的查询需求，而具有扩展简单、读写快速、成本低廉特点的非关系型数据库为此提供了一种可行的解决方案。设计并实现了一种基于Cassandra数据库的数据降维及键值存储、索引方法，可对时空轨迹数据进行高效管理。为进一步提高效率，融合了Hilbert曲线编码技术将空间分割成小单元，并将轨迹数据映射到不同单元中。充分利用时空局部性原理，为不同应用场景下的轨迹数据设计并实现了对应的分区键与聚簇键，实现轨迹对象时空近邻存储，令数据查询更为有效。基于实际应用场景的实验结果表明，所提出的方法能有效支撑海量轨迹数据的存储与索引，并在数据的插入、查询及存储结构可扩展性等方面优于其他时空大数据索引和查询方法。Abstract:
Objectives Because of the fast growing acquisition of real-time spatiotemporal data for various applications such as smart city or real-time air-quality monitoring, the traditional database technologies can-not satisfy the higher standards for large-scale data indexing, querying, and storing operations. As the via-ble alternative, NoSQL databases that are scalable and possess fast input/output capabilities offer potential solutions to accommodate the needs. Methods We propose a Hilbert curve and Cassandra technologies based approach for efficient indexing and storing of large-scale spatiotemporal datasets aiming to provide an effective framework for processing, querying, and analyzing large amount of data with spatial and temporal features. For example, the dataset of vehicle trajectories contains valuable spatial and temporal features those are being employed in the real world. The collected spatiotemporal datasets are preprocessed in order to fit the proposed structures for different applications. Specifically, two types of query applications com -monly used in the real world are the spatiotemporal range query and query upon vehicle IDs respectively. Two corresponding indexing structures are designed and implemented in order to accommodate the requests. S2 Geometry Library open sourced by Google is utilized to divide the earth surface into grids, and data points fall in grids are assigned with the specific IDs as the keys. The keys and columns are so designed by applying the Hilbert curve and Cassandra techniques that the resultant structures will physically store the spatially neighboring data points close to each other, and they are more suitable for large-scale spatiotempo-ral data querying and analyzing applications. Results The datasets acquired from the real applications are used to conduct the computational experiments to validate the efficiency of the proposed approach. The que-ry efficiency and the time consumed to store large amount of spatiotemporal data are investigated and bench-marked against some existing database technologies. Conclusions The computational experiments reveal the superiority of the proposed approach comparing to the existing methodologies, the required time to store (insert) data in the database is reduced by 6 times while the time needed to query data is decreased by at least 10 times. The efficiency of the proposed methodology is validate further by applying it to query the vehicle trajectories gathering the real-time air quality data. -
Key words:
- spatiotemporal data /
- Cassandra /
- distributed storage /
- vehicle trajectory /
- database keys /
- spa-tial encoding
-
图 2 Z阶曲线（X轴是纬度数据，Y轴是经度数据）
Figure 2. Z-order Curve (Where X-axis Is Latitude and Y-axis Is Longitude)
图 7 有无使用Cell ID根据区域的查询时间对比
Figure 7. Query Time Comparison in an Area with/Without Cell ID
表 1 Cassandra数据模型中的基本概念
Table 1. Terms Used in Cassandra Data Model
名称 概念 Column Cassandra中最基本的存储单元，用于存储某一列的信息 Primary key 主键，决定每一行数据的唯一性，由分区键和集群键组成 Partition key 分区键，根据Hash值存储数据到不同的物理区域中 Cluster key 集群键(聚簇键)，对于分区中的记录进行排序 
下载: 导出CSV
表 2 强生出租车车载GPS数据
Table 2. Qiangsheng Taxi GPS Data
列号 列名 数据类型（精度范围） 中文备注 0 车机号 Small int 出租车标识，如12345 1 控制字 Var Char ‘A’ 2 报警 Int 1：报警；0：正常 3 空车 Int 1：空车；0：重车 4 顶灯状态 Char 定位状态A：收敛；V：不收敛顶灯状态0:营运；1:待运；2:电调；3:暂停；4:求助；5:停运 5 高架 Int 0：地面道路；1：高架 6 刹车 Int 0：无刹车；1：刹车 7 预留字段 8 接收时间 Char(19) 数据接收到时间，例如2016-03-01T00:00:14 9 GPS时间 Char(19) GPS定位的时间，例如2016-03-01T00:00:14 10 经度 decimal(10, 6) 十进制，小数点后保留6位 11 纬度 decimal(10, 6) 十进制，小数点后保留6位 12 速度 decimal(5, 1) 十进制，小数点后保留1位 13 方向 decimal(5, 1) 十进制，小数点后保留1位 14 卫星个数 tiny int 15 预留字段
下载: 导出CSV
表 3 车载空气监测设备传感数据
Table 3. Sensor Data of Mobile Air Quality Monitoring Devices
列号 列名 数据类型（精度范围） 中文备注 0 车机号 Small int 出租车标识字符，如B603-0066 1 经度 decimal(10, 6) 十进制，小数点后保留6位 2 纬度 decimal(10, 6) 十进制，小数点后保留6位 3 PM10监测值 decimal(5, 1) 十进制，小数点后保留1位 4 PM2_5监测值 decimal(5, 1) 十进制，小数点后保留1位 5 速度 tiny int 6 时间 Date 数据接收到时间
2019-12-04 00:00:00.001000+08:00
下载: 导出CSV
表 4 查询消耗时间对比表
Table 4. Comparison of Querying Time
总数据量/万条 Cassandra查询时间/s MySQL查询时间/s 5个ID全时段数据量/万条 350 0.142 2.55 3.6 726 0.375 4.77 9.3 1 109 0.714 13.27 16.9 1 497 1.1 19.5 24.4 1 885 1.42 20.86 33.1 2 279.5 1.81 32.87 39.8 2 656.29 2.13 50.57 46 3 031 2.31 58.85 52 3 427.52 2.74 32.05 59.4 4 681.49 3.9 71.43 84.6 5 856.23 4.8 106.98 104.87 7 913.365 2 6.47 112.78 139.76 9 955.085 2 8.2 113.1 174 12 401.82 9.85 140.78 213.2
下载: 导出CSV
-
[1] 邬群勇, 张良盼, 吴祖飞. 利用出租车轨迹数据识别城市功能区[J]. 测绘科学技术学报, 2018, 35(4): 86-90 https://www.cnki.com.cn/Article/CJFDTOTAL-JFJC201804015.htm Wu Qunyong, Zhang Liangpan, Wu Zufei. Identifying City Functional Areas Using Taxi Trajectory Data [J]. Journal of Geomatics Science and Technology, 2018, 35(4): 86-90 https://www.cnki.com.cn/Article/CJFDTOTAL-JFJC201804015.htm [2] 刘菊, 许珺, 蔡玲, 等. 基于出租车用户出行的功能区识别[J]. 地球信息科学学报, 2018, 20(11): 1 550-1 561 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201811003.htm Liu Ju, Xu Jun, Cai Lin, et al. Identifying Functional Regions Based on the Spatiotemporal Pattern of Taxi Trajectories[J]. Journal of Geo-Information Science, 2018, 20(11): 1 550-1 561 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201811003.htm [3] 周岩, 谭洪卫, 胡婷莛, 等. 基于移动监测的城市道路PM2. 5和PM10浓度分布研究[J]. 环境工程技术学报, 2017, 7(4): 433-441 doi: 10.3969/j.issn.1674-991X.2017.04.059 Zhou Yan, Tan Hongwei, Hu Tingting, et al. Study on Mass Concentration Distribution of PM2. 5 andPM10 on Urban Roads Based on Mobile Monitoring [J]. Journal of Environmental Engineering Techno- logy, 2017, 7(4): 433-441 doi: 10.3969/j.issn.1674-991X.2017.04.059 [4] Samet H. Foundations of Multidimensional and Metric Data Structures(The Morgan Kaufmann Se-ries in Computer Graphics and Geometric Modeling) [M]. San Francisco: Morgan Kaufmann Publishers Inc, 2005 [5] Qian C, Yi C, Cheng C, et al. Geosot-Based Spa-tiotemporal Index of Massive Trajectory Data[J]. ISPRS International Journal of Geo-Information, 2019, 8(6): 284 doi: 10.3390/ijgi8060284 [6] Hughes J N, Annex A, Eichelberger C N, et al. Geomesa: A Distributed Architecture for Spatiotemporal Fusion[C]//SPIE Defense + Security Symposium, Baltimore, Maryland, USA, 2015 [7] Zhu Q, Gong J, Zhang Y. An Efficient 3D R-tree Spatial Index Method for Virtual Geographic Envi-ronments[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2007, 62(3): 217-224 doi: 10.1016/j.isprsjprs.2007.05.007 [8] Chakka V P, Everspaugh A, Patel J M. Indexing Large Trajectory Data Sets with SETI[C]//Confe-rence on Innovative Data Systems Research, Asilo-mar, CA, USA, 2003 [9] Song Z, Roussopoulos N. Seb-Tree: An Approach to Index Continuously Moving Objects[C]//The 4th International Conference on Mobile Data Manage-ment, Melbourne, Australia, 2003 [10] Pfoser D, Jensen C S, Theodoridis Y. Novel Ap-proaches to the Indexing of Moving Object Trajecto-ries [C]//The 26th International Conference on Very Large Data Bases, Cairo, Egypt, 2000 [11] Li G, Tang J. A New R-tree Spatial Index Based on Space Grid Coordinate Division[C]//International Conference on Informatics, Cybernetics, and Com-puter Engineering, Melbourne, Australia, 2011 [12] Kwon D, Lee S, Lee S. Indexing the Current Posi-tions of Moving Objects Using the Lazy Update Rtree[C]//The 3rd International Conference on Mo-bile Data Management, Singapore, 2002 [13] Xiong X, Aref W G. R-trees with Update Memos [C]//The 22nd International Conference on Data Engineering, Atlanta, GA, USA, 2006 [14] 韩煜星. 面向移动轨迹大数据的查询检索和挖掘算法的研究[D]. 上海: 华东师范大学, 2018 Han Yuxing. Research on Query Optimization and Mining Algorithm for Big Trajectory Data[D]. Shanghai: East China Normal University, 2018 [15] Guan X, Bo C, Li Z, et al. ST-hash: An Efficient Spatiotemporal Index for Massive Trajectory Data in a NoSQL Database[C]//The 25th International Conference on Geoinformatics, Buffalo, NY, USA, 2017 [16] Ding R, Meng X. A Quadtree Based Dynamic Attri-bute Index Structure and Query Process[C]//Inter-national Conference on Computer Networks and Mo-bile Computing, Beijing, China, 2001 [17] 许涛. 基于海量出租车轨迹数据的旅行时间预测[D]. 上海: 华东师范大学, 2017 Xu Tao. Travel Time Prediction Based on Massive Taxi Trajectory Data[D]. Shanghai: East China Normal University, 2017 [18] Huang M, Hu P, Xia L. A Grid Based Trajectory Indexing Method for Moving Objects on Fixed Net-work[C]//The 18th International Conference on Geoinformatics, Beijing, China, 2010 [19] Li R, He H, Wang R, et al. Trajmesa: A Distributed NoSQL Storage Engine for Big Trajectory Data [C]//The 36th International Conference on Data Engineering(ICDE), Dallas, TX, USA, 2020 [20] Wu Z, Li C, Wu Y, et al. Travel Time Estimation Using Spatiotemporal Index Based on Cassandra [J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2018, DOI: 10. 5194/isprs-annals-IV-4-235-2018 [21] 何立志. 基于Hadoop平台的时空数据索引和查询技术研究[D]. 西安: 西安电子科技大学, 2018 He Lizhi. Research on Index and Query Technology of Spatiotemporal Data Based on Hadoop[D]. Xi' an: Xidian University, 2018 [22] 苏敏章. 基于Spark的时空数据查询与分析关键技术研究[D]. 西安: 西安电子科技大学, 2018 Su Minzhang. Research of Query and Analysis Tech-nology for Spatiotemporal Big Data Based on Spark [D]. Xi'an: Xidian University, 2018 [23] Zheng K, Shang S, Yuan N J, et al. Towards Effi-cient Search for Activity Trajectories[C]//The 29th International Conference on Data Engineering (ICDE), Brisbane, QLD, Australia, 2013 [24] Moon B, Jagadish H V, Faloutsos C, et al. Analy-sis of the Clustering Properties of the Hilbert Spacefilling Curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124-141 doi: 10.1109/69.908985 -
点击查看大图
图(11) / 表(4)
计量
- 文章访问数: 1063
- HTML全文浏览量: 407
- PDF下载量: 81
- 被引次数: 0
