XZ-Ordering Method

1 背景

空间数据库系统的索引结构，主体采用R树索引及其各种变体。这些方法采用树状结构，树中每个节点均对应物理存储中的一页（Page）。该方法的问题在于，当在传统关系型数据库中实现R树时，无法直接和属性数据组合在一起统一管理，必须额外地增加一个索引文件或者索引表单独实现地理空间对象的空间索引，这种方式也被称为混合索引方案。这种混合索引方案存在以下几个方面问题：

非常难以维护，因为要保持两种结构的同步更新。如果一方更新失败，都会导致另一方被迫停止。为实现这一目的，必须要实现一种面向同质数据库系统的分布式提交协议，这需要对数据库内部技术细节非常了解，实现起来也非常耗时。采取混合索引方案会带来其他问题，例如：文件系统和数据库系统采用的是完全不同的数据安全策略、备份策略和并发访问策略，维护起来非常复杂。

面向对象数据库系统（另外一种NoSQL数据库）可能是解决上述问题的一种方案，因为面向对象数据库可以扩展面向应用的数据类型。但是在对象数据库中，如果要实现多维索引结构，也需要使用数据管理系统在块层级的存储管理访问接口，而大部分数据库管理系统并不提供这种接口，因此实际操作起来并不现实。

综上所述，在关系型数据库或对象数据库中实现空间索引，最便于实现的方式是将空间属性映射到关系模型中。

空间填充曲线作为一种将多维空间映射到一维空间的方法，不仅能够实现降维，同时还能够保持多维空间中的邻近性，即多维空间中相邻的点近似在一维的空间填充曲线上也距离也相近。虽然这种距离保持在概念上并不严格，但是通常可以查询时，将匹配对象限制在嵌入空间的有限区域内。因此，特别适合于在数据检索过程中的粗过滤阶段。

注：多边形的空间索引通常分为两到三个阶段：第一个阶段为过滤（filtering），即对于任何空间检索窗口或区域，首先通过过滤命中可能与检索区域相交的对象集合，滤除与检索区域肯定不想交的对象，从而缩小检索范围；后续第二或三个阶段在过滤数据集基础上进行精化（refinement），采用的主要方法是建立空间对象的外包多边形、凸包等形状估算模型，在精化过程中，对这些估算模型和检索窗口进行相交判断，返回真的为最终命中对象。由此可见，不同的形状估算模型的空间检索命中精度是不同的。形状估算模型越精确，命中精度越高，越粗略，命中精度越低。但是由于高的估算意味着更多的存储和计算资源成本，造成最终命中精度和形状估算模型精度之间的矛盾，需要根据实际需求做权衡（trade-off）。

2 定义与术语

几个重要概念的定义如图1：

（1）工作空间（Workspace）：指索引建立的整个矩形区域，为便于数学描述，定义该空间为归一化空间，x和y的定义域均为 $[0,1]$ 。

（2）象限（Quadrant）：Z序采用四分法从整个工作空间开始迭代向下四分，每次四分都会产生四个象限，按照图中的Z形分别给以编号为 $q=\{0,1,2,3\}$ 。

（3）分辨率层级（Resolution Level）：Z序中的每一次四分，都会照1/4的分辨率对整个工作空间进行新的划分，称第 $l$ 次划分对应的分辨率层级为 $l$ 。

（4）象限序列（Quadrant Sequence）：随着Z序的四分，按照自顶向下的层级关系，会形成一个不同层级象限编号连接形成的象限序列 $<q_1q_2q_3q_4...q_l>，记为Q,$ 其中 $l$ 为序列长度，也代表该序列所在的分辨率层级。整个工作空间被划分为无缝、无叠、层层嵌套的划分体系。

（5）元素（Element）：上述某个象限序列所对应的区域（region），被称为元素。根据四分法和象限序列的定义可知：a）象限序列 $l$ 长度越长，所在层级越深，分辨率越细；b)当某个元素$$e_1$$包含另外一个元素$$e_2$$时， $l_{e1}\le l_{e2}$ , 同时也意味着 $$e_1$$ 的象限序列 $$Q（e_1)$$ 是 $$e_2$$ 的象限系列 $$Q（e_2）$$ 的前缀，反之亦然；c) 在归一化的工作空间中， $l$ 层某个元素的面积为 $(\frac{1}{4})^l$ 。

（6）细胞（Cell）：在一个Z序划分体系中，最优分辨率层级（或最深分辨率层次）中的元素，被称为细胞。它是构成工作空间的最小单位，通常定义其序列长度或分辨率层级为 $g$ ， $g$ 是所有分辨率层级 $l$ 的最大值。

