荐读 | 图计算的查询模式有哪些?

发布于:2022-11-09 ⋅ 阅读:(13) ⋅ 点赞:(0) ⋅ 评论:(0)

我们在了解什么是图计算(图数据库)之前,要先了解一下“图论”是什么。图论是数学家欧拉于18世纪上半叶所开创的,其研究的对象就是图——若干顶点及连接顶点的边所构成的空间拓扑结构(图形),这种图形用来描述事物(顶点)之间的某种关系(边)。显然,我们所说的图形就是网络,而图计算的本质就是面向复杂网络的计算,或者是面向关联数据与关联关系的计算。

图1:图中若干蓝色点,即是“顶点;点与点之间的关系是“边”;点边交错形成复杂的网络

​很多我们日常生活中接触的数据类型在本质上都是图论的研究对象,例如:

· 集合(set)

· 树(tree)

· 列表(list)

· 堆栈(stack)

· 队列(queue)

· 数组(array)或向量(vector)

数组是离散的数据,为什么也会是图论的研究对象呢?

肯定有细心的读者存在这样的疑问。这是因为虽然图论研究的是复杂网络,但在极端的情况下,网络中只存在一组顶点而没有边的时候,这些离散的点就是一组数组。同样的逻辑,基于表结构的关系型数据库可以看作是一种二维数据库,而图数据库本质上是一种高维的数据库,高维可以向下兼容低维,反之则非常困难。

图计算中最关注的有如下几点:

1. 基础的计算与查询模式;

2. 常见的数据结构;

3. 关于计算效率的讨论。

首先我们来看看,图计算中有哪些基础的计算查询模式。其实,其分类方式的不同取决于不同的看待视角,例如是从关联的视角还是离散的视角,再如还可以从图上的查询(遍历操作)的方式来看等

下面,笔者进行下拆分详解。

一是,从关联或离散的角度看,可以分为:

· 离散查询(Discreted Query)

· 关联查询(Connected Query)

最典型的离散查询是面向元数据的查询,在图计算、图数据库的语境下,元数据(meta-data)指顶点或边,因为这两者是最小颗粒度的数据,通常用唯一的ID来标识它们,不需要再作细分。所有仅面向顶点或边的操作,都是典型的离散类型操作。

值得一提的是,有的读者对于边是否算作是元数据表示困惑,认为边并非独立存在,它因为会关联顶点而看起来像是一个复合数据结构。需要指出的是,元数据的定义一方面是最小颗粒度、不可再分,另一方面是,有唯一的匹配的ID来定位它。而在图数据库中,只有顶点和边符合这两点。但是,边的表达的确更为复杂,因为边上面除了ID外,还会关联起点与终点、方向以及其它属性。有一些图计算系统中会对边进行切割,也就是说关联一条边的两个顶点可能会被切分存储在不同的分片中,但是这种切边设计的系统一个是比较少见,另一个是计算效率很低(相比于切点而言的分片逻辑)。

关联查询是图数据库相比于其他数据库而言最有特色的图计算操作。例如,路径查询、K邻查询、子图查询、组网查询、各类图算法等都属于典型的关联查询。关联查询通常是从某个顶点(或多个顶点)出发,通过对边、点以及它们各自的属性进行过滤,来返回相关联的数据集。这种关联查询,从关系型数据库的视角看,类似于表连接的操作,然而,图计算所能带来的灵活性与高性能是关系型数据库所无法比拟的。

二是,从图上的查询(遍历操作)的方式来看,可以分为如下典型的类型:

· 广度优先(BFS)

· 深度优先(DFS)

广度优先的遍历最为典型的是K邻和最短路径查询。以K邻(K-Hop)为例,它的原始的定义是,从某个顶点出发,查找所有和该顶点最短路径距离为K跳(步、层)的所有的不重复的顶点集合。K邻计算的逻辑是如果想知道某个顶点的第K层的全部邻居,需要先知道它的全部K-1层邻居,依此类推。换个角度描述:从该顶点出发,先要找到它的第一层的全部邻居,再到第二层,直到找到所有的第K层邻居为止。

K邻操作在数据量巨大,且高度联通的数据集上面的计算复杂度可能非常大,因为从任何一个节点出发,只要K值够大,就可以联通到所有的节点上面去。在金融场景中,以信用卡交易数据的图计算为例,所有的信用卡和它们的交易对手POS机之间形成的交易网络几乎是完全联通的(这个假设的前提是,每一张卡,只要它消费,就会至少和某个POS机关联,而这个POS机还会与其它卡交易,其它卡还会与更多的POS及关联,这样的网络是高度联通的,甚至是不存在孤点的-在实际操作中,孤点可能会被直接剔除,因为他们对于关联查询是没有意义的),见下图。

图2:信用卡和pos机之间形成的交易网络

如:图3所示,我们演示了不同类型的K-Hop操作,例如K=3时,以及K是一个范围值【1-3】的时候,该操作的返回值的变化。显然后者的数值大于前者,因为它还额外包含了K=1及K=2的情况下的最短路径邻居的数量。

​图3-1:K邻操作示意图

​图3-1:K邻操作示意图

​图3-3:K邻操作示意图

如果把K=1 + K=2 + K=3的K邻的返回数值相加,总和应等于K=【1-3】。这也是通过K邻计算来验证一个图数据库或图计算系统准确性的一种典型的手段。笔者注意到,因为图计算的复杂性而造成的系统性的图计算准确性的问题是普遍存在的,例如第K-1层的顶点重复地出现在第K层,或者第K层中出现的同一个顶点多次,这都属于典型的图计算的广度优先遍历算法实现存在bug的情况。

下图中所示的是典型的BFS与DFS之间在遍历一张有向图时的经过节点的顺序的差异(见图4)。

图4:BFS vs. DFS示意图

​深度优先的算法比较常见于按照某种特定的过滤规则在图中从某个顶点出发寻找到另外一个或多个顶点之间的联通的路径。例如,在银行的交易网络数据中,寻找两个账户之间的全部单一方向的按时序降序或升序排列的转账路径。

理论上,广度优先和深度优先算法都可以完成同样的查询需求,区别在于算法的综合的复杂度与效率,以及对计算资源的消耗。另外,上图中的遍历算法是典型的单线程的遍历逻辑,如果在多线程并发遍历的情况下,具体的每个顶点的被遍历时途径顺序会产生变化,这个笔者会再专写文章再详细剖析。(文/ Ricky)

注:在中文语境下,图计算经常可以等同于图数据库,毕竟图数据库所要完成的最重要的工作就是图计算,我们的讨论也是按此进行。(对图计算与图数据库之间的差异,特别感兴趣的读者,可详细阅读此前笔者写的文章:来自“图”的挑战是什么?如何区分图数据库与图计算? 一文速解)。

预告:下期,我们再聊聊《图计算的数据结构与计算效率》