| 1. |
- Abbas, Zainab
(författare)
-
Scalable Streaming Graph and Time Series Analysis Using Partitioning and Machine Learning
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Recent years have witnessed a massive increase in the amount of data generated by the Internet of Things (IoT) and social media. Processing huge amounts of this data poses non-trivial challenges in terms of the hardware and performance requirements of modern-day applications. The data we are dealing with today is of massive scale, high intensity and comes in various forms. MapReduce was a popular and clever choice of handling big data using a distributed programming model, which made the processing of huge volumes of data possible using clusters of commodity machines. However, MapReduce was not a good fit for performing complex tasks, such as graph processing, iterative programs and machine learning. Modern data processing frameworks, that are being popularly used to process complex data and perform complex analysis tasks, overcome the shortcomings of MapReduce. Some of these popular frameworks include Apache Spark for batch and stream processing, Apache Flink for stream processing and Tensor Flow for machine learning.In this thesis, we deal with complex analytics on data modeled as time series, graphs and streams. Time series are commonly used to represent temporal data generated by IoT sensors. Analysing and forecasting time series, i.e. extracting useful characteristics and statistics of data and predicting data, is useful for many fields that include, neuro-physiology, economics, environmental studies, transportation, etc. Another useful data representation we work with, are graphs. Graphs are complex data structures used to represent relational data in the form of vertices and edges. Graphs are present in various application domains, such as recommendation systems, road traffic analytics, web analysis, social media analysis. Due to the increasing size of graph data, a single machine is often not sufficient to process the complete graph. Therefore, the computation, as well as the data, must be distributed. Graph partitioning, the process of dividing graphs into subgraphs, is an essential step in distributed graph processing of large scale graphs because it enables parallel and distributed processing.The majority of data generated from IoT and social media originates as a continuous stream, such as series of events from a social media network, time series generated from sensors, financial transactions, etc. The stream processing paradigm refers to the processing of data streaming that is continuous and possibly unbounded. Combining both graphs and streams leads to an interesting and rather challenging domain of streaming graph analytics. Graph streams refer to data that is modelled as a stream of edges or vertices with adjacency lists representing relations between entities of continuously evolving data generated by a single or multiple data sources. Streaming graph analytics is an emerging research field with great potential due to its capabilities of processing large graph streams with limited amounts of memory and low latency. In this dissertation, we present graph partitioning techniques for scalable streaming graph and time series analysis. First, we present and evaluate the use of data partitioning to enable data parallelism in order to address the challenge of scale in large spatial time series forecasting. We propose a graph partitioning technique for large scale spatial time series forecasting of road traffic as a use-case. Our experimental results on traffic density prediction for real-world sensor dataset using Long Short-Term Memory Neural Networks show that the partitioning-based models take 12x lower training time when run in parallel compared to the unpartitioned model of the entire road infrastructure. Furthermore, the partitioning-based models have 2x lower prediction error (RMSE) compared to the entire road model. Second, we showcase the practical usefulness of streaming graph analytics for large spatial time series analysis with the real-world task of traffic jam detection and reduction. We propose to apply streaming graph analytics by performing useful analytics on traffic data stream at scale with high throughput and low latency. Third, we study, evaluate, and compare the existing state-of-the-art streaming graph partitioning algorithms. We propose a uniform analysis framework built using Apache Flink to evaluate and compare partitioning features and characteristics of streaming graph partitioning methods. Finally, we present GCNSplit, a novel ML-driven streaming graph partitioning solution, that uses a small and constant in-memory state (bounded state) to partition (possibly unbounded) graph streams. Our results demonstrate that \ours provides high-throughput partitioning and can leverage data parallelism to sustain input rates of 100K edges/s. GCNSplit exhibits a partitioning quality, in terms of graph cuts and load balance, that matches that of the state-of-the-art HDRF (High Degree Replicated First) algorithm while storing three orders of magnitude smaller partitioning state.
|
|
| 2. |
- Abbas, Zainab, 1991-, et al.
(författare)
-
Short-Term Traffic Prediction Using Long Short-Term Memory Neural Networks
- 2018
-
Ingår i: Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services. - : Institute of Electrical and Electronics Engineers Inc.. - 9781538672327 ; , s. 57-65
-
Konferensbidrag (refereegranskat)abstract
- Short-term traffic prediction allows Intelligent Transport Systems to proactively respond to events before they happen. With the rapid increase in the amount, quality, and detail of traffic data, new techniques are required that can exploit the information in the data in order to provide better results while being able to scale and cope with increasing amounts of data and growing cities. We propose and compare three models for short-term road traffic density prediction based on Long Short-Term Memory (LSTM) neural networks. We have trained the models using real traffic data collected by Motorway Control System in Stockholm that monitors highways and collects flow and speed data per lane every minute from radar sensors. In order to deal with the challenge of scale and to improve prediction accuracy, we propose to partition the road network into road stretches and junctions, and to model each of the partitions with one or more LSTM neural networks. Our evaluation results show that partitioning of roads improves the prediction accuracy by reducing the root mean square error by the factor of 5. We show that we can reduce the complexity of LSTM network by limiting the number of input sensors, on average to 35% of the original number, without compromising the prediction accuracy. .
|
|
| 3. |
- Abbas, Zainab, 1991-, et al.
(författare)
-
Streaming Graph Partitioning: An Experimental Study
- 2018
-
Ingår i: Proceedings of the VLDB Endowment. - : ACM Digital Library. - 2150-8097. ; 11:11, s. 1590-1603
-
Tidskriftsartikel (refereegranskat)abstract
- Graph partitioning is an essential yet challenging task for massive graph analysis in distributed computing. Common graph partitioning methods scan the complete graph to obtain structural characteristics offline, before partitioning. However, the emerging need for low-latency, continuous graph analysis led to the development of online partitioning methods. Online methods ingest edges or vertices as a stream, making partitioning decisions on the fly based on partial knowledge of the graph. Prior studies have compared offline graph partitioning techniques across different systems. Yet, little effort has been put into investigating the characteristics of online graph partitioning strategies.In this work, we describe and categorize online graph partitioning techniques based on their assumptions, objectives and costs. Furthermore, we employ an experimental comparison across different applications and datasets, using a unified distributed runtime based on Apache Flink. Our experimental results showcase that model-dependent online partitioning techniques such as low-cut algorithms offer better performance for communication-intensive applications such as bulk synchronous iterative algorithms, albeit higher partitioning costs. Otherwise, model-agnostic techniques trade off data locality for lower partitioning costs and balanced workloads which is beneficial when executing data-parallel single-pass graph algorithms.
|
|
| 4. |
- Ahlberg, Michael, et al.
(författare)
-
Router placement in wireless sensor networks
- 2006
-
Ingår i: 2006 IEEE International Conference on Mobile Adhoc and Sensor Systems, Vols 1 and 2. - : IEEE. - 9781424405060 ; , s. 498-501
-
Konferensbidrag (refereegranskat)abstract
- In this paper we propose and evaluate algorithms for placement of routers in a wireless sensor network. There are two major requirements on router placement First, a placement must guarantee connectivity, i.e. every sensor must be able to communicate through routers with a predefined computer-connected gateway node. Second, a placement must provide robust communication in the case of router failures. This is achieved by placing redundant routers that increase the number of possible routes. Both requirements should be met by placing as few routers as possible. The proposed algorithms compute placement in an efficient and reasonably fast way.
|
|
| 5. |
- Al-Shishtawy, Ahmad, 1978-, et al.
(författare)
-
Achieving Robust Self-Management for Large-Scale Distributed Applications
- 2010
-
Ingår i: Self-Adaptive and Self-Organizing Systems (SASO), 2010 4th IEEE International Conference on. - : IEEE Computer Society. - 9781424485376 ; , s. 31-40
-
Konferensbidrag (refereegranskat)abstract
- Achieving self-management can be challenging, particularly in dynamic environments with resource churn (joins/leaves/failures). Dealing with the effect of churn on management increases the complexity of the management logic and thus makes its development time consuming and error prone. We propose the abstraction of robust management elements (RMEs), which are able to heal themselves under continuous churn. Using RMEs allows the developer to separate the issue of dealing with the effect of churn on management from the management logic. This facilitates the development of robust management by making the developer focus on managing the application while relying on the platform to provide the robustness of management. RMEs can be implemented as fault-tolerant long-living services. We present a generic approach and an associated algorithm to achieve fault-tolerant long-living services. Our approach is based on replicating a service using finite state machine replication with a reconfigurable replica set. Our algorithm automates the reconfiguration (migration) of the replica set in order to tolerate continuous churn. The algorithm uses P2P replica placement schemes to place replicas and uses the P2P overlay to monitor them. The replicated state machine is extended to analyze monitoring data in order to decide on when and where to migrate. We describe how to use our approach to achieve robust management elements. We present a simulation-based evaluation of our approach which shows its feasibility.
|
|
| 6. |
- Al-Shishtawy, Ahmad, 1978-, et al.
(författare)
-
Distributed Control Loop Patterns for Managing Distributed Applications
- 2008
-
Ingår i: SASOW 2008. - LOS ALAMITOS : IEEE Computer Society. - 9781424434688 ; , s. 260-265
-
Konferensbidrag (refereegranskat)abstract
- In this paper we discuss various control loop patterns for managing distributed applications with multiple control loops. We introduce a high-level framework, called DCMS, for developing, deploying and managing component-based distributed applications in dynamic environments. The control loops, and interactions among them, are illustrated in the context of a distributed self-managing storage service implemented using DCMS to achieve various self-* properties. Different control loops are used for different self-* behaviours, which illustrates one way to divide application management, which makes for both ease of development and for better scalability and robustness when managers are distributed. As the multiple control loops are not completely independent, we demonstrate different patterns to deal with the interaction and potential conflict between multiple managers.
|
|
| 7. |
- Al-Shishtawy, Ahmad, 1978-, et al.
(författare)
-
ElastMan : Autonomic elasticity manager for cloud-based key-value stores
- 2013
-
Ingår i: HPDC 2013 - Proceedings of the 22nd ACM International Symposium on High-Performance Parallel and Distributed Computing. - New York, NY, USA : ACM. - 9781450319102 ; , s. 115-116
-
Konferensbidrag (refereegranskat)abstract
- The increasing spread of elastic Cloud services, together with the pay-as-you-go pricing model of Cloud computing, has led to the need of an elasticity controller. The controller automatically resizes an elastic service in response to changes in workload, in order to meet Service Level Objectives (SLOs) at a reduced cost. However, variable performance of Cloud virtual machines and nonlinearities in Cloud services complicates the controller design. We present the design and evaluation of ElastMan, an elasticity controller for Cloud-based elastic key-value stores. ElastMan combines feedforward and feedback control. Feedforward control is used to respond to spikes in the workload by quickly resizing the service to meet SLOs at a minimal cost. Feedback control is used to correct modeling errors and to handle diurnal workload. We have implemented and evaluated ElastMan using the Voldemort key-value store running in a Cloud environment based on OpenStack. Our evaluation shows the feasibility and effectiveness of our approach to automation of Cloud service elasticity.
|
|
| 8. |
- Al-Shishtawy, Ahmad, et al.
(författare)
-
ElastMan : Elasticity manager for elastic key-value stores in the cloud
- 2013
-
Ingår i: ACM International Conference Proceeding Series. - New York, NY, USA : ACM. - 9781450321723
-
Konferensbidrag (refereegranskat)abstract
- The increasing spread of elastic Cloud services, together with the pay-as-you-go pricing model of Cloud computing, has led to the need of an elasticity controller. The controller automatically resizes an elastic service in response to changes in workload, in order to meet Service Level Objectives (SLOs) at a reduced cost. However, variable performance of Cloud Virtual Machines and nonlinearities in Cloud services, such as the diminishing reward of adding a service instance with increasing the scale, complicates the controller design. We present the design and evaluation of ElastMan, an elasticity controller for Cloud-based elastic key-value stores. ElastMan combines feedforward and feedback control. Feedforward control is used to respond to spikes in the workload by quickly resizing the service to meet SLOs at a minimal cost. Feedback control is used to correct modeling errors and to handle diurnal workload. To address nonlinearities, our design of ElastMan leverages the near-linear scalability of elastic Cloud services in order to build a scale-independent model of the service. We have implemented and evaluated ElastMan using the Voldemort key-value store running in an OpenStack Cloud environment. Our evaluation shows the feasibility and effectiveness of our approach to automation of Cloud service elasticity.
|
|
| 9. |
- Al-Shishtawy, Ahmad, et al.
(författare)
-
Enabling Self-Management Of Component Based Distributed Applications
- 2008
-
Ingår i: FROM GRIDS TO SERVICE AND PERVASIVE COMPUTING. - Boston, MA : Springer-Verlag New York. - 9780387094557 ; , s. 163-174
-
Konferensbidrag (refereegranskat)abstract
- Deploying and managing distributed applications in dynamic Grid environments requires a high degree of autonomous management. Programming autonomous management in turn requires programming environment support and higher level abstractions to become feasible. We present a framework for programming self-managing component-based distributed applications. The framework enables the separation of application’s functional and non-functional (self-*) parts. The framework extends the Fractal component model by the component group abstraction and one-to-any and one-to-all bindings between components and groups. The framework supports a network-transparent view of system architecture simplifying designing application self-* code. The framework provides a concise and expressive API for self-* code. The implementation of the framework relies on scalability and robustness of the Niche structured p2p overlay network. We have also developed a distributed file storage service to illustrate and evaluate our framework.
|
|
| 10. |
- Apolonia, Nuno, et al.
(författare)
-
Gossip-based service monitoring platform for wireless edge cloud computing
- 2017
-
Ingår i: Proceedings IEEE 14th International Conference on Networking, Sensing and Control (ICNSC). - : Institute of Electrical and Electronics Engineers (IEEE).
-
Konferensbidrag (refereegranskat)abstract
- Edge cloud computing proposes to support shared services, by using the infrastructure at the network's edge. An important problem is the monitoring and management of services across the edge environment. Therefore, dissemination and gathering of data is not straightforward, differing from the classic cloud infrastructure. In this paper, we consider the environment of community networks for edge cloud computing, in which the monitoring of cloud services is required. We propose a monitoring platform to collect near real-time data about the services offered in the community network using a gossip-enabled network. We analyze and apply this gossip-enabled network to perform service discovery and information sharing, enabling data dissemination among the community. We implemented our solution as a prototype and used it for collecting service monitoring data from the real operational community network cloud, as a feasible deployment of our solution. By means of emulation and simulation we analyze in different scenarios, the behavior of the gossip overlay solution, and obtain average results regarding information propagation and consistency needs, i.e. in high latency situations, data convergence occurs within minutes.
|
|