（7）上包（Up Hull）：包含某个元素 $e$ 的祖先层级中的元素集合，被称为该元素的上包$ UpSet{ e })$。

（8）下包（Down Hull)：被某个元素 $e$ 所包含的子孙层级中的元素集合，被称为该元素的下包 $DownSet\{ e \}$ 。

3 Z序研究情况

3.1 Z序在点数据集空间索引中的应用

点数据比较简单，比较直观的做法是采用最佳分辨率，即用细胞来描述一个点。所有点数据均映射在g层上，其象限序列长度相等。通常可将象限序列直接转化为数值类型，其数值不失象限序列本身的保序性，同时结合B+树建立索引结构。各种关系型数据库大多默认主索引为B+树，因此，可以将上述象限序列的数值作为关系表中的主键，利用数据库自身的B+树索引实现快速查询法访问。由于象限序列具有一定的保序性，意味着在物理存储上，空间上相邻的点对象很大几率存储在同一块或者连续的若干块中，因此可以大大降低IO吞吐次数，并利用预读提升IO效率。

注：B+树是考虑到物理存储中块设备的IO特性考虑的一种多扇出平衡树，其出度根据块存储设备中Page或Block的大小来决定，是一种应用非常广泛的外部索引方式，Oracle、MySQL InnoDB、PostSQL等均默认采用B+树索引结构。

3.2 点数据集的Z序查询

以窗口查询为例，整个工作空间从第一层四分开始，逐元素地与查询窗口的做相交判断，会出现三种情况：

元素与查询窗口不想交，则什么也不做；
元素被查询窗口完全包含，则对当前元素包含的所有细胞进行标记。具体实现时，无论采用象限序列还是采用数值方式，因为其长度相同，均可排序，所以查询条件可以定义为排序空间中的一个区段（interval）；
元素与查询窗口相交时，对当前元素按照前述两步迭代四分直至最佳分辨率，并将最佳分辨率中相交的细胞做标记。

将上述各步骤标记形成的区段集合，作为查询检索的条件，对3.1中的索引结构进行多个区间查找，得到查询结果。

基于Z序的查询过程，将空间查询转换为了数值上的区间检索，充分利用了编码有序的优势，效果较好。

3.3 多边形的问题

上述方法对抽象为点的数据比较有用，但是对于具有空间范围的其他数据类型，如：矩形、多边形等，我们会面临新的问题。即如果像点数据一样按照最佳分辨率进行分割（naive approach），则每个多边形可以与很多细胞相交。如果采取这种做法将导致巨量的存储（有人说：空间复杂度不是问题，未来存储不值钱，这种说法其实是在找不出解决方案时的回避），除非采用更为粗糙的划分。因此，有很多方法在探讨如何在使用更优网格分辨率的同时，降低开销。

3.4 多边形对象的单值估算模型及其存在的问题

单值估算模型即对每个多边形只赋予一个象限序列，其做法从整个工作空间的四分开始：

当多边形与象限元素不相交时，什么也不做；
当多边形与单个象限元素相交时，向下迭代四分，直至出现多个象限元素相交的层级；
采用此时的象限序列作为多边形对象的唯一索引码，而非 $3.3$ 提到的多个序列码，因此被称为单值估算模型；

单值估算模型的最大问题在于：
不同多边形对象的象限序列长度不一，只能用字符串来表示；
由于无法转换为数值类型，所以无法按照固定长度的做法采用排序区间代替空间范围查询；
当多边形包含工作空间的中心点（即 $[0.5,0.5]$ ）时，不管该多边形实际面积有多大，总是被分配为空的象限序列（即整个工作空间），这意味如果根据相交关系做检索，无论你怎么做，这些多边形都将在检索结果中。

3.5 多值估算模型及冗余的优化

针对单值估算模型存在的问题，有学者提出一种介于最佳分辨率模型和单值估算模型之间的一种方法。其做法是在自顶向下的四分过程中，不再一律分割到最佳分辨率层次，而是设定两种不同的阈值来控制四分的过程，它们分别是尺寸边界（size-bound）和误差边界（error-bound）。尺寸边界指当多边形对象分割产生的元素数量到达指定尺寸时，则四分终止。误差边界指当迭代四分产生的元素占据的面积与多边形对象实际面积之差或比例达到某个阈值时，四分终止。两种方法都能够避免最佳分辨率模型的巨大开销问题，也能避免单值模型中的变长和中心点问题，但还存在其他问题：

不同多边形对象的象限序列依然是变长的，很难发挥其排序作用；
在索引结构中，一个多边形对象对应多个元素的象限序列，造成索引结构上的冗余，在进行检索时必须做去重处理；
为了避免重复存储后续精化阶段所需的外包矩形、凸包等精细形状估计模型数据（此类数据量较象限序列本身大很多），只能在多边形数据表外，建立一个多对多的关系表或倒排索引表，从而带来更多麻烦。

