Approximating series of timestamped data points using a sequence of line segments with a maximum error guarantee is a fundamental data compression problem, termed as piecewise linear approximation (PLA). Due to the increasing need to analyze massive collections of time-series data in diverse domains, the problem has recently received significant attention, and recent PLA algorithms that have emerged do help us handle the overwhelming amount of information, at the cost of some precision loss. More specifically, these algorithms entail a trade-off between the maximum precision loss and the space savings achieved. However, advances in the area of lossless compression are undercutting the offerings of PLA techniques in real datasets. In this work, we propose Sim-Piece, a novel lossy compression algorithm for time-series data that optimizes the space requirements of representing PLA line segments, by finding the minimum number of groups we can organize these segments into, to represent them jointly. Our experimental evaluation demonstrates that our approach readily outperforms competing techniques, attaining compression ratios with more than twofold improvement on average over what PLA algorithms can offer. This allows for providing significantly higher accuracy with equivalent space requirements. Moreover, our algorithm, due to the simplicity of its merging phase, imposes little overhead while compacting the PLA description, offering a significantly improved trade-off between space and running time. The aforementioned benefits of our approach significantly improve the efficiency in which we can store time-series data, while allowing a tight maximum error in the representation of their values.

Contemporary data-systems empowering the daily human activity are routinely represented with graphs. During the last decade, the volume growth of such systems has been unprece-dented. This hinders the timely analysis of the formed networks due to existing physical memory limitations and significant I/O overheads. Graph compression techniques have managed to reduce memory requirements and allow for representing such networks using a few bits-per-edge. Respective approaches offer succinct mappings for social, biological, and information networks while allowing for the efficient access of sought graph elements. Despite their success, such methods mostly focus on static graphs, and predominantly offer access to either a snapshot or an aggregated view of a network. In reality however, networks change over time and, in many instances, we are interested in capturing and studying this evolution. In this paper we propose a framework for compressing emerging temporal graphs based on a dual-representation which articulates both network structure and corresponding temporal information. We empirically establish properties exhibited by community-networks regarding their time aspect(s) and harness these features in our proposed repre-sentation. Our experimental evaluation demonstrates that our approach for compressing temporal graphs readily outperforms competing techniques, attaining compression ratios that are on average around 60% of the space required by state-of-the-art techniques. Moreover, our memory-efficient representation yields more than 70 % faster graph compression and orders of magnitude quicker retrieval of graphs' elements, especially when it comes to large-scale networks. Finally, our framework is the first effort we are aware of, that considers actual time instead of time steps. This helps us attain better control for the size of our representation and reap further memory savings.

Network slicing allows Mobile Network Operators (MNOs) to partition their physical infrastructure into multiple virtual logical networks, enabling the simultaneous servicing of applications with diverse Quality of Service characteristics. In this paper, we introduce and evaluate economic models and policies for the provisioning, across multiple MNOs, of network slice services to Application Providers. We introduce a Network-Slice-as-a-Service model that maps the service offered by a network slice to requirements on virtualized resources. The placement of virtualized resources over the physical infrastructure of MNOs is determined by an embedding problem, formulated as a Mixed Integer Program. We investigate the embedding under: (i) centralized approaches, where a central Broker determines the embedding for all network slice requests, and (ii) peer-to-peer approaches, where each MNO determines the embedding for the sub-set of network slice requests coming from its own customers. We introduce policies for cooperative modes, with the objective of total profit maximization, and for “coopetitive” (cooperative competition) modes, where MNOs aim to maximize their individual profits. The numerical results reveal that MNOs can maximize their aggregate and individual profits under any approach or mode, if they comply with the proposed policies.

Applications in diverse domains such as astronomy, economics and industrial monitoring, increasingly press the need for analyzing massive collections of time series data. The sheer size of the latter hinders our ability to efficiently store them and also yields significant storage costs. Applying general purpose compression algorithms would effectively reduce the size of the data, at the expense of introducing significant computational overhead. Time Series Management Systems that have emerged to address the challenge of handling this overwhelming amount of information, cannot suffer the ingestion rate restrictions that such compression algorithms would cause. Data points are usually encoded using faster, streaming compression approaches. However, the techniques that contemporary systems use do not fully utilize the compression potential of time series data, with implications in both storage requirements and access times. In this work, we propose a novel streaming compression algorithm, suitable for floating point time series data. We empirically establish properties exhibited by a diverse set of time series and harness these features in our proposed encodings. Our experimental evaluation demonstrates that our approach readily outperforms competing techniques, attaining compression ratios that are competitive with slower general purpose algorithms, and on average around 50% of the space required by state-of-the-art streaming approaches. Moreover, our algorithm outperforms all earlier techniques with regards to both compression and access time , offering a significantly improved trade-off between space and speed. The aforementioned benefits of our approach - in terms of all space requirements, compression time and read access - significantly improve the efficiency in which we can store and analyze time series data.

