内置并行图形算法的优点

内置并行图形算法的优点

根据 DB-Engines.com,图数据库是所有数据管理中发展最迅速的一个类别。是什么让图数据库如此热门?

许多人已经知道图算法是复杂业务用例中最有效的,有时是唯一的解决方案,例如聚集不同的用户组(社区检测),找到有影响力的人或实体(PageRank算法),或预测用户行为以进行个性化 推荐(标签传播算法)。 但是,通常不知道Graph也是解决问题的理想方法,其中可能存在未知数量的连接以连接两个实体。 这种类型的问题在垂直行业中很常见,包括企业知识,供应链分析和能源流量计算等用例。

此博客描述了Graph如何以自然,简洁和有效的方式解决这些问题,并且可以在亚秒内提供答案,即使在遍历数亿个实体和关系时也是如此。

问题描述

让我们考虑一个分析公司之间关系的简单例子。

只有一个表所有权(公司,所有者,百分比)有三列,其中每行描述所有者拥有的公司的百分比。

业务查询(输出):找到拥有A公司最多的前K个“最终所有者”公司。最终所有者是不属于任何其他公司的公司。

输入:公司A的名称,整数K.

例如,给定公司1作为图1中的输入,公司9拥有公司1的大部分。

 

挑战

有两个挑战:

 

1.未知数量的连接。我们不知道X公司可能拥有多少级别/步骤(直接或间接)。

 

2.可能有多条路径,从A公司到拥有A公司所有权的公司X的步骤不同。例如,X公司可能在A公司拥有5个中间公司,但也可能拥有所有权。公司A到3个中间公司在另一条路上。此外,一条路径上的5家中间公司和第二条路径上的3家中间公司可能重叠也可能不重叠。

 

作为图1中的示例,公司9通过两条具有不同长度的路径拥有公司1。 RDBMS和NoSQL DB不是为有效处理多跳(连接)而设计的。此外,标准SQL没有任何方式来表达“重复连接直到达到目标。”此外,在大数据集上,非图形DB甚至老一代图形DB上的计算时间和精力都是令人望而却步的。原因是这些体系结构没有以最低限度和高效率完成工作所需的以顶点为中心的并行计算。他们浪费地加入整个表格,即使大多数表格都不相关。

 

上述类型的问题出现在许多行业和用例中。例如,在供应链管理中,我们可以有物料清单表BOM(部件,父件,数量)。每行描述一个Part(第一列)是制作Parent_Part(第二列)所需的组件之一,第三列描述了制作一个Parent_Part所需的Part单元数。我们再次遇到与上述相同的两个挑战:部分X可能通过未知数量的步骤依赖于部分Y.有许多业务问题需要沿着具有不同步骤的不同路径遍历Part依赖关系图。例如,

 

– 计算是否可以通过所需部件的当前库存满足某些最终产品的订单。

 

– 如果某些部件的价格发生变化,计算最终产品的价格变化。

 

– 电网也需要应对这些挑战。如果一个或多个组件脱机,则该实用程序需要知道它对下游和上游组件以及电源线有何影响。

内置并行的图解决方案

现在,我们描述如何在图查询语言(如TigerGraph及其查询语言GSQL)中使用具有内置并行性的图数据库来轻松高效地解决这类问题。并行性之所以重要,是因为它是实现许多面向图问题的自然而有效的方法。研究过一些图算法的计算机科学家知道,他们通常会有步骤,从“每个顶点/每个边/每个顶点的邻居”开始,每个条件的“这些”意味着我们需要为一个集合中的每个成员执行相同的任务。如果集合很大,那么完成工作的有效方法是并行的。GSQL具有内置的并行性,因此很容易表示这些“针对每个”任务。

 

有几种方法可以解决这个公司所有权问题,这说明了GSQL的功能和灵活性。在TigerGraph的并行读取计算更新执行流中,一个查询或算法的行为类似于图的分布式漫游或遍历:我们从一组指定的顶点开始,然后遵循一个逐步漫游或遍历到相邻边的计划。在此过程中,我们从顶点或边缘收集数据。我们可以将数据传递给我们遇到的顶点,或者保存到最后。

方法1

高层的想法是通过两次公司所有权图。每个过程从公司A开始,并通过所有权边缘进行传播。第一关基本上是准备阶段。它只是简单地计算Y公司直接拥有的并且在A公司也有所有权的公司的数量。在第二遍中,对每个Y公司计算的这个数字被用于确保每个公司在传播之前完全总结A公司的所有所有权。TS对A公司的所有权属于直接拥有它的公司。例如,在图1中,公司4存储数字2,因为它的两个邻居拥有公司1的所有权。

第二个通行证将A公司的所有权百分比传播给直接或间接拥有A公司的所有公司。每个所有者公司都会等待,直到收到第一个通行证中计算的直接所有者数量的所有权消息。然后,它获得了A公司的全部所有权,并将部分所有权传播给它的所有者。对于图1的示例,公司2等待直到收到1条消息(70%的所有权)。在接收到这个消息后,它会向它的所有者发送消息。它向公司5发送消息“42%”(70%x 0.6),向公司3发送消息“28%”(70%x 0.4)。

请注意,我们只计算每个所有者公司Y的总所有权一次,这是有效的。在像供应链和能量流分析这样的用例中,它们需要的传播计算(例如,价格、电压或电流的变化)是计算密集度更高的,因此跨图的高效单次计算对实时性能非常重要。

请参见图2中的GSQL查询。完整的解决方案包括图形模型和GSQL查询可在Tigergraph的Github存储库中获得。