好消息是，相关学者在提出多值估算模型的同时，发现根据查询窗口生成的区间（interval）数量正比于与查询窗口边界相交的细胞数量。这意味着过优的分辨率不仅导致系统开销增加，还会造成数量巨大的区间查询，而每次区间查询都会占用一次数据库的IO，进而严重恶化数据库的检索性能（查询区间数量多，意味着要实现更多次的范围查询）。

注：目前利用ES、MySQL、hBase等数据库实现剖分索引时，大部分采用的都是多值估算模型。在实现过程上，多为”剖分网格码 -> 对象ID --> RecordRow“，因此，上述问题全都存在，效率不可能高。最恶略的情况下，当查询结果包括N个多边形时，可能要做N次IO吞吐。

4 XZ-Ordering原理与方法

鉴于上述分析，德国慕尼黑大学学者Christian Böhm提出了一种扩展Z序（eXtendZ-Ordering）的索引方法。其主要技巧在于一下3点：

4.1 提出一种相互重叠的扩展元素和细胞的概念

在传统方法中，一个象限序列对应一个元素或细胞，元素和细胞之间无缝无叠。而仔细分析Z序体系下的多边形对象，会发现任意一个多边形，总能在某一层次上被相邻并构成矩形的四个元素所覆盖（见下图），而且存在三种情况：

四个元素均没有相同的祖先；
其中两个水平或垂直方向相邻的元素具有相同的祖先；
四个元素拥有共同的祖先。

其中情况3是我们最希望达到的效果，而情况1和情况2都会造成冗余。由此可以设想，是否可以对元素和细胞的范围做重新定义，用图2中左下角元素的象限序列，描述整个四个元素覆盖的区域。这样的话，所有多边形总能够在某一个层级上找到一个唯一的象限序列，其代表的区域能够完全覆盖该多边形，而不受刚性四分网格划分的影响。这种用左下角元素的象限序列来描述一个四倍于它区域的方法，被称之为扩展Z序（XZ-Ordering)。其中每一个扩充了面积后的元素或细胞，被称为扩展元素和扩展细胞。

fig3 扩展单元示意图

在XZ-Ordering中，元素和细胞不再是无缝无叠，根据其定义可以发现，a）扩展元素和细胞的面积是原始元素和细胞的4倍； b）相邻的两个扩展元素之间，总是有50%的重叠。

Christian Böhm基于扩展单元的定义，还提出了确定多边形对象分割尺度的引理：

引理1：象限序列的最小和最大长度

在归一化空间中，长宽为 $（w,h）$ 的多边形，其在XZ序下的象限序列 $\it s$ 的长度 $|\it s|$ ，遵循以下不等式：

l_1 ≤ |\it{s}| < l_2 \qquad with\qquad \lfloor l_1 = log_{0.5}(max\{\it w,\it h \})\rfloor\qquad and\qquad l_2 = l_1 + 2

$|\it s|$ 的具体计算方法如下：

对多边形对象的外包矩形 $（w,h）$ ，在两个坐标方向均做归一化处理；
选取 $\it w$ 和 $\it h$ 的最大值 $max$ （归一化后小于1）；
求 $log_{0.5}(max)$ ，并向下取整得到 $l_1$ ;
$|\it s|$ 应当大于等于 $l_1$ ，小于 $l_1+2$ ，即 $|s| = l_1$ 或者 $|s| = l_1+1$

对于利用扩展元素或细胞来描述多边形边界的方法，Christian Böhm给出了关于其估算误差的引理：

引理：最大估算误差

作为多边形单值估算的扩展元素，其面积与多边形对象的实际面积之间的相对误差有上限，最大不超过15，而大多数情况小于等于3。

证明略。

4.2 提出了一种具备保序性的变长象限序列字符串向数值类型转换的算法

根据扩展元素的定义和相关引理可知，在XZ序下获得的多边形的象限序列也是不定长的，难以将其作为数值类型直接用于关系型数据库中，从而无法实现利用数值类型的排序优势实现区间检索。因此，Christian Böhm很巧妙地设计了一种由变长象限序列计算得到的数值码 $C(s)$ ，同时证明了 $C(s)$ 能够保留原有象限序列的词典排序关系，从而为基于数值的区间检索奠定了基础。即自顶向下产生的变长象限序列的总数量和转换后的数值区间保持一致，两者之间能够一一映射，长度不同的任意象限序列字符串总能够在映射后的数值区间中对应一个且唯一一个数值。

