Large scale graph processing represents an interesting challenge due to the lack of locality. This paper presents Path Graph for improving iterative graph computation on graphs with billions of edges. Our system design has three unique features: First, we model a large graph using a collection of tree-based partitions and use an path-centric computation rather than vertex-centric or edge-centric computation. Our parallel computation model significantly improves the memory and disk locality for performing iterative computation algorithms. Second, we design a compact storage that further maximize sequential access and minimize random access on storage media. Third, we implement the path-centric computation model by using a scatter/gather programming model, which parallels the iterative computation at partition tree level and performs sequential updates for vertices in each partition tree. The experimental results show that the path-centric approach outperforms vertex centric and edge-centric systems on a number of graph algorithms for both in-memory and out-of-core graphs.

The volume of RDF data continues to grow over the past decade and many known RDF datasets have billions of triples. A grant challenge of managing this huge RDF data is how to access this big RDF data efficiently. A popular approach to addressing the problem is to build a full set of permutations of (S, P, O) indexes. Although this approach has shown to accelerate joins by orders of magnitude, the large space overhead limits the scalability of this approach and makes it heavyweight. In this paper, we present TripleBit, a fast and compact system for storing and accessing RDF data. The design of TripleBit has three salient features. First, the compact design of TripleBit reduces both the size of stored RDF data and the size of its indexes. Second, TripleBit introduces two auxiliary index structures, ID-Chunk bit matrix and ID-Predicate bit matrix, to minimize the cost of index selection during query evaluation. Third, its query processor dynamically generates an optimal execution ordering for join queries, leading to fast query execution and effective reduction on the size of intermediate results. Our experiments show that TripleBit outperforms RDF-3X, MonetDB, BitMat on LUBM, UniProt and BTC 2012 benchmark queries and it offers orders of mangnitude performance improvement for some complex join queries.

The scale of RDF graph grows very rapidly. Managing huge scale RDF graph distributively is becoming increasingly important. Partitioning RDF graph is a vital pre-processing step for the goal. When applying graph partitioning algorithms developed over past decades to RDF graph represented using well known RDF model such as Directed Labeled Graphs, Bipartite Graph, the vertices which a triple depends on may be in different partitions. Such partitioning on the RDF models induces huge communication overhead during processing queries. We argue in this paper that there is need for a representation of RDF to enable the parallel and distributed computing application on RDF data. We propose statement hyper graph model which avoid this crucial deficiency of the graph model of RDF data. The proposed models reduce the decomposition problem to the well-known hyper graph partitioning problem. In the light of this model, we explore the cases like horizontal partitioning, vertical partitioning, grid partitioning, etc and evaluate their performance.