Graphlab实现分析:图的存储二
Graphlab实现分析:图的存储二
谈吐鱼 发表于4年前
Graphlab实现分析:图的存储二
  • 发表于 4年前
  • 阅读 3211
  • 收藏 43
  • 点赞 6
  • 评论 4

计数排序、CSR和CSC等概念见上一篇博客“Graphlab实现分析:图的存储一”,此篇博客是接着上一篇博客,介绍一下graphlab中图的动态存储。

1 存储结构

Graphlab实现对图的动态存储也是基于csr和csc格式,不过在csr和csc的底层数据结构设计上做了一些调整,将数组替换为分块链表。如果实现对图的动态存储,那么需要把底层的数据结构从数组换成链表,但需要对原先在静态图存储中所用的那套算法做些调整。

动态存储格式的CSR、CSC和边的值数数组如下图所示:

image

1. Edges是一个数组,数据结构使用vector,只是将批量插入的边的权值按顺序放入到vector中。

2. CSR是由行迭代器数组rowIterators和columns组成。columns是一个分块链表,表示按邻近矩阵的行(即边的source vertex)大小排序的列的链表,如上图所示,Block的内容如下,Block是固定长度的pair< uint64_t, uint64_t>数组,多个block组成一个链,pair的first是邻接矩阵的列(即边的target vertex),second是列所在的边在edges数组中的位置。CSR的rowIterators是对链表的行建立索引,rowIterator[i]指向行i在columns中的起始位置偏移地址。

wps_clip_image-9300

3. 对于CSC是有列迭代器数组colIterators和rows组成。Rows是一个分块链表,表示按邻接矩阵的列(即边的target vertex)大小排序的行的链表,如上图所示,Block的内容如下,Block是固定长度的pair<uint64_t, uint64_t>的数组,多个block组成一个链,pair的first是邻接矩阵的行(即边的target vertex),second是行所在的边在edges数组中的位置。colIterators是对链表的列建立索引,colIterators[j]指向列j在rows中的起始位置偏移地址。

wps_clip_image-9345

2 实现步骤

源码中对csr和csc的构建和动态插入的整体流程:

批量输入的边可以用三个数组来表示,source_vertex数组(边的源顶点),target_vertex数组(边的目标顶点)和边的值数组edge_values。

1. 对source_vertex数组进行计数排序,输出P1和rowptrs,P1是按行从小到大顺序对source_vertex进行排序后生成的序列数组;rowptrs[i]指向第i行在P1中的起始偏移地址,P1[rowptrs[i] + k ]表示第i行的第k个元素在edges数组中的位置,其中 0 <= k < (rowptrs[i + 1] - rowptrs[i])。

2. 对target_vertex数组进行计数排序,输出P2和colptrs,P2是按列从小到大顺序对target_vertex进行排序后生成的序列数组;colptrs[j]指向第j列在P2中的起始偏移地址,P2[colptrs[j] + k]表示第j列的第k个元素在edges数组中的位置,其中0 <= k < (colptrs[j + 1] - colptrs[j]);

3. 由于CSR的底层数据结构是分块链表和行迭代器数组指针,所以需要将计数排序后得到的rowptrs、P1和target_vertex转化为迭代器数组和pair<col,pos>数组。分块链表的block是固定长度的pair<col, pos>数组,所以利用P1和target_vertex来构建pair<col, pos>数组csr_values,第i个输入的边在csr_values中的值为{target_vertex[P1[i]], length(edges) + P1[i]}。

3.1 如果图为空,则用rowptrs和csr_values,来初始化CSR,即将csr_values中的值赋值给CSR的columns,然后将rowptrs的行起始位置转化为columns中的迭代器,放入到rowIterators中。

3.2 如果图不为空,则按行向CSR插入数据,一次插入一行,第i行在csr_values中的值是从csr_values[P1[i]]至csr_values[P1[i + 1]]这一段数据。如下图所示的CSR,rowIterators是一个迭代器的数组,rowIterators[i]存放第i行在columns中的起始位置,rowIterators[i + 1]为第i行的结束位置也是第i + 1行的起始位置;columns是一个分块链表。蓝色为第i行的数据,橙色为i+1行的数据。绿色为需要新插入的第i行的数据。

image

往第i行插入新数据,CSR插入行的步骤如下:

A. 首先会找到rowIterators[i+1]所指向的第i行的结束位置Pos,将此block中位于Pos之后的第i+1行的数据段预先保存起来。

B. 将第i行的新数据拷贝到Pos之后位置上,如果新插入的数据过长,那么会创建一个或多个新的block来容纳。

C. 将预先保存的第i+1行的数据重新拷贝到新插入数据之后。

如下图所示:

image

D. 在上述操作完成之后,第i+1行的迭代器指针变为无效,指向的数据位置为第i行新插入的数据,所以要调整第i+1行的迭代器指针。

image

E. 最后因为按行将数据插入到CSR中会产生一些空隙,如上图block中的白色空格,所以会在所有行都插入后,进行repack操作,将空白的内存进行压缩,变为下图所示:

image

CSC的处理类似于CSR,不在赘述,这种做法的只能支持动态地批量插入,随机插入的性能开销太大。

3 Graphlab中相关的类

dynamic_block:图的动态存储的底层数据结构采用内存块的链表,可以进行动态的插入。Dynamic_block就是实现这个内存块的类,dynamic_block组成了一个块的链表。

block_linked_list:分块链表,是使用dynamic_block组成的一个单向链表。

dynamic_csr_storage:实现csr和csc动态存储的数据结构,将底层的数组替换为链表,然后使用链表的迭代器数组来实现记录行或列的起始位置。

dynamic_local_graph:实现图的动态存储的类,图的动态存储针对的情况是批量更新,而不是随机插入。

共有 人打赏支持
粉丝 38
博文 13
码字总数 41855
评论 (4)
小狗狗
顶一个!
pollex
这里的图,指的是<数据结构>里的图?
neo-chen
太高深,真心看不懂
谈吐鱼
惭愧,写的太差
×
谈吐鱼
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: