近年来智能城市建设在云计算和大数据技术的推动下，取得了飞跃式的发展，产生了海量可记录的数据，如文本、视频、传感器读数等。每年移动互联网接入流量消费超过711亿GB，其中，80%的数据都与时空相关。北京出租车三个月内产生了远超790万条轨迹数据，NASA卫星数据档案库已经超过500TB。迅速产生的时空数据，背后蕴藏着巨大的对智能城市发展有用的信息。如，根据交通轨迹来优化交通信号灯的时间、实时提醒路况、辅助规划交通道路等。此外，时空数据还在农业、金融、环境、能源等方面拥有众多的应用。这一系列的时空应用，加快推动了时空数据处理的需求。然而，时空数据的产生速度和体量决定了传统数据库不能满足其存储和分析的需求。因此，需要利用分布式数据库管理这些海量的时空数据。近年来快速发展的分布式技术可以为海量数据的存储与查询提供有效的支持。时空数据，特别是位置点数据，具有产生快、数量大的特点。因此，对吞吐量的要求往往很高。建立在Hadoop文件系统之上的分布式数据库HBase，基于谷歌的Big Table设计，可以提供快速随机读/写访问海量数据的能力。因此，很多企业都采用HBase管理海量数据。HBase中的数据按照RowKey单维度排序组织。然而，时空数据具有多维属性，至少具有经度和纬度两个维度，而分布式存储一般以键值对的形式组织数据，很难直接存储时空数据。因此，为了高效地支持时空数据的存储和查询，需要引入时空索引技术便于在分布式数据库中管理多维时空数据。传统关系型数据库主要基于B-Tree数据结构组织数据，可以很好地支持单维数值范围等查询，如查询属性A > 1000的记录。然而，对于时空数据，要支持的基础查询场景更为复杂：如这些查询往往需要调用时空范围查询，如二维空间范围加一维时间范围，是多维度的范围。针对时空数据的特殊查询场景，已经有很多常用的索引技术，可高效地支持特定的时空范围查询。这里我们主要介绍R-Tree、Quad-Tree、K-DTree、以及Space Filling Curve、LSH这五种技术。R-Tree是一种平衡树，它只在叶节点中存放指向数据的指针，由Guttman在1984年SIGMOD中提出[1]。Guttman首先提出了MBR的概念，即小边界矩形Minimum Bounding Box，如图1所示，其用一个边平行于坐标轴的小的矩形框住空间对象。在查询时，只需要先找到空间对象的MBR即可。找MBR的任务相对于直接寻找空间对象本身来说容易了很多。R-tree吸纳了B+tree的思想，对数据进行分割。多个相邻的MBR，可以被包含在一个更大的MBR中，如图2中R6、R9以及R10三个矩形，可以被包含在R3中，而R11与R12则被包含在R4中。因此，可以用一个更大的MBR框住内层的小MBR。继续迭代，总能找到若干个大的区域，如图2所示。一层一层构建MBR的操作，非常类似B+tree的构建，终以一种类树状的形式，将所有的时空对象给容纳进去，如图3所示。查询时，通过先找外层的MBR，再不断遍历相交的子层，我们便可以很快找到内层MBR的大概位置。R-Tree有多种变种，如R+-Tree，R*-Tree，X-Tree,M-Tree，BR-Tree等等，其提升主要是针对MBR的分割算法方面的, 本文不再展开介绍。Quad-Tree的初设计源自论文《Quad Trees: A Data Structure for Retrieval on Composite Keys》[2]。Quad-Tree在二维上将空间分为四组相同的子象限，且只有每个叶节点中会包含有关时空数据。Quad-Tree里的每个节点要么正好有4个子节点，要么就是没有子节点(为一个树叶节点)。如图4所示，是一种典型的Quad-Tree。同样地，Quad-Tree也可以表示为树状结构，如图5所示。执行空间查询时，首先从根节点开始检查子节点是否与查询范围相交，如果相交则继续检查子节点，直到达到叶子节点。如果不与查询范围相交，则不再继续检索其子节点。与Quad Tree思想类似，K-D Tree也会将整个空间不断进行分割，终得到较为合适的分割区域。不同之处在于，QuadTree每一次分割，都将当前区域分割为等大小的四个子象限。而K-D Tree则是分成左右或上下两个区间。K-D Tree根据每个维度上数据的方差，取大方差的维度作为分割轴，并对当前数据按分割轴维度进行检索，找到中位数数据，再根据所有数据与中位数当前维度值的大小关系，确定其它数据所属分支。如图6中，从左边开始的第三根红色线将整个区域分割为了左右两个区间，从上开始的根蓝色线将上一步红色线分割出的右边区域再次分割成了两个区域。因为K-D Tree每一次分割都会得到两个子空间，所以可以得到类似二叉树的结构。因此，K-DTree的空间查询类似二叉树的遍历检索过程。空间填充曲线是一种降低空间维度的技术，是由意大利科学家皮亚诺于1890年构造出来的，并由希尔伯特于1891年正式提出的，之后空间填充曲线就得到了深入的研究和广泛的应用[5]。空间填充曲线可将高维空间数据映射到一维空间上，其通过有限次的递归操作将多维空间划分为众多的网格（如图7所示），再通过一条连续的曲线经过所有的网格。因“串”的方式不同，也就衍生了不同的SFC算法。其中，比较典型的为Z-Order、Hilbert Curve。如图7所示，Z曲线递归地将空间分成四个子空间，每一个空间分裂出的四个子空间分别按照图7（a）所示的方式从0到3编号，直到达到大递归次数r，大递归数控制着小网格的大小。如果没有达到大分辨率，则继续划分每一个子空间，并依次递归编码，如图7（b）所示。终，每个小网格都会有的编码序列。我们通过一条曲线按照编码的字典序列将大分辨率下的所有网格连起来，可以看到每一层的编码形成的形状类似字母Z。Hilbert曲线是一种能填充满一个平面正方形的分形曲线。如图8所示，Hilbert曲线通过把一个正方形空间不断的分成4个子空间，再把小正方形的中心点连接起来得到的曲线，即希尔伯特曲线。在希尔伯特曲线的编码映射中，使用U字型来访问每个空间，对分成的4个子空间也同样使用U字形访问，但要调整U字形的朝向使得相邻的空间能够衔接起来。评价一种SpatialFilling Curve的优劣，有两个关键的维度：（1）空间特性保留度：SFC将空间对象映射到一维后，如果两个对象在二维空间上是相近的，那么，在一维曲线中也应该尽可能是相近的。因此，一个好的曲线，理应更大程度上使得在一维曲线中维持空间对象在二维空间上的空间邻近性。对于查询而言，更高的空间特性保留度，也意味着更高的命中率。（2）编码复杂度：可以简单理解为将空间对象映射成一维的计算复杂度。Z-Order在空间特性的保留度上稍微低于Hilbert曲线。但在编码复杂度上，Z-Order更低。因此，很多分布式技术采用Z-Order管理空间数据，如GeoMesa和JUST[7]。3.5 LSH（Locality Sensitive Hashing）LSH（局部敏感哈希）是一系列可以将数据从高维度映射到低维度，同时使得在高维度相近的数据在低维度也大概率相近的哈希函数。对于一个相似性函数s，局部敏感哈希族H是一组哈希函数，其对于任意两个对象有即，对于，随机选取的哈希函数会使它们得到同一哈希值的概率与它们本身的相似度相近。局部敏感哈希终希望得到满足下列条件的哈希表：其中，表示p和q相似。表示p和q相异。根据实际场景，相似度的定义会有不同，局部敏感哈希算法设计也有不同，更多细节请查看文献[6]。HBase基于LSM-Tree架构，底层HFile文件以B+Tree形式组织。在不影响HBase现有架构的基础上，我们来分别探讨一下各种时空索引与HBase的结合方式。从R-Tree的设计上来看，其充分利用了Disk Page的优势。因此，它支持数据的随机写入能力，并能够做到自平衡。它非常适合多边形对象的存储。但是，HBase的数据按Rowkey排序，并按Rowkey进行快速检索。因此，需要提供一种方法，使得R-Tree中的数据按照Rowkey字典排序。然而，在R-Tree的设计中弱化了对数据排序的功能。因为，其节点与子节点之间，更多的是一种包含与被包含关系。并且，当一个叶子节点承载多过数据时，还可能出现分裂的状态。因此，按照传统的树遍历顺序对R-Tree中的对象排序，会导致顺序不确定等问题，这意味着根据R-tree很难构建出一种很好的Rowkey。对于Quad-Tree来说，其分区可不依赖于数据本身，也与数据写入顺序无关。但随着数据的不断写入Quad-Tree可能需要进一步拆成四个子空间，导致原有数据在树中的层次也发生变化。因此，Quad-Tree也不便于直接应用于HBase。但对其稍加改造过后便可很好的支持HBase。上面提到的方法可使Quad-Tree很好地支持HBase的思想，也可看作Spatial Filling Curve的核心思想。SFC首先会确定好树的大层次，并且会通过一条曲线串联起大层次的每一个空间，进而根据曲线访问的顺序确定每一个空间的编码，并映射为HBase的Rowkey。LSH本身是一个哈希函数表，因此它可以很快速地将数据转换到一维上，进而组成Rowkey。[1] Guttman, Antonin. "R-trees: A dynamicindex structure for spatial searching." Proceedings of the 1984ACM SIGMOD international conference on Management of data. 1984.[2] Finkel, Raphael A., and Jon Louis Bentley."Quad trees a data structure for retrieval on composite keys." Actainformatica 4.1 (1974): 1-9.[3] Jaison. HBase与时空索引技术，http://www.nosqlnotes.com/technotes/hbase/hbase-spatial-index/[4] 李喆. 空间索引技术，https://zhuanlan.zhihu.com/p/38597148[5] 维基百科. 空间填充曲线, https://en.wikipedia.org/wiki/Space-filling_curve[6] Lv, Qin, et al. "Multi-probe LSH: efficient indexing forhigh-dimensional similarity search." 33rd International Conference on VeryLarge Data Bases, VLDB 2007. Association for Computing Machinery, Inc, 2007.[7] Ruiyuan Li, Huajun He, Rubin Wang, Yuchuan Huang, Junwen Liu, SijieRuan, Tianfu He, Jie Bao, Yu Zheng. JUST: JD Urban Spatio-Temporal Data Engine.The 36th IEEE International Conference on Data Engineering. (ICDE 2020)
转载请注明：康瑞部落 » HBsae与时空索引技术杂谈