空间填充曲线的聚簇性分析

一、概述

先说结论，作者将曲线分为连续型（Hillbert、Peano等）、近连续型、非连续型（Z序、Morton等）分开讨论。

1.1 关于矩形查询的通用结论

（1）对于固定尺寸的“矩形查询 $r$ ”，存在一个平均簇值的最优解（下限）。

（2）上述最优解（下限）受限于 $r$ 的体积（用r中的单元数做量化）和形状（用 $r$ 中各维度上的边数来量化）。

（3）通常连续性曲线较非连续型曲线更接近最优解（下限）。

（4）对于固定尺寸的“矩形查询 $r$ “ ，仅考虑部分旋转集时，总是构造一种连续型曲线，使其平均簇值达到最优值（下限）。

（5）对于固定尺寸的“矩形查询 $r$ ”，考虑其全旋转集时，所有连续型曲线的平均簇值都是最优解。

1.2 关于连续型曲线的结论

（1）对于连续型填充曲线，通过将某个查询 $g$ 在各维度上做所有可能的平移后，得出统计结论：

该情况下，查询 $g$ 的平均簇值仅和 $g$ 的体积（用 $g$ 内的单元数做量化）、形状（用 $g$ 在各维度上边的数量来量化），以及填充曲线中各维度的边占比有关（用填充曲线中各维度上的边数占曲线总边数的比率来量化）。

（2）对于连续型填充曲线，考虑查询 $g$ 的部分旋转集（查询g在若干维度上做旋转和所有可能的平移后得到的查询集合，被称为部分旋转集），得出结论：

该情况下，查询 $g$ 的平均簇值仅和 $g$ 的体积（用 $g$ 内的单元数做量化）、 $g$ 的若干种旋转形（用 $g$ 做若干旋转后，各维度上边的平均值做量化）、填充曲线中各维度的边占边有关（用填充曲线中各维度的边数占曲线总边数的比率量化）。

（3）对于连续性填充曲线，考虑查询g的全旋转集（查询 $g$ 在所可能的旋转和平移后得到的查询集合），得出统计结论：

该情况下，查询 $g$ 的平均簇值仅和 $g$ 的表面积（用 $g$ 的壳中单元的数量做量化）、空间的维度 $d$ 有关，和曲线形式无关。

（4）对于对称型曲线（一种特殊的连续型曲线，曲线上各维度的边占比均为1/d），

$g$ 的平均簇值和旋转集的内容无关，仅和 $g$ 的表面积以及空间的维度有关。

1.3 关于近连续型填充曲线的结论

（1）对于近连续型曲线，在考虑部分旋转集时，得出结论：

其平均簇值也是可以计算的，查询g的平均簇值仅和g的体积（用g内的单元数做量化）、g的若干种旋转形（用g做若干旋转后，各维度上边的平均值做量化）、填充曲线中各维度的边占边（用填充曲线中各维度的边数占曲线总边数的比率量化）有关。

1.4 关于Z序填充曲线的结论

非连续型填充曲线过于复杂，仅针对Z序的立方体型查询得出结论，其他问题尚无解。

（1）对于立方体型的查询（各种旋转的结果等于自身），其平均簇值是立方体边长和空间维度的函数。

二、基本定义

2.1 与空间、曲线相关的若干定义

定义2.1空间 $U$ 邻边集合 $E(U)$ 定义

（1）假设 $v_1,v_2$ 是空间 $U$ 中的两个点，当两者的曼哈顿距离为1时，定义其为一条邻边 $e = (v_1,v_2)$ ；

（2） $U$ 中所有邻边的集合，被称为空间 $U$ 的邻边集合 $E(U)$ ；

（3）如果 $E(U)$ 中的某条邻边 $e=(v_1,v_2)$ ，仅在第 $i$ 维上坐标不同，其他维上坐标均相等，则称 $e$ 为沿维度 $i$ 的邻边；

（4） $E(U)$ 中所有沿维度 $i$ 的邻边构成的集合，定义为第 $i$ 维上的邻边集合 $E_i(U)$ ；

（5）邻边和邻边集合仅与空间U有关，和填充曲线及查询无关。

