Given a source node $s$s and a target node $t$t in a graph $G$G, the Personalized PageRank (PPR) from $s$s to $t$t is the probability of a random walk starting from $s$s terminates at $t$t. PPR is a classic measure of...
详细信息
Given a source node $s$s and a target node $t$t in a graph $G$G, the Personalized PageRank (PPR) from $s$s to $t$t is the probability of a random walk starting from $s$s terminates at $t$t. PPR is a classic measure of the relevance between two nodes in a graph. It has been applied in numerous real-world systems. However, existing techniques for PPR queries are not robust to dynamic real-world graphs, which typically have different evolving speeds. Their performance is significantly degraded either at a lower graph evolving rate (e.g., much more queries than updates) or a higher rate. To address the above deficiencies, we propose Agenda to efficiently process, with strong approximation guarantees, the single-source PPR (SSPPR) queries on dynamically evolving graphs with various evolving speeds. Compared with previous methods, Agenda has significantly better workload robustness, while ensuring the same result accuracy. Agenda also has theoretically-guaranteed small query and update costs. Experiments on up to billion-edge scale graphs show that Agenda significantly outperforms state-of-the-art methods for various query/update workloads, while maintaining better or comparable approximation accuracies.
In today's data-driven world and heterogeneous computing environments, processing large-scale graphs in an architecture agnostic manner has become more crucial than ever before. In terms of graph analytics framewo...
详细信息
ISBN:
(纸本)9781450384049
In today's data-driven world and heterogeneous computing environments, processing large-scale graphs in an architecture agnostic manner has become more crucial than ever before. In terms of graph analytics frameworks, on the one side, there has been a significant interest in developing hand-optimized high-performance computing solutions. On the systems side, following the big data movement and to bring parallel computing to the masses, researchers have proposed several graph processing and management systems to handle large-scale graphs. Hand optimized HPC approaches require high expertise and are expensive to maintain and develop, and graph processing frameworks suffer from limited expressibility and performance. We propose Parallel Graph algorithms by Blocks (PGAbB), a block-based graph algorithms framework for shared-memory, multi-core, multi-GPU machines. PGAbB offers a sweet spot between efficient parallelism and architecture agnostic algorithm design for a wide class of graph problems while performing close to hand-optimized HPC *** our PGAbB framework, as well as many other recent HPC graph-analytics frameworks, are highly tuned and able to run complex graph analytics in fractions of seconds on billion-edge graphs, there remains a gap in their end-to-end use. Despite the significant improvements that modern hardware and operating systems have made towards input and output, reading the graph from file systems easily takes thousands of times longer than running the computational kernel itself. This slowdown causes both a disconnect for end users and a loss of productivity for researchers and developers. We close this gap by providing a simple to use, small, header-only, and dependency-free C++11 library, PIGO, that brings I/O improvements to graph and sparse matrix systems. Using PIGO, we improve the end-to-end performance for state-of-the-art systems significantly---in many cases by over 40X.
We propose TEDI, an indexing for solving shortest path, and k Nearest Neighbors (kNN) problems. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node contains...
详细信息
We propose TEDI, an indexing for solving shortest path, and k Nearest Neighbors (kNN) problems. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node contains vertices. The shortest paths are stored in such nodes. These local shortest paths together with the tree structure constitute the index of the graph. Based on this index, algorithms can be executed to solve the shortest path, as well as the kNN problem more efficiently. Our experimental results show that TEDI offers orders-of-magnitude performance improvement over existing approaches on the index construction time, the index size and the query answering. (C) 2015 Elsevier Inc. All rights reserved.
We are given a edge-weighted undirected graph G = (V, E) and a set of labels/colors C = (1, 2,..., p). A non-empty subset C-v subset of C is associated with each vertex u epsilon V. A coloring of the vertices is feasi...
详细信息
We are given a edge-weighted undirected graph G = (V, E) and a set of labels/colors C = (1, 2,..., p). A non-empty subset C-v subset of C is associated with each vertex u epsilon V. A coloring of the vertices is feasible if each vertex v is colored with a color of C-v. A coloring uniquely defines a subset E' subset of E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E' is, in general, NP-hard. In this work we first propose polynomial time algorithms for some special cases, namely when the input graph is a tree, a cactus or with bounded tree-width. Then, an implicit enumeration scheme for finding an optimal coloring in the general case is described and computational results are presented. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论