C(s) = \sum_{0\le i <l}q_i.\frac{4^{g-i}-1}{3}+1

4.3 优化了根据查询区域生成查询元素数值区间集合的方法

4.3.1 插入和删除操作

根据 $4.1$ , $4.2$ 中XZ序列的生成机理，所有多边形对象按照 $4.1$ 生成其对应扩展元素的象限序列 $Q(s)$ ，而后按照 $4.2$ 将该象限序列映射为二进制数值码 $C(s)$ ，然后将 $C(s)$ 作为主键，存储在关系型数据库中，进而基于主键实现插入和删除操作。在算法实现过程中，上述两步可合并在一个迭代循环中，其时间复杂度为 $O(l)$ 。

4.3.2 基于编码的查询检索

以窗口查询为例，其原理与 $3.2$ 大致相同。不同之处在于， $3.2$ 检索的点对象均为细胞，其对查询窗口的迭代四分最终会到达细胞级，从而形成多个细胞编码区段构成的集合。XZ序方法可能包含多个层级的元素，无法统一在细胞级的编码区段上进行检索。因此，相应的查询检索流程稍有不同：

整个工作空间从第一层四分开始，逐扩展元素地与查询窗口做相交判断，会出现三种情况。

扩展元素与查询窗口不想交，则什么也不做；
扩展元素被查询窗口完全包含，则对当前扩展元素的象限序列、以该象限序列为前缀的所有象限序列做XZ值转换，并生成相应的XZ值区段，标记该区段；
扩展元素与查询窗口相交，对当前扩展元素的XZ值进行标记，然后对当前扩展元素按照前述两步迭代四分直至最佳分辨率层；
对上述各步骤标记形成的区段集合，进行去重合并，并作为查询检索条件，对索引结构进行多个区间查找，得到查询结果。

基于XZ序的查询过程，类似Z序过程，其将空间查询转换为了XZ数值码上的区间检索，充分利用了数值类型有序且定长的优势，并很好的解决了单值估算模型的聚集问题和多值估算模型的冗余问题。此外，通过在迭代过程中的标记，同时实现了上包和下包的检索，从而实现了多层级一体化的查询。

4.3.3 查询条件的优化

根据 $4.3.2$ 节所述，窗口查询将最终将转变成对 $n_{intervals}$ 个数值区间的查询。问题在于，当 $g$ 过优时，会产生大量的扩展元素和区段。平均情况下， $n_{intervals}$ 的空间复杂度为 $O(2^g)$ 。比较一般性的做法是限定查询窗口向下分解的层次 $l$ ，强制性地限制元素和查询区段的数量，但这种方法的粗过滤精度只能达到 $l$ ，无法做到更精细的查询。

如果不加证明的假设，当 $l$ 增加时，其所对应的层级生成的元素和区段数量也会增加，其最大增长速度为4倍。基于这种假设，Christian Böhm提出的另外一种优化算法：即当 $n_{intervals}(l)$ 过大时，就对该层级内的区段集合做合并处理。

概念上假设：层级从 $l$ 增加到 $l+1$ 时，区段的数量将从 $n_l(intervals)$ 变为 $4*n_{intervals}(l)$ 。基于此假设，我们只需要找到合适的 $l$ ，并对 $l$ 后的层级进行区段合并即可。

该算法较大地优化数据库查询的检索吞吐率。其中，需要考虑不同层级区段间的间距（gap）问题。原则上当 $l$ 递减时，相应间距应当加大，即 $gap(l-1)>gap(l)\}>gap(l+1)$ 。

Christian Böhm提出的算法限定每个层次区段总数 $n_{max}$ ，而不是将 $g$ 作为超参数。该方法的好处在于产生的区段总数在可预计的范围内，缺点是造成粗过滤的误检率增高。

在实现算法层面，优化算法采用深度优先的算法，包括两个阶段：

第一个阶段（见下图)采用深度优先遍历，统计每一层次的区段数量 $n_{intervals}(l))$ ，并选择其中区段数量最接近于 $n_{max}$ 的那个层次作为查询窗口分解的最佳分辨率层 $L_{suitable}$ （实际选择的是区段数大于等于 $n_{max}$ 的层中，最小的那一层）。

第二个阶段，依然采用深度优先遍历的方法，对 $[l_{suitable}，g]$ 中的所有层级，依据 $n_{intervals}(l)$ 对该层的区段做合并处理，当 $n_{intervals}(l)>n_{max}$ 时，合并区段间隔最小的那两个区段，循环直至 $n_{intervals}(l)\le n_{max}$ 。第二个阶段将每一层的最大区段数，都限制在了 $n_{max}$ 内，从而降低了总区段数。