定义2.2空间填充曲线 $π$ 的定义

面向 $d$ 维空间 $U$ 的填充曲线 $\pi : U->{0,1,...,n-1}$

该定义代表一个双射系统，即多维空间中的 $cell$ 和填充曲线中的值之间是一一对应的。

定义2.3连续型填充曲线和近连续型填充曲线的定义

（1）连续型填充曲线的定义

当 $\pi^{-1}(i)$ 和 $\pi^{-1}(i+1)$ 在空间U中的曼哈顿距离总是等于1时，填充曲线 $π$ 被称为连续型填充曲线。

即对于 $π$ 中任意任意一点 $i（0\le i \le n-2）$ , 和其下一个点 $i+1$ 在空间U上所映射的两个单元 $\alpha,\beta$ 之间的曼哈顿距离总是为1。

根据定义：

因为填充曲线是双射的，所以$ \pi (\beta) = \pi (\alpha)+1$ ；
边 $（\alpha,\beta）\in E_i(U)$ ，其中 $E_i(U)$ 为空间 $U$ 中，第 $i$ 维上相邻两个单元构成的边的集合；
希尔伯特曲线、行优先曲线、peano曲线都是连续型曲线，因为其所有 $i和i+1$ 在 $U$ 中的曼哈顿距离均为1
$Z$ 序曲线不是连续型曲线，因为其在部分 $i$ 和 $i+1$ 之间的曼哈顿距离大于1

（2）近连续型填充曲线的定义

类似连续型填充曲线的定义，当 $（\alpha,\beta）$ 的在各维度上坐标差的最大值等于1时，被称为近连续型曲线。

根据定义可知，近连续型曲线较连续型填充曲线增加了对角的情况。

**定义2.4 填充曲线的边占比、边占比向量 $\mu(\pi)$ **

（1）沿着填充曲线，在某维度上存在的相邻边的集合定义为 $N^i(π)$ ，其数量为 $|N^i(π)|$ ，根据定义可知， $\sum\limits_{i=1}^d{|N_i(\pi)} \le n-1$ ，例如：希尔伯特曲线其和等于n-1，而Z序曲线的和小于n-1。

（2）某维度上相邻边数在总边数中的比率，被定义为边占比 $\mu_i(π) = \lim\limits_{n\rightarrow\infty}\dfrac{N^i(π)}{n-1}$

（3）各维度的边占比构成的向量，被称为边占比向量 $\mu(\pi)$

$\mu(π) = <\mu_1(π),\mu_2(π),...，\mu_d(π)>$ 。

以二维空间为例：

（1）希尔伯特曲线： $\mu_1(π) = \mu_2(π)=\dfrac{1}{2}$ ， $\mu(\pi) = <\dfrac{1}{2},\dfrac{1}{2}>$ ，由于各占比之和为1，所以该曲线是连续型曲线；

（2）行优先曲线： $\mu_1(π)= 1，\mu_2(π) = 0$ , $\mu(\pi) = <1,0>$ ，由于其和等于1，所以也是连续型曲线；

（3） $Z$ 序曲线： $\mu1(π)= 0，\mu2(π) =1/2$ ， $\mu(\pi) = <0,\dfrac{1}{2}>$ ，由于其和小于1，所以可以判断其中某些边的曼哈顿距离大于1，所以是非连续型曲线；

（3）peano曲线： $\mu_1(π)=2/9，\mu2(π) = 7/9$ ， $\mu(\pi) = <\dfrac{2}{9},\dfrac{7}{9}>$ ，其和等于1，所以也是连续型曲线。

2.2 和查询、簇有关的若干定义

定义2.5查询 $g$ 邻边集合 $E(g)$ 的定义

类似于空间 $U$ 的邻边集合定义，查询 $g \subeq U$ ，

（1）假设 $v_1,v_2$ 是查询 $g$ 中的两个点，当两者的曼哈顿距离为1时，定义其为一条邻边 $e = (v_1,v_2)$ ；

（2） $g$ 中所有邻边的集合，被称为空间 $g$ 的邻边集合 $E(g)$ ；

