Shulou(Shulou.com)06/02 Report--

Graphlab how to achieve analysis chart storage, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Some time ago, I participated in the development of an iterative computing platform, and had a strong interest in memory computing and graph computing. During this period, I also read the relevant papers of spark and pregel to understand the BSP model, but I always felt that reading the paper was too abstract, so I chose to read the graphlab source code as an opportunity to understand graph computing in depth. Next, if I have time, I will record in detail some superficial understanding of graphlab.

In graphlab, the adjacency matrix is used to represent the adjacent relationship between vertices. Given a graph G (V, E), an one-dimensional array is used to store the vertex information of V, and a sparse matrix is used to store the edge information of E.

In graphlab, the graph is distributed on multiple machines, and part of the graph is stored in each machine. Here we discuss how each node in graphlab implements the local storage of the graph.

There are two interfaces in the graph-related interface of graphlab, which are in edges and out edges for getting vertices. Then in graphlab, we need to consider how to effectively store the edge set of a graph, and we can quickly index the in edges and out edges of vertices, and reduce the space overhead as much as possible.

The idea adopted in Graphlab is to use both the csr (compressed sparse row) and csc (compressed sparse column) storage formats of sparse matrix to store the edge set of the graph, and to efficiently implement the interface of in edges and out edges for obtaining vertices.

Graphlab realizes the static storage and dynamic storage of the graph respectively. Static storage means that once the vertices and edges of the graph are stored, no new vertices and edges will be added. On the other hand, dynamic storage can dynamically add vertices and edges to the graph, both of which do not delete vertices and edges. Both static storage and dynamic storage use csr and csc format of sparse matrix to store edge sets, but the data structure of csr and csr is different. Static storage is realized by array and dynamic storage is realized by linked list. In this blog, only static storage will be introduced, while dynamic storage will be introduced in the next blog.

First, I will introduce the csr and csc formats of sparse matrices and count sorting, and then I will give a practical example to analyze the static storage of graphlab diagrams and introduce the related classes of graphlab implementation diagrams.

1 introduction to csr and csc formats and counting sorting of sparse matrices

1.1 introduction to csr and csc formats

Csr uses three arrays to represent a sparse matrix, which is represented by A, and the three arrays are the values of non-zero units in A stored in row order in values, rowptrs, and columns;values, respectively. Columns stores the column index of the cells in the values array. If values (k) = A (I, j), then columns [k] = j. The starting address of the row in values is stored in Rowptrs. If values (k) = A (I, j), then rowptrs (I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.