文档章节

Graphlab实现分析:图的存储二

谈吐鱼
 谈吐鱼
发布于 2014/02/20 22:13
字数 1502
阅读 3249
收藏 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
TOP 10 开源的推荐系统简介

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

Yamazaki
2014/04/29
0
0
Spark之GraphX的特点

1.基于内存实现了数据的复用与快速读取 具有较多迭代次数是图计算算法的一个重要特点。在海量数据背景下,如何保证图计算算法的执行效率是所有图计算模型面对的一个难题。基于MapReduce的图计...

mmake1994
04/16
0
0
Collaborative filtering with GraphChi

原帖地址 http://blog.csdn.net/lzt1983/article/details/7913420 原文链接:Collaborative filtering with GraphChi 本文是GraphChi平台的协同过滤工具箱的快速指南。到目前为止,已经支持A...

七水禾
2014/03/03
0
0
如何搭建满足未来需求的互联网「高速公路」?院士专家们给出了心中的答案

雷锋网 AI 科技评论按:由北京大学深圳研究生院、深圳众享互联科技有限公司以及 YOCSEF 深圳联合主办,深圳市内容中心网络与区块链重点实验室承办的「IEEE HotlCN 2018 区块链技术与应用论坛...

黄善清
08/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
1
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
1
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
0
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
3
0
openJDK之sun.misc.Unsafe类CAS底层实现

注:这篇文章参考了https://www.cnblogs.com/snowater/p/8303698.html 1.sun.misc.Unsafe中CAS方法 在sun.misc.Unsafe中CAS方法如下: compareAndSwapObject(java.lang.Object arg0, long a......

汉斯-冯-拉特
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部