1,721,008 research outputs found
M3: Matrix Multiplication on MapReduce
No full textM3 is an Hadoop library for performing dense and sparse matrix multiplication in MapReduce. The library is based on multi-round algorithms exploiting the 3D decomposition of the problem
Automated generation of model classes for Java PathFinder
No full textModel checkers like Java PathFinder (JPF) often have to combat the state space explosion problem. One solution adopted to tackle this problem is to abstract away parts of the system, e. g., to model complex library classes at a higher level of abstraction. The model classes have the same interface as the actual library classes but exhibit reduced be- haviour and state. Writing such model classes is both error prone and time consuming. In this paper we propose a tool that can automatically derive a model class from the original class. To achieve this goal, the tool uses different algorithms, including slicing and value generation, each yielding a model class with different behaviour and state
Clustering-based Algorithms for Big Data Computations
Full text linkIn the age of big data, the amount of information that applications need to process often exceeds the computational capabilities of single machines. To cope with this deluge of data, new computational models have been defined. The MapReduce model allows the development of distributed algorithms targeted at large clusters, where each machine can only store a small fraction of the data. In the streaming model a single processor processes on-the-fly an incoming stream of data, using only limited memory. The specific characteristics of these models combined with the necessity of processing very large datasets rule out, in many cases, the adoption of known algorithmic strategies, prompting the development of new ones. In this context, clustering, the process of grouping together elements according to some proximity measure, is a valuable tool, which allows to build succinct summaries of the input data. In this thesis we develop novel algorithms for some fundamental problems, where clustering is a key ingredient to cope with very large instances or is itself the ultimate target.
First, we consider the problem of approximating the diameter of an undirected graph, a fundamental metric in graph analytics, for which the known exact algorithms are too costly to use for very large inputs. We develop a MapReduce algorithm for this problem which, for the important class of graphs of bounded doubling dimension, features a polylogarithmic approximation guarantee, uses linear memory and executes in a number of parallel rounds that can be made sublinear in the input graph's diameter. To the best of our knowledge, ours is the first parallel algorithm with these guarantees. Our algorithm leverages a novel clustering primitive to extract a concise summary of the input graph on which to compute the diameter approximation. We complement our theoretical analysis with an extensive experimental evaluation, finding that our algorithm features an approximation quality significantly better than the theoretical upper bound and high scalability.
Next, we consider the problem of clustering uncertain graphs, that is, graphs where each edge has a probability of existence, specified as part of the input. These graphs, whose applications range from biology to privacy in social networks, have an exponential number of possible deterministic realizations, which impose a big-data perspective. We develop the first algorithms for clustering uncertain graphs with provable approximation guarantees which aim at maximizing the probability that nodes be connected to the centers of their assigned clusters. A preliminary suite of experiments, provides evidence that the quality of the clusterings returned by our algorithms compare very favorably with respect to previous approaches with no theoretical guarantees.
Finally, we deal with the problem of diversity maximization, which is a fundamental primitive in big data analytics: given a set of points in a metric space we are asked to provide a small subset maximizing some notion of diversity. We provide efficient streaming and MapReduce algorithms with approximation guarantees that can be made arbitrarily close to the ones of the best sequential algorithms available. The algorithms crucially rely on the use of a k-center clustering primitive to extract a succinct summary of the data and their analysis is expressed in terms of the doubling dimension of the input point set. Moreover, unlike previously known algorithms, ours feature an interesting tradeoff between approximation quality and memory requirements. Our theoretical findings are supported by the first experimental analysis of diversity maximization algorithms in streaming and MapReduce, which highlights the tradeoffs of our algorithms on both real-world and synthetic datasets. Moreover, our algorithms exhibit good scalability, and a significantly better performance than the approaches proposed in previous works
Tools to generate and check consistency of model classes for Java PathFinder
No full textJava PathFinder (JPF) is a model checker for Java applications. Like any other model checker, JPF has to combat the notorious state space explosion problem. Since JPF is a JVM, it can only model check Java bytecode and needs to handle native calls differently. JPF tackles the state space explosion problem and handles native calls by means of so-called model classes and native peers. In this paper we focus on model classes. For a class that either causes a state space explosion or that contains native calls, one can introduce a model class that either abstracts away particular details or implements the native call in Java. Rather than model checking the original class, JPF model checks the model class instead. Writing such model classes is time consuming and error prone. In this paper we propose two tools to assist with the development of model classes. The one tool generates a skeleton of a model class. The other tool checks whether a model class is consistent with the original class
Solving k-center clustering (with outliers) in MapReduce and streaming, almost as accurately as sequentially
Full text linkCenter-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular k-center variant which, given a set S of points from some metric space and a parameter k0, the algorithms yield solutions whose approximation ratios are a mere additive term ε away from those achievable by the best known polynomial-time sequential algorithms, a result that substantially improves upon the state of the art. Our algorithms are rather simple and adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Specifically, our analysis shows that the algorithms become very space-efficient for the important case of small (constant) D. These theoretical results are complemented with a set of experiments on real-world and synthetic datasets of up to over a billion points, which show that our algorithms yield better quality solutions over the state of the art while featuring excellent scalability, and that they also lend themselves to sequential implementations much faster than existing ones
Indexing temporal relations for range-duration queries
Full text linkTemporal information plays a crucial role in many database applications, however support for queries on such data is limited. We present an index structure, termed RD-index, to support range-duration queries over interval timestamped relations, which constrain both the range of the tuples’ positions on the timeline and their duration. RD-index is a grid structure in the two-dimensional space, representing the position on the timeline and the duration of timestamps, respectively. Instead of using a regular grid, we consider the data distribution for the construction of the grid in order to ensure that each grid cell contains approximately the same number of intervals. RD-index features provable bounds on the running time of all the operations, allows for a simple implementation, supports very predictable query performance, and can be constructed and queried in parallel using multithreading. We benchmark our solution on a variety of datasets and query workloads, investigating both the query rate and the behavior of the individual queries. The results show that RD-index performs better than the baselines on range-duration queries, for which it is explicitly designed. Furthermore, it outperforms state of the art indexes also on mixed workloads containing queries that constrain either only the duration or the range along with range-duration queries. Finally, the size of the RD-index is in all settings smaller than the competitors, its construction scales with the number of threads, and parallelization helps improving the runtime of expensive moderate and lowly selective queries
Indexing Temporal Relations for Range-Duration Queries
Full text linkTemporal information plays a crucial role in many database applications,
however support for queries on such data is limited. We present an index
structure, termed RD-index, to support range-duration queries over interval
timestamped relations, which constrain both the range of the tuples' positions
on the timeline and their duration. RD-index is a grid structure in the
two-dimensional space, representing the position on the timeline and the
duration of timestamps, respectively. Instead of using a regular grid, we
consider the data distribution for the construction of the grid in order to
ensure that each grid cell contains approximately the same number of intervals.
RD-index features provable bounds on the running time of all the operations,
allow for a simple implementation, and supports very predictable query
performance. We benchmark our solution on a variety of datasets and query
workloads, investigating both the query rate and the behavior of the individual
queries. The results show that RD-index performs better than the baselines on
range-duration queries, for which it is explicitly designed. Furthermore, it
outperforms specialized indexes also on workloads containing queries
constraining either only the duration or the range
Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce
Full text linkA common approach in the design of MapReduce algorithms is to minimize the number of rounds. Indeed, there are many examples in the literature of monolithic MapReduce algorithms, which are algorithms requiring just one or two rounds. However, we claim that the design of monolithic algorithms may not be the best approach in cloud systems. Indeed, multi-round algorithms may exploit some features of cloud platforms by suitably setting the round number according to the execution context.In this paper we carry out an experimental study of multi-round MapReduce algorithms aiming at investigating the performance of the multi-round approach. We use matrix multiplication as a case study. We first propose a scalable Hadoop library, named M3, for matrix multiplication in the dense and sparse cases which allows to tradeoff round number with the amount of data shuffled in each round and the amount of memory required by reduce functions. Then, we present an extensive study of this library on an in-house cluster and on Amazon Web Services aiming at showing its performance and at comparing monolithic and multi-round approaches. The experiments show that, even without a low level optimization, it is possible to design multi-round algorithms with a small running time overhead
- …