We examine the problem of uncovering communities in complex real-world networks whose elements and their respective associations manifest as streams of data. Community detection is applied in emerging computational environments and concerns critical applications in diverse areas including social computing, web analysis, IoT and biology. Despite the already expended related research efforts, the task of revealing the community structure of massive and rapidly-evolving networks remains very challenging. More specifically, there is an emerging need for online approaches that ingest graph data as a stream. In this paper, we propose a streaming-graph community-detection algorithm that expands seed-sets of nodes to communities. We consider an online setting and process a stream of edges while aiming to form communities on-the-fly using partial knowledge of the graph structure. We use space-efficient structures to maintain very limited information regarding the nodes of the graph and the sought communities, so as to effectively process large scale networks. In addition to our novel streaming approach, we develop a technique that increases the accuracy of our algorithm considerably and additionally propose a new clustering algorithm that allows for automatically deriving the size of the communities we seek to detect. Using ground-truth communities for a wide range of large real-word and synthetic networks, our experimental evaluation shows that our approach does achieve accuracy comparable, and oftentimes better, to the state-of-the-art non-streaming community detection algorithms. More importantly, we attain significant improvements in both execution time and memory requirements.

Graphical data and the network structures that support them are becoming increasingly common and important in engineering and scientific applications. In the context of data compression, such data can be examined at three levels. The structure of a graph can be described as its unlabeled version; the labeling of this structure can be added; and finally, given then structure and labeling, the contents of the labels can be described. In quantifying the amount of information present at each level, and in examining the relationships between them, the notions of symmetry, graph automorphism, and entropy, arise naturally. In this work we consider a class of small-world graphs, where vertices are first connected to their nearest neighbors on a circle and then pairs of non-neighbors are connected according to a distance-dependent distribution. We first determine the degree distribution of this model, and then use it to prove that the model is asymmetric in an appropriate range of parameters. Returning to graph compression, our main results are the computation of the entropy and of the structural entropy of these random graph models.

We consider the problem of uncovering communities in complex real-world networks whose nodes and their respective associations originate in streams of data. Although community detection has received much attention in centralized settings, the prevalence of online social networks has resulted in unprecedented volumes of data whose handling calls for novel streaming approaches. Moreover, bursty production of network interactions necessitates cloud-enabled techniques that can both deal with diverse data rates and deploy more computing resources on the fly for improved performance yields. We propose a distributed streaming community detection approach termed DiCeS, and implement it as a cloud application. While seeking communities, the novelty of our approach is at balancing the incoming load to a cluster of computing nodes and adjusting the cluster processing capacity in an elastic manner. We also provide fault tolerance by ensuring that temporarily suspended or failed nodes are restored and all edges of the network stream ultimately received their due processing. Lastly, DiCeS is interactive regarding i) updating the target communities, and ii) obtaining results on demand. Our experimental results demonstrate that DiCeS does handle the edges of real-world network streams at impressive rates, allows for near-linear scaling, and outperforms previous non-distributed approaches. While using ground-truth communities for a wide range of large real-word networks, we also show that DiCeS attains improved accuracy if compared to earlier centralized algorithms.

A multitude of contemporary applications heavily involve graph data whose size appears to be ever-increasing. This trend shows no signs of subsiding and has caused the emergence of a number of distributed graph processing systems including Pregel, Apache Giraph, and GraphX. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing due to excessive memory demands even for distributed environments. By and large, such contemporary graph processing systems employ ineffective in-memory representations of adjacency lists. Therefore, memory usage patterns emerge as a primary concern in distributed graph processing. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs generated by human activity. In this paper, we propose 1) three compressed adjacency list representations that can be applied to any distributed graph processing system, 2) a variable-byte encoded representation of out-edge weights for space-efficient support of weighted graphs, and 3) a tree-based compact out-edge representation that allows for efficient mutations on the graph elements. We experiment with publicly-available graphs whose size reaches two-billion edges and report our findings in terms of both space-efficiency and execution time. Our suggested compact representations do reduce respective memory requirements for accommodating the graph elements up-to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors.

A multitude of contemporary applications now involve graph data whose size continuously grows and this trend shows no signs of subsiding. This has caused the emergence of many distributed graph processing systems including Pregel and Apache Giraph. However, the unprecedented scale now reached by real-world graphs hardens the task of graph processing even in distributed environments and the current memory usage patterns rapidly become a primary concern for such contemporary graph processing systems. We seek to address this challenge by exploiting empirically-observed properties demonstrated by graphs that are generated by human activity. In this paper, we propose three space-efficient adjacency list representations that can be applied to any distributed graph processing system. Our suggested compact representations reduce respective memory requirements for accommodating the graph elements up to 5 times if compared with state-of-the-art methods. At the same time, our memory-optimized methods retain the efficiency of uncompressed structures and enable the execution of algorithms for large scale graphs in settings where contemporary alternative structures fail due to memory errors.

We improve the state-of-the-art method for the compression of web and other similar graphs by introducing an elegant technique which further exploits the clustering properties observed in these graphs. The analysis and experimental evaluation of our method shows that it outperforms the currently best method of Boldi et al. by achieving a better compression ratio and retrieval time. Our method exhibits vast improvements on certain families of graphs, such as social networks, by taking advantage of their compressibility characteristics, and ensures that the compression ratio will not worsen for any graph, since it easily falls back to the state-of-the-art method.