时空数据库系列（三）技术讲解：时空轨迹数据压缩、空间索引R-tree
系列文章链接
时空数据库系列（一）什么是时空数据？特征和适用场景有哪些？
时空数据库系列（二）时空数据库介绍 了解数据模型与应用场景
时空数据库系列（四）如何高效存储、分析时空数据？时空数据库Spacture给了我们答案
时空数据库系列（五）星环时空数据库Spacture案例与Demo演示
时空轨迹压缩
时空轨迹为移动对象在地理空间移动时，以固定或非固定的时间间隔采样得到的时空点序列。为了保留移动对象详尽的移动状态信息，采样间隔必须尽可能小。较小的采样间隔导致传感器记录大量的时空轨迹数据点，因此在数据库中存储时间轨迹时，为了节省存储成本，需要对时空轨迹数据进行压缩。
首先，对轨迹进行压缩，在保证精度的情况下，以较少的数据点满足对轨迹的记录。轨迹压缩算法分为无损压缩和有损压缩，其中无损压缩主要为哈夫曼压缩。有损压缩分为离线处理和在线数据压缩。离线压缩指收集完整的轨迹数据后，先压缩再传输至服务器。常用的算法有道格拉斯-普客Douglas-Peucker（DP）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法。在线压缩指根据要求的精度选择性的在线更新。常用的方法有滑动窗口、开放窗口、基于安全区域的方法等。
离线压缩——DP算法
在估计轨迹中根据垂直欧式距离保留方向趋势，将原始轨迹替换为近似直线段。如果替换不满足指定的误差要求，则通过选择误差最大的位置点作为分割点，递归地将原问题划分为两个子问题，直到近似轨迹与原始轨迹之间的误差低于指定的误差阈值。
DP算法的步骤如下：
（1）在轨迹曲线在曲线首尾两点P0，P16之间连接一条直线，该直线为曲线的弦；
（2）遍历曲线上其他所有点，求每个点到直线P0-P16的距离，找到最大距离的点P9，最大距离记为dmax；
（3）比较该距离dmax与预先定义的阈值Dmax大小，如果dmax<Dmax，则将该直线P0-P16作为曲线段的近似，曲线段处理完毕；
（4）若dmax>=Dmax，则使P0点将曲线P0-P16分为P0-P9和P9-P16两段，并分别对这两段进行（1）～（3）步处理；
（5）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即为原始曲线的路径，即P0-P3、P3-P9，P9-P16。
在线压缩——滑动窗口
用一条有效的线段拟合一个增长的滑动窗口中的位置点，并继续增长滑动窗口，直到近似误差超过某个误差界。
首先将轨迹的第一个点初始化为锚点 p0 ，然后开始增大滑动窗口，当一个新的点 加入滑动窗口中时，用线段
来拟合滑动窗口内所有的原始轨迹点。只要窗口内的轨迹相对于线段
的距离误差小于用户指定的误差阈值，滑动窗口就会继续增大。否则，将线段
作为近似轨迹的一部分，并将
设置为新的锚点。该算法将一直持续到访问完原始轨迹中的所有位置点。
举个例子：当滑动窗口从 p0 增长到 p0,p1,p2,p3 时，拟合线段与原始轨迹之间的误差均不大于指定的误差阈值。当包含 p4 时，p2 的误差超过阈值，因此 p0p3 被包含在近似轨迹中，然后 p3 被设置为新的锚点（也就是说加入p4之后，超出阈值，则用p4之前的那个点p3作为锚点）。下图绿线即为最终生成的轨迹。
轨迹数据压缩
在时空数据库中，面对海量时空数据的存储需求，除了对轨迹的压缩之外，还需要对轨迹中的点进行压缩。时空轨迹中的点除了包含时间属性t（数据类型一般为long（Unix time）），与空间属性x,y,z（数据类型为float）之外，还有可能包含其他状态属性（数据类型可能为int、float或者string）。例如AIS船舶轨迹，在每个轨迹点上，除了时空坐标外，还有航速航向等属性。若对轨迹数据进行压缩，就意味着同时对时间属性、空间属性和其他属性三种类型数据的压缩。
GORILLA时间序列存储
现在主流的时间序列压缩存储方案为Facebook公司提出的gorilla方法。该方法使用delta-of-delta（DOD）算法进行时间属性压缩，使用XOR算法进行float类型属性的压缩。
GORILLA压缩数据结构如下，t-1为时间头，用以表示该条轨迹的起始时间，同时用来作为时间属性DOD压缩的起始时间。t-1后为时间属性t与空间点值v的压缩存储。
GORILLA算法对时间的压缩
t为int类型使用DOD压缩。DOD压缩算法是delta算法的改进。假设我们要对第i个时间属性进行压缩，则使用DOD压缩的算法如下（压缩第i个数据项）
步骤1：计算差值Di,
IF i==0，THEN Di=t0-t-1, ELSE Di = (ti-ti-1) - (ti-1-ti-2);
步骤2：
IF Di==0, THEN 压缩值= '0'(1bit位)
ELSE IF Di in [-63,64]，THEN 压缩值= '10'(2bit位) + Di(7bit位)
ELSE IF Di in [-255,256], THEN 压缩值= '110'(3bit位) + Di(9bit位)
ELSE IFDi in [-2047,2048]，then 压缩值= '1110' +Di(12bit位)
ELSE 压缩值= '1111' + Di(32bit位)
GORILLA算法对值的压缩
v为double（float）类型使用XOR算法压缩，假设我们要对第i个时间点上的v值进行压缩，算法如下（压缩第i个数据项）
步骤1：
IF i==0, THEN 压缩值=v0, RETURN
ELSE xor = XOR(vn,vn-1) 其中XOR函数是对两个输入值进行异或计算
步骤2：
将xor值转换为十六进制串，该串可以分为三段，前置零段，后置零段及中间有效段。
IF i==1，THEN 压缩值= '11'(2bit位) + 前置零段长度(5bit位) + 有效段长度(6bits) + 有效段
ELSE，
IF vi的有效段在vi-1的有效段范围之内（三段长度信息和vi-1相同），THEN 压缩值= '10' + 有效段
ELSE 压缩值= '11'(2bit位) + 前置零段长度(5bit位) + 有效段长度(6bits) + 有效段
关于十六进制的xor值的三段示意图如下：
数据值 |
16进制 |
vi-1 |
0x402c200000000000 |
vi |
0x400a000000000000 |
vi ^ vi-1 |
0x0026200000000000 |
示意图中最后一行为xor值，其中，'262'为有效段，'262'前面高位的两个0为前置零段，'262'后面低位的0位后置零段。
字符串属性压缩
字符串压缩主要使用LZ系列基于字典的压缩。下图为LZ算法示意图，在此就不过多赘述，感兴趣的伙伴可以在评论区留言讨论。
空间索引R-tree
R-tree是一种用于高效存储空间数据索引的树状数据结构，有助于空间数据查询和存储。其概念起源于Toni Guttman在1984年ACM SIGMOD数据管理国际会议的《R-Trees: A Dynamic Index Structure for Spatial Searching》。R-tree的核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外包矩形，这个最小外接矩形就成为上一层的一个节点。
R-Tree是为范围查询而设计的特殊索引，常用于地理空间系统，其中的“R”代表Rectangle（矩形），即每个条目是具有最小和最大X和Y坐标的矩形。因为所有节点都在它们的最小外包矩形中，所以跟某个矩形不相交的查询就一定跟这个矩形中的所有节点都不相交。叶子节点上的每个矩形都代表一个对象，节点都是对象的聚合，并且越往上层聚合的对象就越多。也可以把每一层看做是对数据集的近似，叶子节点层是最细粒度的近似，与数据集相似度100%，越往上层越粗糙。
在现实生活中，R-tree可以用来存储地图上的空间信息，例如餐馆地址，或者地图上用来构造街道，建筑，湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。
R-Tree的数据结构
对于一棵 R 树，叶子节点所在层次称为 Level1，根节点所在层次称为 Level-h。一棵 R树满足如下性质：
(1) 除根结点之外，所有非根结点包含有 m至 M 个记录索引（条目）。根结点的记录个数可以少于 m。通常m=M/2。
(2) 每一个非叶子结点的分支数和该节点内的条目数相同，一个条目对应一个分支。所有叶子结点都位于同一层，因此 R 树为平衡树。
(3) 叶子结点的每一个条目表示一个几何对象，图示中以点对象为例（Tips：R-Tree不仅可以存储点数据，也可以存储线、多边形等几何数据）。
(4) 非叶结点的每一个条目存放的数据结构为：(I,child−pointer)。child−pointer 是指向该条目对应孩子结点的指针。I 表示一个 n 维空间中的最小外包矩形MBR，I 覆盖了该条目对应子树中所有的矩形或几何对象。
两个点保存在一个叶子节点的两个条目中，恰好框住这两个条目的矩形表示为：I=(I0,I1)。其中 I0=(a,b),I1=(c,d)，也就是说最小外包矩形是用各个维度的边来表示，在三维空间中那就是立方体，用 3 条边（长宽高）就可以表示了。
下面构建一棵 R树。如下图，理论上，点可以任意组合成叶节点，只要 MBR 包含它子树中的所有点。特别是 MBR可以重叠。
下图是另一种组合建立的 R树。
一般分组的原则就是最小化每个MBR 矩形，这样查询的时候发生的相交情况会越少，查询的分支就越少，查询效率越高。
系列文章链接
时空数据库系列（一）什么是时空数据？特征和适用场景有哪些？
时空数据库系列（二）时空数据库介绍 了解数据模型与应用场景
时空数据库系列（四）如何高效存储、分析时空数据？时空数据库Spacture给了我们答案
时空数据库系列（五）星环时空数据库Spacture案例与Demo演示
时空轨迹压缩
时空轨迹为移动对象在地理空间移动时，以固定或非固定的时间间隔采样得到的时空点序列。为了保留移动对象详尽的移动状态信息，采样间隔必须尽可能小。较小的采样间隔导致传感器记录大量的时空轨迹数据点，因此在数据库中存储时间轨迹时，为了节省存储成本，需要对时空轨迹数据进行压缩。
首先，对轨迹进行压缩，在保证精度的情况下，以较少的数据点满足对轨迹的记录。轨迹压缩算法分为无损压缩和有损压缩，其中无损压缩主要为哈夫曼压缩。有损压缩分为离线处理和在线数据压缩。离线压缩指收集完整的轨迹数据后，先压缩再传输至服务器。常用的算法有道格拉斯-普客Douglas-Peucker（DP）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法。在线压缩指根据要求的精度选择性的在线更新。常用的方法有滑动窗口、开放窗口、基于安全区域的方法等。
离线压缩——DP算法
在估计轨迹中根据垂直欧式距离保留方向趋势，将原始轨迹替换为近似直线段。如果替换不满足指定的误差要求，则通过选择误差最大的位置点作为分割点，递归地将原问题划分为两个子问题，直到近似轨迹与原始轨迹之间的误差低于指定的误差阈值。
DP算法的步骤如下：
（1）在轨迹曲线在曲线首尾两点P0，P16之间连接一条直线，该直线为曲线的弦；
（2）遍历曲线上其他所有点，求每个点到直线P0-P16的距离，找到最大距离的点P9，最大距离记为dmax；
（3）比较该距离dmax与预先定义的阈值Dmax大小，如果dmax<Dmax，则将该直线P0-P16作为曲线段的近似，曲线段处理完毕；
（4）若dmax>=Dmax，则使P0点将曲线P0-P16分为P0-P9和P9-P16两段，并分别对这两段进行（1）～（3）步处理；
（5）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即为原始曲线的路径，即P0-P3、P3-P9，P9-P16。
在线压缩——滑动窗口
用一条有效的线段拟合一个增长的滑动窗口中的位置点，并继续增长滑动窗口，直到近似误差超过某个误差界。
首先将轨迹的第一个点初始化为锚点 p0 ，然后开始增大滑动窗口，当一个新的点 加入滑动窗口中时，用线段
来拟合滑动窗口内所有的原始轨迹点。只要窗口内的轨迹相对于线段
的距离误差小于用户指定的误差阈值，滑动窗口就会继续增大。否则，将线段
作为近似轨迹的一部分，并将
设置为新的锚点。该算法将一直持续到访问完原始轨迹中的所有位置点。
举个例子：当滑动窗口从 p0 增长到 p0,p1,p2,p3 时，拟合线段与原始轨迹之间的误差均不大于指定的误差阈值。当包含 p4 时，p2 的误差超过阈值，因此 p0p3 被包含在近似轨迹中，然后 p3 被设置为新的锚点（也就是说加入p4之后，超出阈值，则用p4之前的那个点p3作为锚点）。下图绿线即为最终生成的轨迹。
轨迹数据压缩
在时空数据库中，面对海量时空数据的存储需求，除了对轨迹的压缩之外，还需要对轨迹中的点进行压缩。时空轨迹中的点除了包含时间属性t（数据类型一般为long（Unix time）），与空间属性x,y,z（数据类型为float）之外，还有可能包含其他状态属性（数据类型可能为int、float或者string）。例如AIS船舶轨迹，在每个轨迹点上，除了时空坐标外，还有航速航向等属性。若对轨迹数据进行压缩，就意味着同时对时间属性、空间属性和其他属性三种类型数据的压缩。
GORILLA时间序列存储
现在主流的时间序列压缩存储方案为Facebook公司提出的gorilla方法。该方法使用delta-of-delta（DOD）算法进行时间属性压缩，使用XOR算法进行float类型属性的压缩。
GORILLA压缩数据结构如下，t-1为时间头，用以表示该条轨迹的起始时间，同时用来作为时间属性DOD压缩的起始时间。t-1后为时间属性t与空间点值v的压缩存储。
GORILLA算法对时间的压缩
t为int类型使用DOD压缩。DOD压缩算法是delta算法的改进。假设我们要对第i个时间属性进行压缩，则使用DOD压缩的算法如下（压缩第i个数据项）
步骤1：计算差值Di,
IF i==0，THEN Di=t0-t-1, ELSE Di = (ti-ti-1) - (ti-1-ti-2);
步骤2：
IF Di==0, THEN 压缩值= '0'(1bit位)
ELSE IF Di in [-63,64]，THEN 压缩值= '10'(2bit位) + Di(7bit位)
ELSE IF Di in [-255,256], THEN 压缩值= '110'(3bit位) + Di(9bit位)
ELSE IFDi in [-2047,2048]，then 压缩值= '1110' +Di(12bit位)
ELSE 压缩值= '1111' + Di(32bit位)
GORILLA算法对值的压缩
v为double（float）类型使用XOR算法压缩，假设我们要对第i个时间点上的v值进行压缩，算法如下（压缩第i个数据项）
步骤1：
IF i==0, THEN 压缩值=v0, RETURN
ELSE xor = XOR(vn,vn-1) 其中XOR函数是对两个输入值进行异或计算
步骤2：
将xor值转换为十六进制串，该串可以分为三段，前置零段，后置零段及中间有效段。
IF i==1，THEN 压缩值= '11'(2bit位) + 前置零段长度(5bit位) + 有效段长度(6bits) + 有效段
ELSE，
IF vi的有效段在vi-1的有效段范围之内（三段长度信息和vi-1相同），THEN 压缩值= '10' + 有效段
ELSE 压缩值= '11'(2bit位) + 前置零段长度(5bit位) + 有效段长度(6bits) + 有效段
关于十六进制的xor值的三段示意图如下：
数据值 |
16进制 |
vi-1 |
0x402c200000000000 |
vi |
0x400a000000000000 |
vi ^ vi-1 |
0x0026200000000000 |
示意图中最后一行为xor值，其中，'262'为有效段，'262'前面高位的两个0为前置零段，'262'后面低位的0位后置零段。
字符串属性压缩
字符串压缩主要使用LZ系列基于字典的压缩。下图为LZ算法示意图，在此就不过多赘述，感兴趣的伙伴可以在评论区留言讨论。
空间索引R-tree
R-tree是一种用于高效存储空间数据索引的树状数据结构，有助于空间数据查询和存储。其概念起源于Toni Guttman在1984年ACM SIGMOD数据管理国际会议的《R-Trees: A Dynamic Index Structure for Spatial Searching》。R-tree的核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外包矩形，这个最小外接矩形就成为上一层的一个节点。
R-Tree是为范围查询而设计的特殊索引，常用于地理空间系统，其中的“R”代表Rectangle（矩形），即每个条目是具有最小和最大X和Y坐标的矩形。因为所有节点都在它们的最小外包矩形中，所以跟某个矩形不相交的查询就一定跟这个矩形中的所有节点都不相交。叶子节点上的每个矩形都代表一个对象，节点都是对象的聚合，并且越往上层聚合的对象就越多。也可以把每一层看做是对数据集的近似，叶子节点层是最细粒度的近似，与数据集相似度100%，越往上层越粗糙。
在现实生活中，R-tree可以用来存储地图上的空间信息，例如餐馆地址，或者地图上用来构造街道，建筑，湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”，“检索距离我2千米以内的所有路段”（然后显示在导航系统中）或者“查找（直线距离）最近的加油站”这类问题。
R-Tree的数据结构
对于一棵 R 树，叶子节点所在层次称为 Level1，根节点所在层次称为 Level-h。一棵 R树满足如下性质：
(1) 除根结点之外，所有非根结点包含有 m至 M 个记录索引（条目）。根结点的记录个数可以少于 m。通常m=M/2。
(2) 每一个非叶子结点的分支数和该节点内的条目数相同，一个条目对应一个分支。所有叶子结点都位于同一层，因此 R 树为平衡树。
(3) 叶子结点的每一个条目表示一个几何对象，图示中以点对象为例（Tips：R-Tree不仅可以存储点数据，也可以存储线、多边形等几何数据）。
(4) 非叶结点的每一个条目存放的数据结构为：(I,child−pointer)。child−pointer 是指向该条目对应孩子结点的指针。I 表示一个 n 维空间中的最小外包矩形MBR，I 覆盖了该条目对应子树中所有的矩形或几何对象。
两个点保存在一个叶子节点的两个条目中，恰好框住这两个条目的矩形表示为：I=(I0,I1)。其中 I0=(a,b),I1=(c,d)，也就是说最小外包矩形是用各个维度的边来表示，在三维空间中那就是立方体，用 3 条边（长宽高）就可以表示了。
下面构建一棵 R树。如下图，理论上，点可以任意组合成叶节点，只要 MBR 包含它子树中的所有点。特别是 MBR可以重叠。
下图是另一种组合建立的 R树。
一般分组的原则就是最小化每个MBR 矩形，这样查询的时候发生的相交情况会越少，查询的分支就越少，查询效率越高。
登录后可评论
.jpg)
