– NII Shonan Meeting | NII Shonan Meeting

The growing interest in “Big Data” has led to an increased interest in designing algorithms and systems for problems with very large inputs. Among these problems, graph problems are among the most challenging: basic algorithmic primitives, such as depth first searches, can not be performed in the data stream model [10] and existing algorithms can be notoriously hard to parallelize, to the extent that numerous graph-specific parallel systems have been developed [15, 16]. Nevertheless, there have recently been exciting developments on graph problems, both in streaming and parallel models, as well as work on sketching and sparsifying graphs. Sketching, Sparsification, and Streaming: One way to deal with the data deluge is to reduce the graph size to something more manageable, while at the same time preserving the key properties of the graph. Examples of this approach include linear sketches and sparsifiers: Parallel and Distributed Computation: Computation on modern massive graphs often proceeds in a distributed manner. Whether it is computing PageRank, clustering, or simply computing shortest paths, practitioners employ many different systems to get at their result. Each of these systems makes different tradeoffs depending on the possible priorities: Is it important to reduce communication? Can we reduce the computational power of each node? How can we ensure good load balancing or guarantee real-time responses? MapReduce has become a very successful distributed computing platform for a wide variety of large-scale computing applications and there have been some success in parallelizing different graph algorithms including: finding connected components [17,19], computing PageRank on a distributed stream [5], and finding dense subgraphs in parallel [6, 23]. However, MapReduce is ill-suited for implementing some types of graph algorithms and can lead to “sub-optimal performance and usability issues” [16]. Indeed, there has been a recent proliferation of systems designed specifically for large-scale graph processing. Recently, there has been work [14] on developing a distributed computing theory for graph processing systems such as Pregel, in a similar way to the theory developed for message passing distributed systems. Earlier work on abstracting the MapReduce model [13] has been very influential. Designing and analyzing algorithms for graph problems in this new abstraction is an important challenge. It will require algorithmic techniques from distributed and stream computation as well as ideas from information theory and communication complexity for proving lower bounds. Comparing and contrasting MapReduce approach with the message passing approach, and understanding when and why one approach works better than the other, will be of fundamental interest to theorists and practitioners alike. Conclusions: In a growing number of applications, there is the need to efficiently process large scale graphs. Developing a theory and principled approach to developing such algorithms represents a new challenge that needs the expertise of researchers in data streams, distributed computing, and graph algorithms. The goal of this workshop is to bring together researchers from these diverse communities to brainstorm and stimulate further development in this exciting and challenging area. Source.

Яндекс.Метрика Рейтинг@Mail.ru Free Web Counter
page counter
Last Modified: April 18, 2016 @ 7:05 am