1,720,976 research outputs found
Dragon: Multidimensional Range Queries on Distributed Aggregation Trees,
Get PDFDistributed query processing is of paramount importance in next-generation distribution services, such as Internet of
Things (IoT) and cyber-physical systems. Even if several multi-attribute range queries supports have been proposed for
peer-to-peer systems, these solutions must be rethought to fully meet the requirements of new computational paradigms
for IoT, like fog computing. This paper proposes dragon, an ecient support for distributed multi-dimensional range
query processing targeting ecient query resolution on highly dynamic data. In dragon nodes at the edges of the
network collect and publish multi-dimensional data. The nodes collectively manage an aggregation tree storing data
digests which are then exploited, when resolving queries, to prune the sub-trees containing few or no relevant matches.
Multi-attribute queries are managed by linearising the attribute space through space lling curves. We extensively
analysed dierent aggregation and query resolution strategies in a wide spectrum of experimental set-ups. We show that
dragon manages eciently fast changing data values. Further, we show that dragon resolves queries by contacting a
lower number of nodes when compared to a similar approach in the state of the art
Fast Connected Components Computation in Large Graphs by Vertex Pruning
Get PDFFinding connected components is a fundamental task in applications dealing with graph analytics, such as social network analysis, web graph mining and image processing. The exponentially growing size of today's graphs has required the definition of new computational models and algorithms for their efficient processing on highly distributed architectures. In this paper we present CRACKER, an efficient iterative MapReduce-like algorithm to detect connected components in large graphs. The strategy of CRACKER is to transform the input graph in a set of trees, one for each connected component in the graph. Nodes are iteratively removed from the graph and added to the trees, reducing the amount of computation at each iteration. We prove the correctness of the algorithm, evaluate its computational cost and provide an extensive experimental evaluation considering a wide variety of synthetic and real-world graphs. The experimental results show that CRACKER consistently outperforms state-of-the-art approaches both in terms of total computation time and volume of messages exchanged
NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data
No full textWe present NG-DBSCAN, an approximate density-based clustering
algorithm that operates on arbitrary data and any symmetric
distance measure. The distributed design of our algorithm makes it
scalable to very large datasets; its approximate nature makes it fast,
yet capable of producing high quality clustering results. We provide
a detailed overview of the steps of NG-DBSCAN, together
with their analysis. Our results, obtained through an extensive experimental
campaign with real and synthetic data, substantiate our
claims about NG-DBSCAN’s performance and scalability
Distributed Current Flow Betweeness Centrality
Get PDF—The computation of nodes centrality is of great importance
for the analysis of graphs. The current flow betweenness
is an interesting centrality index that is computed by considering
how the information travels along all the possible paths of a
graph. The current flow betweenness exploits basic results from
electrical circuits, i.e. Kirchhoff’s laws, to evaluate the centrality
of vertices. The computation of the current flow betweenness may
exceed the computational capability of a single machine for very
large graphs composed by millions of nodes. In this paper we
propose a solution that estimates the current flow betweenness in
a distributed setting, by defining a vertex-centric, gossip-based
algorithm. Each node, relying on its local information, in a selfadaptive
way generates new flows to improve the betweenness of
all the nodes of the graph. Our experimental evaluation shows
that our proposal achieves high correlation with the exact current
flow betweenness, and provides a good centrality measure for
large graphs
Model driven generation of mobility traces for distributed virtual environments with TRACE
No full textAvatars' mobility is an essential element to design, validate, and compare different distributed virtual environment architectures. It has a direct impact on the management of such systems because it defines the workload associated with the areas in the virtual world. Currently, a relevant part of this evaluation is conducted by means of synthetic traces generated through mobility models. Despite that, in the last decade, several models have been proposed in literature to describe avatars mobility. However, a standard methodology that drives researchers in their evaluation does not yet exist. In order to alleviate this issue, we present TRACE, an open source tool supporting the generation and analysis of traces by means of embedded mobility models. TRACE's ultimate aim is to facilitate the evaluation and comparison of virtual environments and allow researchers to focus on developing their solution rather than spend time to code and test custom mobility traces. TRACE provides a unified format to describe the traces. It enables scalable and efficient trace generation and analysis for thousands of avatars with seven built-in models. Also, it defines APIs enabling the integration of additional models, different configurations of the environment, and several built-in metrics to analyze the generated traces
Crack random forest for arbitrary large datasets
No full textRandom Forests (RF) of tree classifiers are a state-of-the-art method for classification purposes. RF show limited hyperparameter sensitivity, have high numerical robustness, possess native capacity of dealing with numerical and categorical features, and are quite effective in many real world problems with respect to other state-of-the-art techniques. In this work we show how to crack RF in order to be able to train them on arbitrary large datasets. In particular, we extend ReForeSt, an Apache Spark-based RF implementation. The new version of ReForeSt computation automatically adapts to two methodologies to distribute the data and the computation on the available machines and automatically chooses the one able to provide the result in less time. The new ReForeSt also supports Random Rotations, a quite recent randomization technique which can bust the accuracy of the original RF. We perform an extensive experimental evaluation between ReForeSt and MLlib by taking advantage of the Google Cloud Platform1. We test the performances and the scalability of ReForeSt and MLlib on several real world datasets. Results confirm that ReForeSt outperforms MLlib both in terms of memory and computational efficiency, and classification performances. ReForeSt is publicly available via GitHub2
Telos: An approach for distributed graph processing based on overlay composition
No full textThe recent years have been characterised by the production of a huge amount of data. As matter of fact, human being, overall, is generating an unprecedented amount of data flowing in multiple and heterogeneous sources, ranging from scientific devices, social network, business transactions, etc. Data that is usually represented as a graph, which, due to its size, is often infeasible to process on a single machine. The direct consequence is the need for exploiting parallel and distributed computing frameworks to face this problem. This paper proposes Telos, an high-level approach for large graphs processing. Our approach takes inspiration from overlay networks, that is a widely adopted approach for information dissemination, aggregation and computing orchestration in highly distributed systems. Telos consists of a programming framework supporting the definition of computations on graphs as a composition of overlays, each devoted to a specific aim. The framework is implemented on the top of Apache Spark. A set of experimental results is presented to give a clear evidence of the effectiveness of our approach
Distributed Graph Grocessing: An approach based on overlay composition
No full textNowadays, human being is producing an unprecedented amount of
data coming from multiple and heterogeneous sources, ranging from scientic
devices to business transactions. In many contexts such data is modelled as a
graph, however, due to its size, it is often infeasible to process it on a single
machine. A solution
that is becoming more and more adopted relies on the adoption of distributed
computing frameworks based on the MapReduce paradigm or the BSP model.This paper proposes a multi-layer graph overlay approach to support
the orchestration of distributed, vertex-centric computations targeting Big-
Data problems. Our approach takes
inspiration from the overlay networks, a widely exploited approach for infor-
mation dissemination, aggregation and computing orchestration in massively
distributed systems. We propose Telos, an environment supporting the deni-
tion of multi-layer graph overlays which provides each vertex with a layered,
vertex-centric, view of the graph. Telos is dened on the top of the RDD Spark
abstraction and it has been evaluated by considering two well-known graph
problems. We present a set of experimental results showing the eectiveness
of our approach
- …
