下载掌阅APP，畅读海量书库
立即打开
城市每秒钟都会接收来自不同领域的大量异构数据，有效地管理这些数据集对于支持城市的实时监控和数据分析的实施至关重要。为了设计一个有效的城市大数据数据管理系统，我们需要关注四个方面：数据结构、查询、索引和检索算法。
城市中生成的绝大多数数据都与独特的时空属性相关，即空间坐标和随时间动态变化的读数。如图4.1所示，城市大数据在结构和时空动态方面有六种形式。根据数据结构，我们可以将城市数据分为两组，包括基于点和基于网络的数据，分别由图4.1中的两行表示。基于其时空动态，我们可以将数据分为三类，包括时空静态数据、空间静态时间动态数据，以及时空动态数据，分别由三列表示。例如，一个POI与一个静态点位置相关，其属性不（如大小和名称）随时间改变，因此它属于时空静态数据（详细内容请参考1.5.1节）。我们需要定义合适的数据结构来容纳不同类型的数据。之后，我们可以为不同的数据结构设计不同的存储机制、索引和检索算法。
对时空数据的典型查询可以分为两类：范围查询和最近邻查询 [26] 。如图4.2a所示，第一类查询搜索部分或全部位于特定范围内的对象，这个范围可以是地理区域或时空范围。例如，查找位于某地理区域内的建筑物是空间范围查询，搜索过去两分钟内经过广场的空出租车是时空范围查询。在第二类查询中，给定一个对象或点，我们搜索满足给定条件的 k 最近邻（KNN）对象。这类查询通常涉及距离度量，例如查询驾驶员周围最近的加油站。在这里，驾驶员的位置是查询点，而加油站是要搜索的对象，这里的距离应该是网络距离。对时空数据的这两类查询与搜索文档中的关键词，或调用唯一索引和检索算法非常不同。
图4.1 城市大数据的六种数据形式
图4.2 空间和时空数据查询
为了加速数据的访问和检索过程，我们需要设计索引结构来提前充分组织数据。典型的空间索引可以分为两组：基于空间分区的索引和数据驱动的索引。
第一类索引，如基于网格的索引和四叉树索引 [29] ，如图4.3a和图4.3b所示，根据某些规则将空间分割成网格（大小相等或不均匀），而不考虑数据的分布。然后构建网格与落入该网格的数据之间的关系。这样的网格极大地减小了检索算法的搜索空间，因为落入不能满足查询条件的网格的数据可以忽略。
图4.3 一些常用的空间索引
图4.3（续）
第二类索引（例如k-d树 [1] 和R树 [16] ）是基于数据分布构建的索引。k-d树通过使用数据集中的少数几个点来分割数据集。R树则根据数据构造许多矩形，并将这些小矩形进一步组织成大矩形。我们将在4.2.1节中进一步说明这一点。
空间索引可以通过以下三种方法扩展为时空索引。
第一种方法如图4.4a所示，我们可以将时间视为第三个维度，直接将空间索引应用于时空数据。例如，3D R树 [39] 是R树的扩展，它根据时空点构造三维立方体（而不是矩形）。
第二种方法如图4.4b所示，例如多版本R树（MVR树） [37] 、历史R树（HR树） [26] 和HR+树 [36] ，是为每个时间槽构建一个空间索引。为了提高这种索引的效率，可以在不同时间戳之间重用索引的不变子结构。
第三种方法首先使用空间索引（如四叉树或R树）将空间分割成区域，然后为落入每个空间区域的数据构建一个时间索引，如图4.4c所示。可扩展且高效的轨迹索引（SETI） [6] 、起始-结束时间B树（SEB） [32] 和压缩起始-结束树（CSE树） [40] 都属于这一类别。
图4.4 时空索引方法
给定一个查询和一个索引，检索算法搜索满足查询条件的对象。为了提高检索效率，这类算法通常会根据空间或时空索引显著地修剪搜索空间。例如，当进行基于网格索引的空间范围查询时，如图4.3a所示，我们只能检索部分或完全位于查询矩形内的网格以便进一步细化，其他网格被过滤掉。有时，检索算法会得出一些上界或下界来修剪搜索空间。例如，给定一个查询点和R树索引，我们可以快速估计到一组落在矩形内的点的最短欧几里得距离 d s 和最长距离 d l 。如果一个其他对象的距离小于 d s ，那么这个矩形内的所有点都不可能是查询点的最近邻点。也就是说，可以在不计算查询点与它们之间距离的情况下修剪它们。我们将在4.3节中进一步解释这部分内容。