文档章节

Graphlab实现分析:图的存储二

谈吐鱼
 谈吐鱼
发布于 2014/02/20 22:13
字数 1502
阅读 3277
收藏 43

<p>计数排序、CSR和CSC等概念见上一篇博客“Graphlab实现分析:图的存储一”,此篇博客是接着上一篇博客,介绍一下graphlab中图的动态存储。</p> <h3>1 存储结构</h3> <p>Graphlab实现对图的动态存储也是基于csr和csc格式,不过在csr和csc的底层数据结构设计上做了一些调整,将数组替换为分块链表。如果实现对图的动态存储,那么需要把底层的数据结构从数组换成链表,但需要对原先在静态图存储中所用的那套算法做些调整。</p> <p>动态存储格式的CSR、CSC和边的值数数组如下图所示:</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221316_CzyD.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201402/20221316_f4Sl.png" width="420" height="288" /></a> </p> <p>1. Edges是一个数组,数据结构使用vector,只是将批量插入的边的权值按顺序放入到vector中。</p> <p>2. CSR是由行迭代器数组rowIterators和columns组成。columns是一个分块链表,表示按邻近矩阵的行(即边的source vertex)大小排序的列的链表,如上图所示,Block的内容如下,Block是固定长度的pair&lt; uint64_t, uint64_t&gt;数组,多个block组成一个链,pair的first是邻接矩阵的列(即边的target vertex),second是列所在的边在edges数组中的位置。CSR的rowIterators是对链表的行建立索引,rowIterator[i]指向行i在columns中的起始位置偏移地址。</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221316_CJVW.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="wps_clip_image-9300" border="0" alt="wps_clip_image-9300" src="http://static.oschina.net/uploads/img/201402/20221317_byvd.png" width="446" height="41" /></a></p> <p>3. 对于CSC是有列迭代器数组colIterators和rows组成。Rows是一个分块链表,表示按邻接矩阵的列(即边的target vertex)大小排序的行的链表,如上图所示,Block的内容如下,Block是固定长度的pair&lt;uint64_t, uint64_t&gt;的数组,多个block组成一个链,pair的first是邻接矩阵的行(即边的target vertex),second是行所在的边在edges数组中的位置。colIterators是对链表的列建立索引,colIterators[j]指向列j在rows中的起始位置偏移地址。</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221317_96tZ.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="wps_clip_image-9345" border="0" alt="wps_clip_image-9345" src="http://static.oschina.net/uploads/img/201402/20221317_pPmc.png" width="447" height="41" /></a></p> <h3>2 实现步骤</h3> <p>源码中对csr和csc的构建和动态插入的整体流程:</p> <p>批量输入的边可以用三个数组来表示,source_vertex数组(边的源顶点),target_vertex数组(边的目标顶点)和边的值数组edge_values。</p> <p>1. 对source_vertex数组进行计数排序,输出P1和rowptrs,P1是按行从小到大顺序对source_vertex进行排序后生成的序列数组;rowptrs[i]指向第i行在P1中的起始偏移地址,P1[rowptrs[i] + k ]表示第i行的第k个元素在edges数组中的位置,其中 0 &lt;= k &lt; (rowptrs[i + 1] - rowptrs[i])。</p> <p>2. 对target_vertex数组进行计数排序,输出P2和colptrs,P2是按列从小到大顺序对target_vertex进行排序后生成的序列数组;colptrs[j]指向第j列在P2中的起始偏移地址,P2[colptrs[j] + k]表示第j列的第k个元素在edges数组中的位置,其中0 &lt;= k &lt; (colptrs[j + 1] - colptrs[j]);</p> <p>3. 由于CSR的底层数据结构是分块链表和行迭代器数组指针,所以需要将计数排序后得到的rowptrs、P1和target_vertex转化为迭代器数组和pair&lt;col,pos&gt;数组。分块链表的block是固定长度的pair&lt;col, pos&gt;数组,所以利用P1和target_vertex来构建pair&lt;col, pos&gt;数组csr_values,第i个输入的边在csr_values中的值为{target_vertex[P1[i]], length(edges) + P1[i]}。</p> <p>3.1 如果图为空,则用rowptrs和csr_values,来初始化CSR,即将csr_values中的值赋值给CSR的columns,然后将rowptrs的行起始位置转化为columns中的迭代器,放入到rowIterators中。</p> <p>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行的数据。</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221317_q9OB.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201402/20221318_wCtV.png" width="439" height="165" /></a> </p> <p>往第i行插入新数据,CSR插入行的步骤如下:</p> <p>A. 首先会找到rowIterators[i+1]所指向的第i行的结束位置Pos,将此block中位于Pos之后的第i+1行的数据段预先保存起来。</p> <p>B. 将第i行的新数据拷贝到Pos之后位置上,如果新插入的数据过长,那么会创建一个或多个新的block来容纳。</p> <p>C. 将预先保存的第i+1行的数据重新拷贝到新插入数据之后。</p> <p>如下图所示:</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221318_Uy92.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201402/20221318_h8hk.png" width="439" height="221" /></a> </p> <p>D. 在上述操作完成之后,第i+1行的迭代器指针变为无效,指向的数据位置为第i行新插入的数据,所以要调整第i+1行的迭代器指针。</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221318_ZZ4s.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201402/20221319_qTA7.png" width="440" height="192" /></a> </p> <p>E. 最后因为按行将数据插入到CSR中会产生一些空隙,如上图block中的白色空格,所以会在所有行都插入后,进行repack操作,将空白的内存进行压缩,变为下图所示:</p> <p><a href="http://static.oschina.net/uploads/img/201402/20221319_9IUd.png"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="image" border="0" alt="image" src="http://static.oschina.net/uploads/img/201402/20221319_yncj.png" width="442" height="194" /></a> </p> <p>CSC的处理类似于CSR,不在赘述,这种做法的只能支持动态地批量插入,随机插入的性能开销太大。</p> <h3>3 Graphlab中相关的类</h3> <p><b>dynamic_block</b>:图的动态存储的底层数据结构采用内存块的链表,可以进行动态的插入。Dynamic_block就是实现这个内存块的类,dynamic_block组成了一个块的链表。</p> <p><b>block_linked_list</b>:分块链表,是使用dynamic_block组成的一个单向链表。</p> <p><b>dynamic_csr_storage</b>:实现csr和csc动态存储的数据结构,将底层的数组替换为链表,然后使用链表的迭代器数组来实现记录行或列的起始位置。</p> <p><b>dynamic_local_graph</b>:实现图的动态存储的类,图的动态存储针对的情况是批量更新,而不是随机插入。</p>