（3）如果 $E(g)$ 中的某条邻边 $e=(v_1,v_2)$ ，仅在第 $i$ 维上坐标不同，其他维上坐标均相等，则称 $e$ 为沿维度 $i$ 的邻边；

（4） $E(g)$ 中所有沿维度 $i$ 的邻边构成的集合，定义为第 $i$ 维上的邻边集合 $E_i(g)$ ，由此可见, $E_i(g) = E(g) \cap E_i(U)$ 。

定义2.6查询 $g$ 邻边向量 $v(g)$ 的定义

给定查询 $g$ ，定义其邻边向量为长度等于 $d$ 的向量 $v(g)$ ，其值为：
$v(g)=<v_1(g),v_2(g),...,v_d(g)>, where 1 \le i \le d, v_i(g)=|E_i(g)|$

(1) $E_i(g)$ 为 $g$ 在第 $i$ 个维度上邻边的集合， $|E_i(g)|$ 为其邻边的个数。

（2） $v_i(g)$ 为标量， $v(g)$ 为向量；

（3） $g$ 的邻边向量本质上是对 $g$ 的形状特性描述。

定义2.7 簇的定义：
当某个 $cell$ 集合 $C$ （ $C$ 为 $U$ 的子集），如果其在填充曲线 $π$ 中对应的数值是连续的，则被称之为一个簇。需要说明的是，空间上邻接的 $cell$ 集合，有可能形成多个簇，不同类型的填充曲线，其形成这种簇的特性不同，但基本都无法做到在所有平移或旋转情况下只对应一个簇。

（1）查询 $q$ 是 $U$ 的子集， $q$ 的体积 $|q|$ 是其中 $cell$ 的数量；
（2）矩形查询是在各维度上均为有限连续区间的 $cell$ 集合；
（3）对于非矩形查询，可以定义其外包矩形为 $B(q)$ ，当$q $是矩形查询时，两者等价；
（4）当 $|B(q)|$ 独立于 $n$ 时，我们成 $g$ 是固定值尺寸的。

