笔记整理：付可意，天津大学硕士

链接：https://cz5waila03cyo0tux1owpyofgoryroob.oss-cn-beijing.aliyuncs.com/94/21/41/94214132B7EE971885A7C9E079D45807.pdf

动机

本文工作的动机是大数据分析，用于时间关键型海上和空中机动预测。以异构格式从各种数据源（即雷达、卫星）实时收集并转换为RDF格式，最终生成大量GB大小的时空RDF数据。对这种数据集进行高效和可扩展的查询能够为更高级别的数据分析任务提供支持，例如基于移动性和天气属性的轨迹聚类。但目前使用Spark并行处理RDF数据的方法并不专门用于处理时空数据。这意味着时空处理必须作为预处理或后处理步骤进行开发。

但这种“解耦”方法错过了在查询处理管道早期修剪不必要数据的机会，并不可避免地导致性能下降。基于此，本文提出了DiStRDF引擎，它包括两个主要模块：存储层和处理层。存储层提供了时空RDF数据的分布式存储，并在磁盘上精心组织数据和存储布局。处理层是一个查询引擎，它为时空RDF数据提供逻辑和物理运算符，从而为不同的执行计划提供了提高性能的机会。本文在航空和海上领域的真实数据（来自ATM域的4D数据）上的实验评估证明了DiStRDF 系统在使用各种时空范围约束时的效率。

亮点

DiStRDF系统的亮点主要有：

（1）本文开发了一种1D编码方案，该方案将时空信息注入到存储的RDF数据中，而且通过实现基于Z阶的编码，能将一维编码方案从3D扩展到4D情况，有助于实现高效的分布式时空RDF查询处理。

（2）DiStRDF存储层存储编码的RDF三元组和整数标识符与RDF资源之间的映射字典，还使用属性表和列式存储布局来提高性能。

概念及模型

DiStRDF系统架构

DiStRDF系统由两层组成：(A)负责解析和处理SPARQL查询的DiStRDF处理层和(B)负责存储RDF数据的DiStRDF存储层。用户向DiStRDF处理层提供SPARQL查询和单独的时空约束。SPARQL查询解析组件检查查询语法的正确性并将其转换为机器可读的表示形式。Logical Plan Builder组件创建查询的逻辑计划表示，它将SPARQL查询与时空约束结合在一起，并由一组逻辑运算符组成。然后，通过为每个逻辑运算符选择实现算法，物理计划构造器组件将逻辑计划转换为物理表示。处理层利用ApacheSpark在一组计算机器上并行执行查询。

一维(1D)编码方案

空间位置的映射使用网格将空间划分为2m=(2m/2∗2m/2)等大小的单元格，并使用空间填充曲线为网格的空间单元格提供排序。下图显示了m=4的2D情况的示例，其中描述了Hilbert和Z阶曲线，以及分配给每个单元的ID。空间填充曲线旨在通过使附近的单元格也在曲线上靠近来保持空间局部性。

为了处理时间维度，考虑时间划分T={T₀，T₁，……}，其中，T_i表示时间间隔。不假设划分的特定性质，即时间划分的长度(或持续时间)可以变化，除了划分是不相交的，它们覆盖整个时间域，并且在时间顺序上T_i先于T_i+1。如图2所示，每个时间分区T i与2D空间网格相关联。唯一的限制是对于所有时间分区T_i使用相同的网格结构(即，2^m等大小的单元)。

逻辑计划构建器组件

逻辑查询计划通过确定一组逻辑运算符的分层顺序来表示执行相应 SPARQL 查询的方法。查询计划通常表示为一棵树，它由对应于逻辑运算符的一组连接的节点组成。每个节点最多可以有两个子节点和零个或多个父节点。节点将子节点的结果作为输入，并计算其逻辑运算符描述的操作的结果；然后将该结果提供给它们的父节点以继续查询执行。如果一个节点有零子节点（即叶节点），那么它的输入是数据的物理来源。此外，如果一个节点没有父节点（即根节点），那么它的输出被认为是查询结果。

本文构建逻辑计划的流程是将查询解析组件提供的BGP作为输入，并输出逻辑规划树的根节点。最初遍历BGP的三元组模式，并为每个三元组模式创建一个选择操作符。对于三元组模式中指定的每个值，运算符分配一个过滤器值。选择运算符被添加到 LP 列表中。遍历 LP 列表中包含的运算符，尝试找到公共变量名称。匹配运算符由 Join 运算符以及它们的匹配字段组合在一起，这些字段将用作连接条件。然后，在添加其中的新连接运算符之前，这些运算符从 LP 列表中删除。当在 LP 列表中找不到其他匹配运算符时，循环结束。不包含公共变量名称的剩余运算符与表示它们之间交叉连接的 Join 运算符组合在一起。如前所述，孩子从 LP 中删除，其中添加了新的 Join 运算符。当 LP 列表仅留下单个元素时，此循环结束。在 LP 列表的元素上应用投影算子，指定将分配给结果的字段显示名称，以匹配用户提供的名称。投影算子是逻辑计划构建器组件的输出。

上述程序产生的逻辑计划示例如图5所示：

实验

下图分别展示了评估监视航空监测航空查询所需的执行时间和飞行计划域，使用各种逻辑查询计划。

本实验说明通过应用近似时空过滤的好处从一个数量级到 100% 不等。这些结果表明，与常规时空滤波器相比，近似过滤效率是合理的。

总结

本文针对时空SPARQL查询处理问题，提出了一个并行的、可扩展的内存解决方案。DiStRDF系统由一个处理层和一个存储层组成，该解决方案的显著特点包括支持不同的查询执行计划，以及在不同的数据组织上高效地存储时空数据。实验表明，该系统能够在几秒钟内高效地处理具有时空范围限制的RDF查询。已实现的DiStRDF系统的当前状态支持几个真实世界的SPARQL查询，这些查询大多由三重模式和时空范围约束定义。

OpenKG

OpenKG（中文开放知识图谱）旨在推动以中文为核心的知识图谱数据的开放、互联及众包，并促进知识图谱算法、工具及平台的开源开放。

点击阅读原文，进入 OpenKG 网站。