X-Stream: edge-centric graph processing using streaming partitions

By Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel. Symposium on Operating Systems Principles, 2013

746 citations recorded by the source corpus.

X-Stream is a system for processing both in-memory and out-of-core graphs on a single shared-memory machine. While retaining the scatter-gather programming model with state stored in the vertices, X-Stream is novel in (i) using an edge-centric rather than a vertex-centric implementation of this model, and (ii) streaming completely unordered edge lists rather than performing random access. This design is motivated by the fact that sequential bandwidth for all storage media (main memory, SSD, and magnetic disk) is substantially larger than random access bandwidth. We demonstrate that a large number of graph algorithms can be expressed using the edge-centric scatter-gather model. The resulting implementations scale well in terms of number of cores, in terms of number of I/O devices, and across different storage media. X-Stream competes favorably with existing systems for graph processing. Besides sequential access, we identify as one of the main contributors to better performance the fact that X-Stream does not need to sort edge lists during preprocessing.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/4bc31853ab9de45df2e03a0ea991f89d9449e42b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

PARTIES: QoS-Aware Resource Partitioning for Multiple Interactive Services (2019, background): “For example, traditionally throughputbound applications, like big data and graph analytics, are now moving to in-memory computation, with frameworks like Spark [60] and X-Stream [48], which brings task execution latencies to a few milliseconds or seconds.”
Gemini: A Computation-Centric Distributed Graph Processing System (2016, positive): “Inspired by the implementation of several single-node graph processing systems [29, 42, 49, 57, 60], Gemini adopts a chunk-based partitioning scheme that enables a low-overhead scaling out design.”
Graphicionado: A high-performance and energy-efficient accelerator for graph analytics (2016, methodology): “Software Graph Processing Frameworks In addition to the popular software graph processing frameworks described in Section II-A, GraphChi [29], TurboGraph [17], and XStream [42] are also similar frameworks utilizing disk-based systems for graph processing.”
Exploiting iterative-ness for parallel ML computations (2014, background): “Othermachine learning frameworks emphasize features outside the scope of this paper, such as out-of-core disk scheduling [27, 36].”
GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning (2015, background): “GraphChi [13], X-Stream [21] and other out-of-core systems [9, 15, 31, 34] provide alternative solutions.”
NeuGraph: Parallel Deep Neural Network Computation on Large Graphs (2019, background): “, GraphChi [24], Grace [34], FlashGraph [53], XStream [36] and Chaos [35]), distributed shared memory and RDMA (e.”
Scalability! But at what COST? (2015, neutral): “scalable system cores twitter uk-2007-05 Stratosphere [6] 16 950s X-Stream [17] 16 1159s Spark [8] 128 1784s 8000s Giraph [8] 128 200s 8000s GraphLab [8] 128 242s 714s GraphX [8] 128 251s 800s”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, methodology): “Single-machine graph processing systems: There are also several efforts aiming at leveraging multicore platforms for graph processing [39, 46, 53, 57, 65, 66, 92, 101] which focus on such issues as improving out-of-core accesses [39], selecting appropriate execution modes [65], supporting a sophisti”