定义2.8 $q$ 形查询簇值 $c(q,π）$ 的定义

某个 $q$ 形查询，其在填充曲线 $π$ 中的簇数量 $c(q,π）$ ，被定义为 $q$ 形所能切分的最小簇数量。

例如，下图中对于 $3 \times 2$ 的矩形查询：

（1）在希尔伯特曲线中，不同位置的查询，簇数量可能为1，也可能不为1，其簇值就取最小值1；

（2）在Z序曲线中，不同位置的查询，簇数量肯定大于等于2，其簇值就取最小值2。

定义2.9查询集合 $Q$ 的平均簇值 $C(Q,\pi)$ 的定义

如果 $Q$ 为若干查询 $q$ 的集合，则对于非空查询集合 $Q$ ，将其在 $π$ 上的平均簇值 $c(Q，π）$ 定义为：

c(Q,\pi) =\dfrac{\sum\limits_{q \in Q}{c(q,\pi)}}{|Q|}

即若干查询的平均簇值是各查询簇值的平均。

定义2.10查询 $g$ 的旋转、部分旋转集 $\Lambda$ 和全旋转集 $\Lambda^*$ 的定义

（1）旋转 $\lambda$ 指 $g$ 在某两个坐标轴上做了置换，形成90度旋转。

例如：二维空间中，x和y的置换形成一个旋转。

（2） $m$ 个不重复的旋转构成的集合，被称为部分旋转集 $\Lambda=\{\lambda_1,\lambda_2,..,\lambda_m\}$

（3）当 $\Lambda$ 包含了 $d$ 维空间所有可能的坐标轴置换（旋转）时，被称为全旋转集将 $\Lambda^*$ 。

（4）对于任一旋转 $\lambda \in \Lambda^*$ ，定义 $\lambda(i)$ 为 $i$ 在 $\lambda$ 下的镜像 $(1 \le i \le d)$ 。

定义2.11查询 $g$ 的旋转形 $\mathcal{P}$ 、平移形 $\mathcal{T}$ 和全查询集合 $\mathcal{Q}$ 的定义

（1）查询 $g$ 中的某个 $cell$ 经 $\lambda$ 旋转后的值被称为单元旋转值）：

对于任一 $\lambda \in \Lambda^*$ ，某个 $cell x(\,x \in U)$ 在旋转 $\lambda$ 下的值定义为

\mathcal{P}(x,\lambda)=(x_{\lambda(1)},x_{\lambda(2)},...,x_{\lambda(d)})

（2）查询 $g$ 经 $\lambda$ 旋转后，形成的新查询，被称为 $g$ 的旋转形查询 $\mathcal{P}(g,\lambda)$ ：
查询 $g(g\subeq U)$ 在经过 $\lambda$ 旋转后的值，被定义为 $\mathcal{P}(g,\lambda) = \{ \mathcal{P}(v,\lambda)\,|\,v \in g\}$ 。即 $g$ 在旋转后的值，是其内所有 $cell$ 旋转后值的集合。

（3）查询 $g$ 的 $m$ 个旋转形查询构成的集合被称为 $g$ 的部分旋转集合 $\mathcal{P}(g,\Lambda)=\{\mathcal{P}(g,\lambda_1)，\mathcal{P}(g,\lambda_2)，... ,\mathcal{P}(g,\lambda_m) \,|\, \lambda_i \in \Lambda\}$ 。

（4）查询 $g$ 的平移形 $\mathcal{T}(g,\delta)$ 和平移集合 $\mathcal{T}(g) $：

查询 $g(g \subeq U)$ ，在经过向量 $\delta$ ( $\delta =<\delta_1,\delta_2,...\delta_d>)$ 的平移后，产生的新查询被称为其平移形。

$\mathcal{T}(g,\delta)=\{ v+\delta \,|\, v \in g\}$ ，

在空间 $U$ 中所有可能的 $\mathcal{T}(g,\delta)$ 构成的集合，被称为 $g$ 的平移集合 $\mathcal{T}(g)$ 。

（5） $g$ 在旋转 $\lambda_1$ 和旋转 $\lambda_2$ 下的平移集合分别为 $\mathcal{T}(\mathcal{P}(g,\lambda_1))$ 和 $\mathcal{T}(\mathcal{P}(g,\lambda_2))$ ，一般的，当 $\lambda_1 \ne \lambda_2$ 时，两者是有区别的；不过也有可能出现两者相同的特殊情况，如 $g$ 中只有一个单元，而该单元在各维度上的坐标均相同，此时任何两个旋转下的平移集合均相同；立方体形状的查询比较特殊，其所有的旋转均相等。

（6） $\mathcal{T}(\mathcal{P}(g,\Lambda))$ 被称为 $g$ 在旋转 $\Lambda$ 全查询集合集合 $\mathcal{Q}(g)$ 或 $\mathcal{Q}(g,\Lambda^*)$ ， $\mathcal{T}(\mathcal{P}(g,\Lambda^*))$ 被称为 $g$ 的全查询集合集合 $\mathcal{Q}(g)$ 或 $\mathcal{Q}(g,\Lambda^*)$ 。

通过上述定义可知：

（1）作者的目的并非研究单一的查询个体，而是在尺寸固定的情况下，对查询的各种可能性进行遍历，在此基础上形成统计结论。

（2）通过平移集合 $\mathcal{T}(g)$ ，对 $g$ 进行聚簇性统计分析，可以得出其某种固定方向的统计结论；

（3）通过全查询集合 $\mathcal{Q}(g)$ ，对查询 $g$ 进行聚簇性统计分析，可以得出更为一般性的结论。

举例：

$d=2$ ，形状为 $2 \times 3$ 的查询 $g$ ，其旋转集合 $\Lambda^*$ 为{(1,2),(2,1)}，其对应的旋转形为 $\mathcal{P}$ 为 (2,3) 和 (3,2)，其查询集合 $\mathcal{Q}(g,\Lambda^*)$ 为U中所有可能的 $2 \times 3$ 矩形和所有可能的 $3 \times 2$ 矩形，并且全查询集合中的查询数量为： $|\mathcal{Q}(g,\Lambda^*)|=2(\sqrt{n}-1)(\sqrt{n}-2)$ 。

定义2.12查询 $g$ 的旋转形邻边向量、旋转形集合的邻边向量的定义

(1) 旋转形邻边向量

给定查询 $g$ 和旋转集合 $\lambda \in \Lambda^*$ ，其旋转构成后的查询的邻边向量，被称为g的旋转形邻边向量 $v(g,\lambda)$ 。

（2）给定查询 $g$ 和非空旋转集合 $\Lambda \subeq \Lambda^*$ ，定义其旋转形集合 $\mathcal{P}(g,\Lambda)$ 对应的邻边向量 $v(g,\Lambda)$ 为各邻旋转形邻边向量的平均值向量，即：

v(g,\Lambda) =(v_1(g,\Lambda),v_2(g,\Lambda),...,v_d(g,\Lambda))\\where \quad 1 \le i \le d,\\and\quad v_i(g,\Lambda)=\dfrac{\sum_{\lambda\,\in\, \Lambda}v_i(\mathcal{P}(g,\lambda))}{|\Lambda|}\\

定义2.13命中函数 $I(q,\alpha,\beta)$ 的定义

对于 $U$ 中两个单元 $\alpha,\beta$ , 以及查询 $q\,(q \subeq U)$ , 当 $\alpha,\beta$ 都被 $q$ 包含时，称为被 $q$ 命中：

I(q,\alpha,\beta) = \left \{ \begin{align*} &1\qquad if \quad \alpha \in q\quad and\quad \beta \in q\\ &0\qquad otherwise \end{align*} \right .

命中函数主要用于辅助区分查询g内两个单元的邻接关系。

（1）空间填充曲线可以被视为一系列从一个单元（cell）走向另一个单元（cell）的有向边构成的集合，其中每个cell仅被访问一次。

（2）边可以由U中两个单元 $(\alpha，\beta)$ 定义，其中 $\left |\begin{align*} &\alpha = \pi^{-1}(i),\\&\beta=\pi^{-1}(i+1)\\\end{align*}\right.$ ， $,0\le i \le n-2 $ 。

（3）填充曲线 $\pi$ 中所有边的集合， $N(\pi) = \{ (\alpha_i,\beta_i)\} where \,\left |\begin{align*} &\alpha_i = \pi^{-1}(i),\\&\beta_i=\pi^{-1}(i+1)\\\end{align*}\right. ，and \quad0\le i \le n-2$

（4） $N(\pi)$ 中在第 $i$ 个维度上相邻的边的集合，表示为 $N^i(\pi)$ （见定义1.4）。根据定义可知，不同类型的填充曲线，其 $N^i(\pi)\sub N(\pi)$ ，但 $\sum\limits_{i=1}^dN^i(\pi)$ 不一定等于 $\N(\pi)$ 。

（5） $I$ 指示了查询 $q$ 中两个单元，是否为填充曲线上的相邻点，为量化q的簇值提供了一种计量手段。

（6）根据定义，假设查询 $q$ 共有 $|q|$ 个单元，初始状态下簇值为 $|q|$ ，即每个单元都独立成簇，后面的工作就是从这些独立的簇中，根据 $I$ 进行簇的合并。具体方法是按照填充曲线的方向对 $N(\pi)$ 中的边进行顺序遍历（也可求出 $q$ 的 $\pi_{min},\pi_{max}$ 后,在其区间内进行遍历）时，如果边 $N(\alpha,\beta)$ 中的两个顶点 $\alpha和 \beta$ 都被查询 $q$ 包含，则两点在一个簇中，簇值 $|q| -1$ ，遍历结束后， $|q|$ 的剩余值即为簇值（见引理2.3）。

三、重要的引理和计算公式

引理3.1 查询集合大小 $|\mathcal{Q}(r,\Lambda)|$ 的计算公式

若 $r$ 为 $d$ 维矩形， $r_i$ 表示 $r$ 在维度 $i$ 上的长度，令 $\Lambda \subeq \Lambda^*$ ， $n$ 为填充曲线的总长度，则有：

|\mathcal{Q}(r,\Lambda)| = |\Lambda|\prod_{i=1}^{d}(\sqrt[d]{n}-r_i+1)

引理3.2更一般的，对于非矩形查询g，可根据其外包矩形计算全查询集合大小 $|\mathcal{Q}(r,\Lambda)|$

若 $g$ 为非矩形查询， $b_i$ 表示 $g$ 的外包矩形 $B(g)$ 在维度 $i$ 上的长度，令 $\Lambda \sube \Lambda^*$ ，则有：

|\mathcal{Q}(g,\Lambda)| = |\Lambda|\prod_{i=1}^{d}(\sqrt[d]{n}-b_i+1)

（1）全查询集合的大小和填充曲线的形式无关，只和填充曲线的长度有关；

（2）这种无关性有助于对不同类型的填充曲线进行对比分析；

（3）非矩形查询利用外包矩形的全查询集合来代替；

（4）总体上，全查询集合的大小和所要分析的旋转个数、填充曲线的长度成正相关。

引理3.3查询 $q$ 簇值的计算公式

对于任意查询 $q$ 和任意填充曲线 $\pi$ ，

c(q,\pi)=|q| -\sum\limits_{(\alpha,\beta) \in N(\pi)}I(q,\alpha,\beta)

即对于指定的查询 $q$ ：

（1）其簇值不大于 $q$ 中单元的数量 $|q|$ ；

（2） $q$ 中任意两个单元 $\alpha,\beta$ ，如果 $\alpha$ 到 $\beta$ 正好构成 $\pi$ 中的一条边，则簇值在 $|q|$ 基础上减1 。

例如：

对于下图所示的2维 $4 \times 4$ 网格空间，每个单元按照填充曲线被顺序赋予一个数值，当查询 $q$ 为阴影所示的区域时(此处 $|q|=3$ )，只有一个 $I(q,\alpha,\beta)$ 为非0，即1号单元到2号单元，其他 $（\alpha,\beta）$ 的组合均为0。因此根据上述计算公式，此处 $c(q,\pi)=|q|-1= 2$ 。

引理3.4 查询集合平均簇值的计算公式

c(Q,\pi) = |q|-\dfrac{\sum_{i=0}^{n-2}|P_Q(\pi^{-1}(i),\pi^{-1}(i+1))|}{|Q|}

类似于引理3.3，只是对于空间填充曲线中的每一条边，对查询集合 $Q$ 中的所有查询做包含分析，并相应的削减簇值，曲线遍历完成后，做簇值的平均。

（1）对于空间填充曲线上的某条边对应的两个单元 $\alpha,\beta \in U$ ，定义 $P_Q(\alpha,\beta)=\{r \in Q|I(r,\alpha,\beta)=1\}$ 用于表示其在所有查询中的被命中集合，自然的， $|P_Q(\alpha,\beta)|$ 为命中次数，被命中一次，簇值减去1。

引理3.5查询 $q$ 表面积的计算公式

查询g的表面积定义为其壳中单元的数量，表面积 $ S_g=2d|g|-2|E(g)|$ ，即表面积是查询g的体积和在各维度上边数量总和的函数。

四、定理及相关推论

4.1 关于连续型空间填充曲线的结论

定理4.1任意连续型填充曲线、任意固定尺寸的查询 $g$ ，仅考虑平移时的平均簇值

对于任意连续型填充曲线 $\pi$ ,任意固定尺寸的查询 $g$ ，其平移集合 $\mathcal{T}(g)$ 的平均簇值可以有如下公式计算：

\lim\limits_{n\rightarrow \infty}c(\mathcal{T}(g),\pi)=|g| - \mu(\pi) \cdot v(g)\\ where \,“\cdot”\,指向量的点乘

（1）根据定义2.4和2.6， $\mu(\pi)$ 为填充曲线 $\pi$ 各维度的边占比向量， $v(g)$ 为查询 $g$ 各维度的边数量向量；

（2）该定理表明，在仅考虑平移的情况下，任意固定尺寸的查询，其平均簇值仅和查询g的体积（单元数量）、g的形状(用各维度上边的数量量化)和填充曲线的形式（用曲线各维度上边的比率量化）有关；

（3）当n趋近于无穷大时，任意固定尺寸查询的平均簇值趋近于固定的值；

（4）证明过程见参考文献。

定理4.2 任意连续型填充曲线、任意固定尺寸的查询 $g$ ，同时考虑平移和部分旋转时的平均簇值

对于任意连续型填充曲线 $\pi$ ,任意固定尺寸的查询 $g$ ，和旋转集合 $\Lambda \sube \Lambda^*$ ，其平均簇值可以有如下公式计算：

\lim\limits_{n\rightarrow \infty}c(\mathcal{Q}(g,\Lambda),\pi)=|g| - \mu(\pi) \cdot v(g,\Lambda)\\where \,“\cdot”\,指向量的点乘

(1)根据定义2.4和2.12， $\mu(\pi)$ 为填充曲线 $\pi$ 各维度的边占比向量， $v(g,\Lambda)$ 为查询 $g$ 在旋转集 $\Lambda$ 下，各维度的边数量平均值的向量；

（2）该定理表明，在同时考虑旋转和平移的情况下，任意固定的查询，其平均簇值仅和查询g的体积（单元数量）、g的形状(用各维度上各种旋转形成的边数量的平均值来量化)和填充曲线的形式（用曲线各维度上边的比率量化）有关；

（3）当n趋近于无穷大时，任意固定尺寸查询的平均簇值趋近于固定的值。

算法4.3查询和旋转集合确定情况下，构造连续型空间曲线的算法

定理4.4 任意连续型曲线、任意固定尺寸的查询，同时考虑平移和所有可能的旋转时的平均簇值

对于任意连续型填充曲线 $\pi$ ,任意固定尺寸的查询 $g$ ，和全旋转集合 $\Lambda^*$ ，其平均簇值可以有如下公式计算

\lim\limits_{n\rightarrow\infty}c(\mathcal(Q)(g,\Lambda^*),\pi)=\dfrac{S_g}{2d}

（1） $S_g$ 为查询g的表面积， $ S_g=2d|g|-2|E(g)|$ ，表面积定义为g的壳中单元的数量；

（2）此处忽略了与边界邻接的情况；

（3）该定理表明，如果查询特点是全部旋转都会出现且处于均匀分布时，则所有连续型曲线的平均簇值都相同，没有优略之分，且仅与查询的表面积有关（实际应用中，d一般为常数）。

4.2 任意填充曲线的矩形查询平均簇值的下限分析

对于矩形查询 $r$ 和旋转集 $\Lambda$ 的全查询集合 $\mathcal{Q}(r,\Lambda)$ ，令 $v^{max}=v^{max}(r,\Lambda)=max_{1\le i\le d}v_i(r,\Lambda)$ ，则有如下定理：

定理4.5矩形查询平均簇值的计算公式

对于固定尺寸的矩形查询 $r$ 和非空旋转集合 $\Lambda \sube \Lambda^*$ ,对于任意填充曲线 $\pi$ (连续的或非连续的)，如果其全查询集合 $\mathcal{Q}(r,\Lambda)$ 的平均簇值存在下限，则：

\lim\limits_{n\leftarrow\infty} c(\mathcal{Q}(r,\Lambda),\pi) \ge |r| -v^{max}

定理4.6 任意固定尺寸的矩形查询，总能构造出一条连续型填充曲线，使其平均簇值达对最优解。

对固定尺寸的矩形查询 $r$ 和非空旋转集合 $\Lambda \sube \Lambda^*$ ,总是存在一条连续型填充曲线 $\pi$ ，其平均簇值能达到最优解。即：

\lim\limits_{n\leftarrow\infty} c(\mathcal{Q}(r,\Lambda),\pi) = |r| -v^{max}

推论4.7对于任意固定尺寸的矩形查询，如果考虑其所有可能的旋转时，任意一条连续型填充曲线的平均簇值都是最优的。

4.3 Z序曲线的空间聚簇性分析

定义4.8：空间U的重新定义

空间 $U$ 由维度 $d$ 和各维度的尺寸 $2^k$ 定义，特别的，此处各维度尺寸相等。假设该空间与Z序之间为双射关系，则有各维度尺寸 $2^k\,=\,^{d}\sqrt{n},\,n为空间填充曲线长度$ ，例如：以二维平面U可被d=2,k=10的参数唯一确定，其各维度尺寸均为 $1024=2^{10}$ ，且 $n = 1024^2$ 。

定义4.9：Z值得定义

$U$ 上的某个点 $x=（x_1,x_2,\ldots x_d）where\, 0\le x_i \le 2^k,and \,0<i<d$ （其中， $x_i$ 可以用 $k$ 位二进制数字表示）， $x_i^j$ 为其在第i维上的第j个二进制数字， $j=1,2,\ldots k$ ，则该点的Z值被定义为：

Z(x) = x_1^1,x_2^1,\ldots,x_d^1,x_1^2,x_2^2,\ldots x_d^2 \ldots x_1^k,x_2^k,\ldots x_d^k

例如：当 $d=3,k=4$ 时， $U$ 中某点 $（0011,1011,1010）$ 的Z值为： $Z(0011,1011,1010) = 011,000,111,110$

下图为d=2，k=3时的Z序示意图。

定义4.10：查询 $q$ 及其平移集合 $\mathcal{T}(q)$ 的定义

此处将查询 $q$ 确定为立方体形式，即 $Size\,of\,q=m\times m\times ...\times m$ ，其平移集合 $\mathcal{T}(q)$ 被定义为 $q$ 在 $U$ 中所有可能的平移产生的集合。

定理4.11：Z序曲线中立方体查询的平均簇值计算表达式

如果 $Z$ 为 $d$ 维空间的 $Z$ 序曲线， $q$ 是大小为 $m^d$ 的立方体查询，则有关于 $q$ 的平均簇值为：

\lim\limits_{n->\infty}{c(T(q),Z)} =(2+o(\dfrac{1}{2^d}))m^{d-1}+o(m^{d-1})

该平均簇值的下限为 $m^{d-1}$ ，(即， $q$ 形在 $U$ 中的平移，平均会产生不少于 $m^{d-1}$ 个簇)。因此，可以断定，Z序曲线的性能是其下限的2倍。

引理4.12：定义 $N(Z)$ 为 $Z$ 中所有边的集合，如果我们将其分解为 $kd$ 个不连接的部分，组 $G_h(0 \le h \le {kd-1})$ ，

4.4、近连续型空间曲线的聚簇性分析

五、总结

个人觉得作者的最大贡献在于：

（1）**提出了一种量化分析空间填充曲线性能的通用方法。**作者提出了一种“以边为中心”的量化分析方法，上述所有结论，都是通过对查询 $g$ 以及填充曲线 $\pi$ 的边特性量化而得出。

（2）对于矩形查询，给出了平均簇值可能的最优解计算式。同时指出，如果应用中矩形查询的各种旋转形均存在且分布比较均匀，则选择任何一条连续型填充曲线都能够使平均簇值为最优值。

（3）对于矩形查询，如果仅考虑部分旋转集，则可以构造出一条能够达到最优解的填充曲线，并给出了构造填充曲线的算法，这为某些特定形式的查询优化提供了理论支撑。

（4）在更广泛的查询条件下，为连续型曲线的各种平均簇值计算提供了基本算式，该算式由查询 $g$ 和填充曲线 $\pi$ 的体积和形状特性决定。

（5）针对Z序曲线的立方体查询这一具体问题做了分析，给出了该情况下Z序曲线平均簇值的分析表达式。

六、其他相关文献

6.1 本文文献索引

（1）Xu P, Tirthapura S. Optimality of clustering properties of space-filling curves[J]. ACM Transactions on Database Systems (TODS), 2014, 39(2): 1-27.

（2）Pan Xu and Srikanta Tirthapura. 2014. Optimality of Clustering Properties of Space-Filling Curves. ACM Trans. Database Syst. 39, 2, Article 10 (May 2014), 27 pages. DOI:https://doi.org/10.1145/2556686

6.2 一篇用试验数据证明Z序编码、Grey编码、Hilbert编码聚簇性能的文献

（3）Kumar A. (1994) A study of spatial clustering techniques. In: Karagiannis D. (eds) Database and Expert Systems Applications. DEXA 1994. Lecture Notes in Computer Science, vol 856. Springer, Berlin, Heidelberg. DOI：https://doi.org/10.1007/3-540-58435-8_171