© 著作权归作者所有

共有 人打赏支持
谈吐鱼
粉丝 37
博文 13
码字总数 41855
作品 0
杭州
程序员
私信 提问
加载中

评论(4)

谈吐鱼
谈吐鱼
惭愧,写的太差
netkiller-
netkiller-
太高深,真心看不懂
pollex
pollex
这里的图,指的是<数据结构>里的图?
小狗狗
小狗狗
顶一个!
Graphlab实现分析:图的存储一

前一段时间参与了一个迭代计算平台的开发,对于内存计算和图计算产生了比较浓厚的兴趣,这期间也阅读了spark和pregel的相关论文,了解一下BSP模型,但总觉得看论文太抽象了,于是选择阅读gra...

谈吐鱼
2014/01/21
0
0
hello dato--graphlab create

Install Dato(GraphLab Create) Dato需要注册才能使用, 并且有30天的试用期. 下面使用python的虚拟环境安装一个干净的dato测试环境: 如果是旧版本升级, 则到dato-env下执行: 测试dato可用: 如...

zqhxuyuan
08/27
0
0
1-机器学习启蒙- Python基础语法与工具

机器学习正在改变世界 以前的机器学习观点 我为什么学习机器学习?机器人:人工智能应用。 亚马逊零售推荐,Google广告。电影推荐,音乐推荐,社交推荐。 机器学习管道 数据通过机器学习算法...

天涯明月笙
02/06
0
0
TOP 10 开源的推荐系统简介

最 近这两年推荐系统特别火,本文搜集整理了一些比较好的开源推荐系统,即有轻量级的适用于做研究的SVDFeature、LibMF、LibFM等,也有重 量级的适用于工业系统的 Mahout、Oryx、EasyRecd等,...

oschina
2014/04/29
51.8K
31
TOP 10 开源的推荐系统简介

最 近这两年推荐系统特别火,本文搜集整理了一些比较好的开源推荐系统,即有轻量级的适用于做研究的SVDFeature、LibMF、LibFM等,也有重 量级的适用于工业系统的 Mahout、Oryx、EasyRecd等,...

Yamazaki
2014/04/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Integer使用双等号比较会发生什么

话不多说,根据以下程序运行,打印的结果为什么不同? Integer a = 100;Integer b = 100;System.out.println(a == b);//print : trueInteger a = 200;Integer b = 200;System.out.pr...

兜兜毛毛
15分钟前
0
0
CockroachDB

百度云上的CockroachDB 云数据库 帮助文档 > 产品文档 > CockroachDB 云数据库 > 产品描述 开源NewSQL – CockroachDB在百度内部的应用与实践 嘉宾演讲视频及PPT回顾:http://suo.im/5bnORh ...

miaojiangmin
26分钟前
1
0
I2C EEPROM驱动实例分析

上篇分析了Linux Kernel中的I2C驱动框架,本篇举一个具体的I2C设备驱动(eeprom)来对I2C设备驱动有个实际的认识。 s3c24xx系列集成了一个基于I2C的eeprom设备at24cxx系列。at24cxx系列芯片包...

yepanl
28分钟前
2
0
设计模式之工厂模式

本篇博文主要翻译这篇文章: https://www.journaldev.com/1392/factory-design-pattern-in-java 由于翻译水平有限,自认为许多地方翻译不恰当,欢迎各位给出宝贵的建议,建议大家去阅读原文。...

firepation
今天
5
0

中国龙-扬科
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部