管理海量空间数据的利器-空间填充曲线
Published:
现实世界中存在大量的多维空间数据，如加油站位置、河流走向等。为了高效存储和管理海量的空间数据，很多基于Key-Value存储的空间数据库，如GeoMesa[1]、JUST[2]，使用了空间填充曲线技术。它们将多维空间数据转换到一维空间上，并通过转换后的一维空间索引值存储和查询多维数据。本文详细介绍了几种常用的空间填充曲线(Z曲线、Hilbert曲线、XZ-Ordering)的映射算法。
[本文总阅读量: 次]
JUST技术：管理海量空间数据的利器-空间填充曲线
JUST-团队 何华均
现实世界中存在大量的多维空间数据，如加油站位置、河流走向等。为了高效存储和管理海量的空间数据，很多基于Key-Value存储的空间数据库，如GeoMesa[1]、JUST[2]，使用了空间填充曲线技术。它们将多维空间数据转换到一维空间上，并通过转换后的一维空间索引值存储和查询多维数据。本文详细介绍了几种常用的空间填充曲线(Z曲线、Hilbert曲线、XZ-Ordering)的映射算法。
一、简介
随着基础设施和GPS终端的飞速发展，城市中出现了大量的空间对象。这些空间对象可以分为两种类型：点空间对象（例如，POI和GPS点）和空间扩展对象（例如道路、轨迹和行政区域）。许多城市应用通过空间范围查询来高度依赖于空间对象。例如，要预测空间区域的交通流量，我们应该首先需要检索位于该区域的轨迹以计算目前的流量。另一个例子是找到区域中POI、道路和其他空间对象以分析其功能。
但是，出于几个原因，管理空间对象是一项挑战。首先，空间物体通常固有地具有复杂的结构，因为它们通常包含至少纬度和经度的高维信息。对于空间扩展对象，则更加复杂，因为它们通常具有形状、大小、面积和其他属性。其次，空间数据通常具有巨大的规模。例如，每天有60,000多名快递员生成超过1TB的GPS日志，而NASA卫星数据档案库已经超过500TB [3]。具有空间插件的关系数据库，例如MySQL Spatial、Oracle Spatial或者PostGIS，通常会遇到可伸缩性问题，即当数据量到达一定程度时，系统往往不能工作。研究人员在诸如Spark和Hadoop的分布式平台中建立了R-tree，Quad-tree或KD-tree之类的空间索引，以管理大量的空间对象，但是它们可能会出现索引占用大量内存的问题。此外，空间物体是连续产生的。当出现新的空间数据时，这些基于Spark和基于Hadoop的空间数据管理系统通常需要从头开始重建索引以实现良好的查询效率，这非常耗时。为了克服所有上述问题，一些工作使用空间填充曲线（SFC）[4]，例如Z-Ordering[5]、Hilbert[6]、XZ-Ordering[7]，将高维的空间信息转化成了一维信息，在key-value数据库中管理空间对象。
空间填充曲线是一种降低空间维度的技术，是由意大利科学家皮亚诺于1890年首次构造出来的，并由希尔伯特于1891年正式提出的，之后空间填充曲线就得到了深入的研究和广泛的应用[5]。空间填充曲线将高维空间数据映射到一维空间，并利用转换后的索引值存储和查询数据。空间填充曲线通过有限次的递归操作将多维空间划分为众多的网格（如图1所示），再通过一条连续的曲线经过所有的网格。
图1、空间网格
从数学的角度上看，可以将空间填充曲线看成是一种把d 维空间数据转换到1维连续空间上的映射函数。实际上，存储磁盘是一维的存储设备，而空间数据是多维数据，不存在天然的一维顺序。因此，为了使空间上邻近的元素映射也尽可能是一维直线上接近的点，提出了许多的映射方法。最常用的方法包括Z-Ordering[5]、Hilbert[6]曲线和XZ-Ordering，其中Z-Ordering和Hilbert曲线主要用于管理点对象，XZ-Ordering用于管理空间扩展对象，如线和多边形对象。
二、点空间填充曲线
点对象是指只具有经度和纬度的二维空间数据。Z-Ordering和Hilbert曲线常用于管理点对象的空间填充曲线。
Z-Ordering: Z曲线是较简单的空间填充曲线。如图2所示，Z曲线递归地将空间分成四个子空间，直到达到最大递归次数r，最大分辨率控制着最小网格的大小。每一个空间分裂出的四个子空间分别按照图2（a）所示的方式从0到3编号。如果没有达到最大分辨率，则继续划分每一个子空间，并依次递归编码，如图2（b）所示。最终，每个最小网格都会有唯一的编码序列。我们通过一条曲线按照编码的字典序将最大分辨率下的所有网格连起来，可以看到每一层的编码形成的形状类似字母Z。通常，字符串的大小比较没有整数比较效率高，进而影响查询效率。因此，在实际使用中，会将Z曲线的编码序列转化为整数。如图3所示，Z曲线从整数0开始按照曲线的连接顺序对网格依次递增编码。
图2、Z曲线示意图
图3、数值化
Hilbert曲线: Hilbert曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在1891年提出，如图4所示。Hilbert曲线通过把一个正方形空间不断的分成4个子空间，再把小正方形的中心点连接起来得到的曲线，即希尔伯特曲线。在希尔伯特曲线的编码映射中，使用U字型来访问每个空间，对分成的4个子空间也同样使用U字形访问，但要调整U字形的朝向使得相邻的空间能够衔接起来。如图4（a），在第一层时，选择一个起始点和方向，然后用0到3依次给四个子空间编号。然而，当层数大于1时，维护总体的邻接特性，是一件较为复杂的过程。通过不断的观察，我们发现，子空间的曲线是由原空间的简单变换得来，而且只存在四种变换方式，并且相同的变换也适用于子空间的子空间等等。给定一个空间，我们根据它的U字形曲线朝向来确定其四个子空间的U字形曲线朝向和编号。如图5(a)所示，当U字形朝向为下时，Hibert曲线从左下角开始按照顺时针方向分别对其四个子空间编号为0到3，并且进一步划分四个子空间时，它们的U字型朝向分别为左、下、下、右。其它朝向的U字形变换和编号方式，如图5(b)(c)(d)所示。同样地，Hilbert曲线会按照曲线的前进顺序从整数0开始给所有最小的网格编码。
图4、Hilbert曲线示意图
图5、Hilbert曲线的四种变化
三、空间扩展填充曲线
空间数据除了点类型，还有大量的空间扩展对象，如线和多边形。它们通常具有长度、面积等属性。因此，不能被一个经纬度唯一表示。Z曲线和Hibert曲线最终得到的编码只能表示处于最大分辨率的网格。然而，一个空间扩展对象很可能会与多个最小网格相交，因此Z曲线和Hibert曲线都不能用唯一的编码值来表示它。为了利用空间填充曲线来表示空间扩展对象，最简单的方法是用所有与空间扩展对象相交的网格的对应编码表示它，然后将它拷贝多次并存储在每一个编码下。明显地，这种方法会带来额外的存储开销，并且在查询时需要时间执行去重操作。XZ-Ordering解决了上面提到的问题。它扩展Z曲线，提出了一个放大元素的概念。它固定住Z曲线每一个子空间的左下角，然后将其长和高都扩大一倍得到更大的索引空间，得到的索引空间称作扩大元素。如图6（c）中，子空间“00”被扩张到了“0”所覆盖的子空间，“303”扩张为由“303”、“312”、“321”、“330”这四个子空间组成的索引区域。最终，XZ-Ordering利用恰好能完全包含多边形的放大元素来表示多边形，如O1被“303”的扩大元素表示，O1和O3被“00”的扩大元素表示。
图6、XZ-Ordering示意图
由于XZ-Ordering使用到了不同分辨率的索引空间表示多边形对象，因此它的索引空间数量不只是最大分辨率的网格数量。因为，分辨率每增加一次，Z曲线的每个子空间都会分裂出四个新的子空间，而每个子空间也可以扩展为XZ-Ordering的扩大元素。因此，XZ-Ordering拥有个
个处于分辨率i的索引空间。进而，它能表示的所有索引空间的数量为不同分辨率下的索引空间数量的累加值。XZ-Ordering实际能表示的索引空间数量为：
+
，
其中，l表示最大分辨率。
XZ-Ordering同样会用一个整数来表示索引空间，并且尽量满足空间相近的索引空间具有相近的整数值。它的数值化思路可以理解为一种深度优先编码，如图7所示，为XZ-Ordering最大分辨率为2时的编码。先从第0层开始编码为0，然后再按照深度优先访问的顺序编码，如先编码第1层中子空间序号为“0”的空间为1，再编码“00”子空间为2。当编码完“0”开头的所有索引空间后，回退到上一层，再开始编码上一层为“1”的空间为6，再深度编码“1”下面所有的索引空间。
图7、XZ-Ordering最大分辨率为2时的编码
四、总结
空间填充曲线将多维数据转换到一维整数域上，并且尽可能保持了多维空间的特性，使得空间相近的空间在转换后的整数上也尽可能地相近。Z曲线和Hibert曲线是较为常用的空间填充曲线，其中Z曲线较容易实现。XZ-Ordering扩展了Z曲线，使得它能较好地表示非点空间对象，如线和多边形对象。
参考文献：
https://www.geomesa.org/
http://just.urban-computing.com/
Ruiyuan Li, Huajun He, Rubin Wang, Yuchuan Huang, Junwen Liu, Sijie Ruan, Tianfu He, Jie Bao, and Yu Zheng. 2020. Just: Jd urban spatio-temporal data engine. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1558–1569.
Tetsuo Asano, Desh Ranjan, Thomas Roos, Emo Welzl, and Peter Widmayer. 1997. Space-filling curves and their use in the design of geometric data structures. Theoretical Computer Science 181, 1 (1997), 3–15.
https://en.wikipedia.org/wiki/Space-filling_curve
Christian Böhm, Gerald Klump, and Hans-Peter Kriegel. 1999. XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension. In Proceedings of the 6th International Symposium on Advances in Spatial Databases (SSD ‘99). Springer-Verlag, Berlin, Heidelberg, 75–90.