【MIT博士论文】高效现实世界图分析的系统与技术，110页pdf

图是模拟现实世界实体及其相互关系的自然方式，涵盖了从社交网络和生物数据集到云计算基础设施数据血统图等。在这些大型图上进行查询常常涉及到成本高昂的子图遍历和复杂的分析计算。此外，现实世界中的图通常编码了随时间演变的关系，这种关系被模型化为时间图，即边与时间属性（如开始时间和持续时间）相关联的图。这些现实世界的图往往比通用的顶点与边模型更有结构性，但这一洞察大多未被现有的图引擎用于图查询优化探索。此外，大多数时间图处理系统仍然效率不高，因为即使是在普通商用服务器的可用存储内也适合的图，它们也依赖于分布式处理。为此，我们提出了两个专为优化大规模实际图处理而设计的系统。第一个系统Kaskade，通过利用图和查询的结构属性来推断物化图视图，加速查询评估，通过重写查询来解决高效查询评估的挑战，这些查询基于输入图和查询特征被认为是有益的。第二个系统Kairos，引入了选择性索引，一种根据底层时间图和输入查询的特征选择一部分目标顶点进行索引的技术。该系统进一步采用了一种专为内存存储和快速检索时间边而设计的高度专业化的并行数据结构。最终，Kairos建立在共享内存并行图处理的事实标准系统Ligra之上，为应用程序开发者提供了类似的优势和熟悉的API。这两个系统在与其他基准相比时提供了高达50-60倍的加速，并引入了旨在高效实现实际图分析的新颖的查询优化技术类别。