大规模时空数据集与图数据库的可达性和距离查询处理

# 大规模时空数据集与图数据库的可达性和距离查询处理 ## 1. 时空数据集可达性查询处理 ### 1.1 算法适应性 在时空数据集的可达性查询中，之前针对 ¯PT 可达性的方法可轻松修改以解决 PT 可达性问题。在 ¯PT 场景中于 tc + λ 时刻到达的对象 Oj，在 PT 场景下由于处理延迟 λp 不能立即开始重传，而是在 tc + λt + λp 时刻准备开始交换。同时，也能对 PT 算法进行修改以解决一般的 P ¯T 可达性问题，找到所有接触后，省略会议验证部分即可。经过这些修改，RICC 算法能解决涉及延迟的三类可达性问题。 ### 1.2 实验数据集 实验使用了两种现实数据集： - **移动车辆数据集（MV）**：由 Brinkhoff 数据生成器创建，基于旧金山湾区约 30000 km² 的真实道路网络。包含三组数据，分别记录 1000、2000 和 4000 辆在限速内行驶的车辆信息，每 5 秒记录一次车辆位置，持续四个月（共 2,040,000 个时间点）。假设通过专用短程通信协议（DSRC）进行无线通信，接触距离 dcont = 300 m，分别记为 MV1、MV2 和 MV4。 - **随机路径点数据集（RW）**：使用自定义数据生成器，基于随机路径点模型，常用于模拟移动用户的移动。生成三组数据，分别模拟 10000、20000 和 40000 个人的移动，每 6 秒记录一次位置，持续一个月（共 432,000 个时间点），每组数据覆盖面积为 100 km²。进行两组实验，第一组假设通过蓝牙连接通信，接触距离 dcont = 25 m；第二组假设个体需转移物理物品才能接触，接触距离 dcont = 2 m，分别记为 RW1、RW2 和 RW4。 数据集和索引的大小以及系统规格如下表所示： | 数据集 | 数据集大小 (GB) | 索引大小 (GB) - RICC | 索引大小 (GB) - ReachGrid | | --- | --- | --- | --- | | MV1 | 54 | 17 | 54 | | MV2 | 107 | 56 | 100 | | MV4 | 213 | 175 | 194 | | RW1 | 97 | 31 | 99 | | RW2 | 194 | 120 | 197 | | RW4 | 387 | 419 | 392 | 系统规格： | 项目 | 详情 | | --- | --- | | OS | Linux 2.6 | | 磁盘大小 | 3TB, 7200 RPM | | CPU | 3.3 GHz | | RAM | 16 GB | | 页面大小 | 4096 B | ### 1.3 参数优化 RICC 的查询性能取决于收缩参数 C 和网格分辨率 G，这两个参数依赖于数据集。使用数据集的 10% 子集进行参数调整，若数据在时间上均匀，可使用任意部分；若数据有特定模式（如昼夜、高峰时段等），则创建反映该模式的样本。通过 300 个查询（查询长度在 100 到 500 个时间点之间随机选取）测试性能，找到使 I/O 次数最少的参数对 (C, G)。以 MV1 数据集为例，参数调整结果如下表： | 收缩参数（时间点） \ 网格分辨率（千 km） | 20 | 40 | 60 | 80 | | --- | --- | --- | --- | --- | | 20 | 9295 | 5884 | 5162 | 5779 | | 40 | 9277 | 5876 | 5192 | 5738 | | 60 | 9278 | 5874 | 5127 | 5656 | | 80 | 9260 | 5815 | 5146 | 5413 | 基于此结果，后续涉及 MV1 的实验选取 (C, G) = (60, 60)，其他数据集的参数选取方式类似。 ### 1.4 预处理和索引 - **预处理时间**：预处理时间取决于数据集大小和收缩参数。在参数优化阶段，若多组参数对 (C, G) 的查询性能相近，选择收缩参数 C 较小的那组，以减少预处理时间。数据集的预处理时间从 90 分钟（1000 个对象的移动车辆数据集）到 43 小时（40000 个对象的随机游走数据集，dcont = 25 m）不等。考虑到预处理速度以及每个时间块数据仅读入主存一次，RICC 可用于处理时空数据流。 - **索引大小**：快速可达性算法常面临索引大小过大的问题。当预计算传递闭包时查询时间最短，但这需要与图大小成二次方的空间。而 RICC 能在索引大小相对较小的情况下实现良好的查询性能，因为它预计算的是图的小部分可达性，而非传递闭包。 ### 1.5 查询处理 #### 一对一查询 对 MV 和 RW（dcont = 25 m）数据集创建三组查询，查询长度分别为 100、300 和 500 个时间点，通过计算 I/O 次数评估 RICC 和 ReachGrid 的性能。结果表明，RICC 在所有实例中均优于 ReachGrid。这是因为 ReachGrid 会访问单元格中的每个对象，而 RICC 专注于预计算的会议。随着查询长度增加，ReachGrid 需检查的对象数量迅速增加，在最小数据集（MV1、RW1，会议数量最少）的最长查询中，RICC 比 ReachGrid 最多可提高 5 倍性能。 #### 可扩展性测试 在 MV1 数据集上进行五组查询，时间间隔从 50 到 1600 个时间点不等（1600 个时间点后 MV1 数据集中的所有对象都可达）。结果显示，对于最短查询，RICC 和 ReachGrid 的磁盘访问次数相近，但对于较长查询，RICC 的性能明显更好，在 1600 个时间间隔的查询中最多可提高 6.5 倍，且 RICC 随查询长度的增加扩展性良好。 #### 多对多查询 - **单源多目标查询**：单源多目标查询的性能与一对一查询相同。对于查询 (Os, {OT1, OT2}, I)，回答该查询的时间 t = max(tQ1, tQ2)，I/O 次数 NIO = max(N 1 IO, N 2 IO)，其中 tQi 是目标 ti 到达的时间（或查询间隔结束时间），N i IO 是回答查询 (OS, OTi, I) 所需的 I/O 次数。 - **多源查询**：若算法在索引构建中强烈依赖空间局部性，执行多源查询时性能会下降。在最坏情况下（源点相距很远），查询 ({OS1, OS2}, OT, I) 的 I/O 次数 NIO = N 1 IO1 + N 2 IO2。使用 MV 和 RW（dcont = 25 m）数据集进行实验，随着源点数量增加，RICC 和 ReachGrid 的 I/O 次数差距增大。 #### 长间隔查询 使用 RW1 数据集（dcont = 2 m）进行长间隔查询实验。由于接触距离较小，平均接触度降低，两个对象相互到达的平均时间变长。从 1000 个时间点的查询开始，将查询长度扩展到 8000 个时间点（该数据集约 95% 的对象在查询间隔结束时可达）。由于 ReachGrid 在该场景下查询处理速度极慢，无法完成参数优化和预处理，而 RICC 可有效用于长间隔查询，其性能随查询长度几乎呈线性扩展。 以下是 RICC 算法在不同查询类型下的性能表现流程图： ```mermaid graph LR A[查询类型] --> B[一对一查询] A --> C[可扩展性测试] A --> D[多对多查询] A --> E[长间隔查询] B --> B1[创建查询集] B1 --> B2[评估 RICC 和 ReachGrid 性能] B2 --> B3[RICC 优于 ReachGrid] C --> C1[设置不同时间间隔查询] C1 --> C2[比较 RICC 和 ReachGrid 磁盘访问次数] C2 --> C3[RICC 长查询性能更好] D --> D1[单源多目标查询] D --> D2[多源查询] D1 --> D11[性能与一对一查询相同] D2 --> D21[源点增加差距增大] E --> E1[设置长间隔查询] E1 --> E2[ReachGrid 处理慢] E2 --> E3[RICC 可有效处理] ``` ## 2. 大规模图数据库的距离查询处理 ### 2.1 研究背景与需求 在图算法理论中，图的距离查询是一个被广泛研究的问题，因其具有广泛的应用场景。随着社交网络的兴起，产生了大量的无向无权图。在这些网络中，两个顶点之间的距离反映了实体之间的紧密程度，例如用于查找相互关联的用户或提取社交媒体用户中的社区信息。虽然可以使用广度优先搜索（BFS）来计算图中任意两个顶点之间的距离，但这种方法在主存中无法实现快速查询，也难以适应二级存储解决方案。此外，大多数适用于道路网络的预处理技术无法应用于大规模图，如社交或协作网络。 ### 2.2 现有方法及不足 目前，最有前景的方法是基于 2 - 跳标签或枢纽标签（HL）算法。该算法为每个顶点 v 存储两部分标签 L(v)：前向标签 Lf(v) 和后向标签 Lb(v)，可快速回答顶点到顶点的最短路径查询。此技术已成功应用于道路网络，并最近扩展到无向无权图，还用于道路网络的一对多、多对多和 kNN 查询以及社交网络的 kNN 和 RkNN 查询。 然而，HL 算法在二级存储方面的应用较少。HLDB 将大陆道路网络的枢纽标签存储在商业数据库系统中，并将典型的 HL 距离查询转换为普通 SQL 命令，还展示了如何通过 SQL 查询高效回答 kNN 查询和 k - 最佳途经点。但它仅在道路网络上进行了测试，对于大规模图，由于标签尺寸大，速度会严重下降。HopDB 提出了一种在预处理期间也利用二级存储的定制解决方案，但它仅回答顶点到顶点的查询，是一个定制的 C++ 解决方案，无法与现有数据库系统一起使用，实际应用有限。 ### 2.3 COLD 框架介绍 本文提出了一个纯 SQL 的 COLD 框架（COmpressed Labels on the Database），用于在大规模图上处理多个距离查询。该框架可以回答多种精确距离查询，包括点到点、kNN、RkNN 和一对多查询，是一个适用于各种大规模图问题的完整数据库解决方案。 ### 2.4 相关概念 在介绍 COLD 框架之前，先明确一些相关概念： - **k - 最近邻（kNN）查询**：寻找输入顶点 q 的 k 个最近邻。 - **反向 k - 最近邻（RkNN）查询**：给定查询点 q 和对象集 P，检索所有将 q 作为其 k 个最近邻之一的对象。在图网络中，dist(s, t) 表示两个对象之间的最小网络距离。形式上，RkNN(q) = {p ∈ P : dist(p, q) ≤ dist(p, pk)}，其中 pk 是 p 的 k - 最近邻。本文假设对象位于顶点上，且始终指图上的快照 kNN 和 RkNN 查询，即对象不移动。对象密度 D 指的是图中对象集 P 的大小与顶点总数 |V| 的比值，即 D = |P|/|V|。 ### 2.5 现有图查询方法总结 以下是不同类型图查询（kNN 和 RkNN）在不同网络（道路网络和其他图类）中的现有方法总结： | 查询类型 | 网络类型 | 方法 | 优点 | 缺点 | | --- | --- | --- | --- | --- | | kNN | 道路网络 | G - tree | 平衡树结构 | 无法扩展到大陆道路网络，预处理时间长，需要目标选择阶段，不能用于移动对象 | | kNN | 道路网络 | [17] 扩展的 CRP 算法 | - | 需要目标选择阶段，不能用于移动对象，仅对查询位置附近的对象效果好 | | kNN | 道路网络 | SALT 框架 | 可回答多种距离查询，预处理时间快，查询时间优秀，无需目标选择阶段，可用于静态或移动对象 | - | | RkNN | 道路网络 | [30] 使用网络 Voronoi 细胞 | - | 仅在小网络上测试，预处理计算网络 Voronoi 细胞成本高，查询执行时间长，不适合实时场景 | | RkNN | 其他图类 | [32] | - | 仅在稀疏网络上测试，对于密集图和大 k 值的可扩展性存疑 | | RkNN | 时间依赖道路网络 | [10] | - | 测试网络规模有限，查询时间长 | ### 2.6 COLD 框架优势 COLD 框架具有以下优势： - **查询类型丰富**：能够处理多种距离查询，包括之前方法未处理的 RkNN 和一对多查询，为大规模图问题提供了更全面的解决方案。 - **性能优越**：实验结果表明，COLD 在查询时间和效率方面优于以前的方法，包括流行的图数据库。 - **存储空间小**：与以前的方法相比，COLD 需要的存储空间明显更少。 - **可重复性强**：使用流行的开源数据库引擎实现，无需第三方扩展，结果易于重现。 ### 2.7 COLD 框架工作流程 COLD 框架的工作流程如下： ```mermaid graph LR A[输入大规模图数据] --> B[计算顶点标签] B --> C[存储标签到数据库] C --> D[接收查询请求] D --> E{查询类型} E --> |点到点查询| F[执行点到点查询] E --> |kNN 查询| G[执行 kNN 查询] E --> |RkNN 查询| H[执行 RkNN 查询] E --> |一对多查询| I[执行一对多查询] F --> J[返回查询结果] G --> J H --> J I --> J ``` 该流程图展示了 COLD 框架从输入图数据到处理不同类型查询并返回结果的整个过程。首先，计算每个顶点的标签并存储到数据库中。当接收到查询请求时，根据查询类型执行相应的查询操作，最后返回查询结果。 综上所述，无论是时空数据集的可达性查询处理中的 RICC 算法，还是大规模图数据库的距离查询处理中的 COLD 框架，都在各自的领域展现出了良好的性能和适应性，为解决大规模数据的查询问题提供了有效的解决方案。