Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDynamic Balanced Graph Partitioning
93
0
0.0
(
0
)
Added by
Marcin Bienkowski
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between $n$ nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into $ell$ clusters, each of size $k$, such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of inter-cluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with $ell=2$ generalize online paging, and scenarios with $k=2$ constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least $k$, even with significant augmentation. Our main algorithmic contributions are an $O(k log{k})$-competitive deterministic algorithm for the general setting with constant augmentation, and a constant competitive algorithm for the maximum matching variant.
rate research
Read More
We consider the following online optimization problem. We are given a graph $G$ and each vertex of the graph is assigned to one of $ell$ servers, where servers have capacity $k$ and we assume that the graph has $ell cdot k$ vertices. Initially, $G$ does not contain any edges and then the edges of $G$ are revealed one-by-one. The goal is to design an online algorithm $operatorname{ONL}$, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than $varepsilon k$ for constant $varepsilon>0$. Whenever $operatorname{ONL}$ learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, $operatorname{ONL}$ should minimize the competitive ratio: the total cost $operatorname{ONL}$ incurs compared to an optimal offline algorithm $operatorname{OPT}$. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of $O(log ell + log k)$ on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than $Omega(log ell + log k)$. We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of $Theta(ell lg k)$; to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. We believe this technique is of independent interest and will find further applications in the future.
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = log N$, maintaining an $O(mathcal{C} log N)$-coloring with $O(log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $Omega(N^frac{2}{c(c-1)})$ vertices per update, for any constant $c geq 2$.
The dynamic scaling of distributed computations plays an important role in the utilization of elastic computational resources, such as the cloud. It enables the provisioning and de-provisioning of resources to match dynamic resource availability and demands. In the case of distributed graph processing, changing the number of the graph partitions while maintaining high partitioning quality imposes serious computational overheads as typically a time-consuming graph partitioning algorithm needs to execute each time repartitioning is required. In this paper, we propose a dynamic scaling method that can efficiently change the number of graph partitions while keeping its quality high. Our idea is based on two techniques: preprocessing and very fast edge partitioning, called graph edge ordering and chunk-based edge partitioning, respectively. The former converts the graph data into an ordered edge list in such a way that edges with high locality are closer to each other. The latter immediately divides the ordered edge list into an arbitrary number of high-quality partitions. The evaluation with the real-world billion-scale graphs demonstrates that our proposed approach significantly reduces the repartitioning time, while the partitioning quality it achieves is on par with that of the best existing static method.
Many real-world systems, such as social networks, rely on mining efficiently large graphs, with hundreds of millions of vertices and edges. This volume of information requires partitioning the graph across multiple nodes in a distributed system. This has a deep effect on performance, as traversing edges cut between partitions incurs a significant performance penalty due to the cost of communication. Thus, several systems in the literature have attempted to improve computational performance by enhancing graph partitioning, but they do not support another characteristic of real-world graphs: graphs are inherently dynamic, their topology evolves continuously, and subsequently the optimum partitioning also changes over time. In this work, we present the first system that dynamically repartitions massive graphs to adapt to structural changes. The system optimises graph partitioning to prevent performance degradation without using data replication. The system adopts an iterative vertex migration algorithm that relies on local information only, making complex coordination unnecessary. We show how the improvement in graph partitioning reduces execution time by over 50%, while adapting the partitioning to a large number of changes to the graph in three real-world scenarios.
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
