Abstract Multivariate time series analysis is a vital but challenging task, with multidisciplinary applicability, tackling the characterization of multiple interconnected variables over time and their dependencies. Traditional methodologies often adapt univariate approaches or rely on assumptions specific to certain domains or problems, presenting limitations. A recent promising alternative is to map multivariate time series into high-level network structures such as multiplex networks, with past work relying on connecting successive time series components with interconnections between contemporary timestamps. In this work, we first define a novel cross-horizontal visibility mapping between lagged timestamps of different time series and then introduce the concept of multilayer horizontal visibility graphs. This allows describing cross-dimension dependencies via inter-layer edges, leveraging the entire structure of multilayer networks. To this end, a novel parameter-free topological measure is proposed and common measures are extended for the multilayer setting. Our approach is general and applicable to any kind of multivariate time series data. We provide an extensive experimental evaluation with both synthetic and real-world datasets. We first explore the proposed methodology and the data properties highlighted by each measure, showing that inter-layer edges based on cross-horizontal visibility preserve more information than previous mappings, while also complementing the information captured by commonly used intra-layer edges. We then illustrate the applicability and validity of our approach in multivariate time series mining tasks, showcasing its potential for enhanced data analysis and insights.

Abstract We present Jay, a software framework for offloading applications in hybrid edge clouds. Jay provides an API, services, and tools that enable mobile application developers to implement, instrument, and evaluate offloading applications using configurable cloud topologies, offloading strategies, and job types. We start by presenting Jay's job model and the concrete architecture of the framework. We then present the programming API with several examples of customization. Then, we turn to the description of the internal implementation of Jay instances and their components. Finally, we describe the Jay Workbench, a tool that allows the setup, execution, and reproduction of experiments with networks of hosts with different resource capabilities organized with specific topologies. The complete source code for the framework and workbench is provided in a GitHub repository.

Abstract Being able to capture the characteristics of a time series with a feature vector is a very important task with a multitude of applications, such as classification, clustering or forecasting. Usually, the features are obtained from linear and nonlinear time series measures, that may present several data related drawbacks. In this work we introduceNetFas an alternative set of features, incorporating several representative topological measures of different complex networks mappings of the time series. Our approach does not require data preprocessing and is applicable regardless of any data characteristics. Exploring our novel feature vector, we are able to connect mapped network features to properties inherent in diversified time series models, showing thatNetFcan be useful to characterize time data. Furthermore, we also demonstrate the applicability of our methodology in clustering synthetic and benchmark time series sets, comparing its performance with more conventional features, showcasing howNetFcan achieve high-accuracy clusters. Our results are very promising, with network features from different mapping methods capturing different properties of the time series, adding a different and rich feature set to the literature.

MOTIVATION: Network alignment (NA) finds conserved regions between two networks. NA methods optimize node conservation (NC) and edge conservation. Dynamic graphlet degree vectors are a state-of-the-art dynamic NC measure, used within the fastest and most accurate NA method for temporal networks: DynaWAVE. Here, we use graphlet-orbit transitions (GoTs), a different graphlet-based measure of temporal node similarity, as a new dynamic NC measure within DynaWAVE, resulting in GoT-WAVE. RESULTS: On synthetic networks, GoT-WAVE improves DynaWAVE's accuracy by 30% and speed by 64%. On real networks, when optimizing only dynamic NC, the methods are complementary. Furthermore, only GoT-WAVE supports directed edges. Hence, GoT-WAVE is a promising new temporal NA algorithm, which efficiently optimizes dynamic NC. We provide a user-friendly user interface and source code for GoT-WAVE. AVAILABILITY AND IMPLEMENTATION: http://www.dcc.fc.up.pt/got-wave/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Crowd-sourcing the resources of mobile devices is a hot topic of research given the game-changing applications it may enable. In this paper we study the feasibility of using edge-clouds of mobile devices to reduce the load in traditional WiFi infrastructures for video dissemination applications. For this purpose, we designed and implemented a mobile application for video dissemination in sport venues that retrieves replays from a central server, through the access points in the WiFi infrastructure, into a smartphone. The fan's smartphones organize themselves into WiFi-Direct groups and exchange video replays whenever possible, bypassing the central server and access points. We performed a real-world experiment using the live TV feed for the Champions League game Benfica-Besiktas with the help of a group of volunteers using the application at the student's union lounge. The analysis of the logs strongly suggests that edge-clouds can significantly reduce the load in the access points at such large venues and improve quality of experience. Indeed, the edge-clouds formed were able to serve up to 80% of connected users and provide 56% of all downloads requested from within.

With recent advances in high-throughput cell biology, the amount of cellular biological data has grown drastically. Such data is often modeled as graphs (also called networks) and studying them can lead to new insights into molecule-level organization. A possible way to understand their structure is by analyzing the smaller components that constitute them, namely network motifs and graphlets. Graphlets are particularly well suited to compare networks and to assess their level of similarity due to the rich topological information that they offer but are almost always used as small undirected graphs of up to five nodes, thus limiting their applicability in directed networks. However, a large set of interesting biological networks such as metabolic, cell signaling, or transcriptional regulatory networks are intrinsically directional, and using metrics that ignore edge direction may gravely hinder information extraction. Our main purpose in this work is to extend the applicability of graphlets to directed networks by considering their edge direction, thus providing a powerful basis for the analysis of directed biological networks. We tested our approach on two network sets, one composed of synthetic graphs and another of real directed biological networks, and verified that they were more accurately grouped using directed graphlets than undirected graphlets. It is also evident that directed graphlets offer substantially more topological information than simple graph metrics such as degree distribution or reciprocity. However, enumerating graphlets in large networks is a computationally demanding task. Our implementation addresses this concern by using a state-of-the-art data structure, the g-trie, which is able to greatly reduce the necessary computation. We compared our tool to other state-of-the art methods and verified that it is the fastest general tool for graphlet counting.

Recent advances in mobile device technology have triggered research on using their aggregate computational and/or storage resources to form edge-clouds. Whilst traditionally viewed as simple clients, smartphones and tablets today have hardware resources that allow more sophisticated software to be installed, and can be used as thick clients or even thin servers. Simultaneously, new standards and protocols, such as Wi-Fi Direct and Wi-Fi TDLS (Tunneled Direct Link Setup), have been established that allow mobile devices to talk directly with each other, as opposed to over the Internet or across Wi-Fi access points. This can, potentially, lead to ubiquitous, low-latency, device-to-device (D2D) communication. In this paper, we study whether D2D protocols can support mobile-edge clouds by benchmarking different protocols and configurations for a specific application. The results show that decentralized device-to-device techniques can be used to efficiently disseminate multi- media contents while diminishing contention in the wireless infrastructure, allowing for up to 65 % traffic reduction at the access points.

It is well known that many social networks follow the homophily principle, dictating that individuals tend to connect with similar peers. Past studies focused on non-topological properties, such as the age, gender, beliefs or educations. In this paper we focus precisely on the topology itself, exploring the possible existence of pairwise role dependency, that is, purely structural homophily. We show that while pairwise dependency is necessary for some structural roles, it may be misleading for others. We also present SR-Diffuse, a novel method for identifying the structural roles of nodes within a network. It is an iterative algorithm following an optimization model able to learn simultaneously from topological features and structural homophily, combining both aspects. For assessing our method, we applied it in a classification problem in information cascades, comparing its performance against several baseline methods. The experimental results with Flickr and Digg data show that SR-Diffuse can improve the quality of the discovered roles and can better represent the profile of the individuals, leading to a better prediction of social classes within information cascades.

This special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected papers presented at the conference Euro-Par 2014.Euro-Par-the European Conference on Parallel Computing-is an annual series of international conferences dedicated to the promotion and advancement of all aspects of parallel and distributed computing.Euro-Par covers a wide spectrum of topics from algorithms and theory to software technology and hardware-related issues, with application areas ranging from scientific to mobile and cloud computing.The major part of the Euro-Par audience consists of researchers in academic institutions, government laboratories and industrial organisations.Euro-Par 2014, the 20th conference in the Euro-Par series, was held in Porto, Portugal.It was organised by the Computer Science Department of the Faculty of Sciences of the University of Porto.Fifteen broad topics were defined and advertised, covering a large variety of aspects of parallel and distributed computing.The call for papers attracted a total of 267 submissions.The submitted papers were reviewed at least three, and in most cases, four, times (4.02 on average).A total of 68 papers were finally accepted for publication.This makes a global acceptance rate of 25.5%.The authors of accepted papers came from 29 countries, with the four main contributing countries-France, the United States, Spain and Germany-accounting for about 55% of them.Based on the results of the reviews and a majority opinion of the respective topic programme committees, several papers were recommended for a special journal issue.The authors were contacted at the conference and invited to submit revised and extended versions of their papers.These new versions were reviewed independently by three reviewers; two had previously reviewed the conference version, the third had not.Eventually, four papers were accepted for publication.They cover the following four Euro-Par topics: Performance Prediction and Evaluation, Distributed Systems and Algorithms, Theory and Algorithms for Parallel Computation and High-Performance and Scientific Applications.Topic 2 on Performance Prediction and Evaluation contributes the paper Performance prediction of dynamic task-based runtime system for heterogeneous multi-core architectures authored by Luka Stanisic, Samuel Thibault, Arnaud Legrand, Brice Videau and Jean-François Méhaut [1].They address the challenge of deciding, with high accuracy and low effort, what computations to offload onto accelerators on a heterogeneous execution platform.Their coarse-grain hybrid simulation/emulation of StarPU ‡ on SimGrid, a versatile simulator for distributed systems, yields performance predictions of dense linear algebra applications in a matter of seconds and with an accuracy of within a few percent.The reviewers appreciated particularly the volume of experimental results and analysis on a wide range of heterogeneous platforms.Topic 8 on Distributed Systems and Algorithms is represented by the paper A comparative study of spanning tree and gossip protocols for aggregation authored by Lehel Nyers and Márk Jelasity [2].The authors provide a carefully designed comparative study of two paradigms for distributed aggregation queries, like average and sum: gossiping and tree algorithms.With a demonstration suite covering different practical topologies and scenarios, they identify the dominating distinguishing influences and do away with stereotypes such as 'gossip is slow and expensive' and 'trees are fragile and complicated'.The reviewers valued the experimental framework as an effective decision tool for choosing between the two paradigms.Topic 12 on Theory and Algorithms for Parallel Computation contributes the paper On constructing DAG-schedules with large AREAs authored by Scott T.

Computing the frequency of small subgraphs on a large network is a computationally hard task. This is, however, an important graph mining primitive, with several applications, and here we present a novel multicore parallel algorithm for this task. At the core of our methodology lies a state-of-the-art data structure, the g-trie, which represents a collection of subgraphs and allows for a very efficient sequential search. Our implementation was done using Pthreads and can run on any multicore personal computer. We employ a diagonal work sharing strategy to dynamically and effectively divide work among threads during the execution. We assess the performance of our Pthreads implementation on a set of representative networks from various domains and with diverse topological features. For most networks, we obtain a speedup of over 50 for 64 cores and an almost linear speedup up to 32 cores, showcasing the flexibility and scalability of our algorithm. This paves the way for the usage of such counting algorithms on larger subgraph and network sizes without the obligatory access to a cluster.

Comparing scientific production across different fields of knowledge is commonly controversial and subject to disagreement. Such comparisons are often based on quantitative indicators, such as papers per researcher, and data normalization is very difficult to accomplish. Different approaches can provide new insight and in this paper we focus on the comparison of different scientific fields based on their research collaboration networks. We use co-authorship networks where nodes are researchers and the edges show the existing co-authorship relations between them. Our comparison methodology is based on network motifs, which are over represented patterns, or sub graphs. We derive motif fingerprints for 22 scientific fields based on 29 different small motifs found in the corresponding co-authorship networks. These fingerprints provide a metric for assessing similarity among scientific fields, and our analysis shows that the discrimination power of the 29 motif types is not identical. We use a co-authorship dataset built from over 15,361 publications inducing a co-authorship network with over 32,842 researchers. Our results also show that we can group different fields according to their fingerprints, supporting the notion that some fields present higher similarity and can be more easily compared.

Abstract Logic programming provides a high-level view of programming, giving implementers a vast latitude into what techniques to explore to achieve the best performance for logic programs. Towards obtaining maximum performance, one of the holy grails of logic programming has been to design computational models that could be executed efficiently and that would allow both for a reduction of the search space and for exploiting all the available parallelism in the application. These goals have motivated the design of the Extended Andorra Model (EAM), a model where goals that do not constrain nondeterministic goals can execute first. In this work, we present and evaluate the Basic design for EAM, a system that builds upon David H. D. Warren's original EAM with Implicit Control. We provide a complete description and implementation of the Basic design for EAM System as a set of rewrite and control rules. We present the major data structures and execution algorithms that are required for efficient execution, and evaluate system performance. A detailed performance study of our system is included. Our results show that the system achieves acceptable base performance and that a number of applications benefit from the advanced search inherent to the EAM.

Finding and counting the occurrences of a collection of subgraphs within another larger network is a computationally hard problem, closely related to graph isomorphism. The subgraph count is by itself a very powerful characterization of a network and it is crucial for other important network measurements. G-tries are a specialized data-structure designed to store and search for subgraphs. By taking advantage of subgraph common substructure, g-tries can provide considerable speedups over previously used methods. In this paper we present a parallel algorithm based precisely on g-tries that is able to efficiently find and count subgraphs. The algorithm relies on randomized receiver-initiated dynamic load balancing and is able to stop its computation at any given time, efficiently store its search position, divide what is left to compute in two halfs, and resume from where it left. We apply our algorithm to several representative real complex networks from various domains and examine its scalability. We obtain an almost linear speedup up to 128 processors, thus allowing us to reach previously unfeasible limits. We showcase the multidisciplinary potential of the algorithm by also applying it to network motif discovery.

We address the problem of providing transparent, lightweight, fault-tolerance mechanisms for generic peer-to-peer middleware systems. The main idea is to use the peer-to-peer overlay to provide for fault-tolerance rather than support it higher up in the middleware architecture, e.g. in the form of services. To evaluate our approach we have implemented a fault-tolerant middleware prototype that uses a hierarchical peer-to-peer overlay in which the leaf peers connect to sensors that provide data streams. Clients connect to the root of the overlay and request streams that are routed upwards through intermediate peers in the overlay up to the client. We report encouraging preliminary results for latency, jitter and resource consumption for both the non-faulty and faulty cases.

Complex networks from domains like Biology or Sociology are present in many e-Science data sets. Dealing with networks can often form a workflow bottleneck as several related algorithms are computationally hard. One example is detecting characteristic patterns or "network motifs" - a problem involving subgraph mining and graph isomorphism. This paper provides a review and runtime comparison of current motif detection algorithms in the field. We present the strategies and the corresponding algorithms in pseudo-code yielding a framework for comparison. We categorize the algorithms outlining the main differences and advantages of each strategy. We finally implement all strategies in a common platform to allow a fair and objective efficiency comparison using a set of benchmark networks. We hope to inform the choice of strategy and critically discuss future improvements in motif detection.

Abstract Inductive logic programming (ILP) is a sub‐field of machine learning that provides an excellent framework for multi‐relational data mining applications. The advantages of ILP have been successfully demonstrated in complex and relevant industrial and scientific problems. However, to produce valuable models, ILP systems often require long running times and large amounts of memory. In this paper we address fundamental issues that have direct impact on the efficiency of ILP systems. Namely, we discuss how improvements in the indexing mechanisms of an underlying logic programming system benefit ILP performance. Furthermore, we propose novel data structures to reduce memory requirements and we suggest a new lazy evaluation technique to search the hypothesis space more efficiently. These proposals have been implemented in the April ILP system and evaluated using several well‐known data sets. The results observed show significant improvements in running time without compromising the accuracy of the models generated. Indeed, the combined techniques achieve several order of magnitudes speedup in some data sets. Moreover, memory requirements are reduced in nearly half of the data sets. Copyright © 2008 John Wiley & Sons, Ltd.

The amount of data collected and stored in databases is growing considerably for almost all areas of human activity. Processing this amount of data is very expensive, both humanly and computationally. This justifies the increased interest both on the automatic discovery of useful knowledge from databases, and on using parallel processing for this task. Multi relational data mining (MRDM) techniques, such as inductive logic programming (ILP), can learn rides from relational databases consisting of multiple tables. However, ILP systems are designed to run in main memory and can have long running times. We propose a pipelined data-parallel algorithm for ILP. The algorithm was implemented and evaluated on a commodity PC cluster with 8 processors. The results show that our algorithm yields excellent speedups, while preserving the quality of learning

Logic programming languages, such as Prolog, provide a high-level, declarative approach to programming. Logic Programming offers great potential for implicit parallelism, thus allowing parallel systems to often reduce a program's execution time without programmer intervention. We believe that for complex applications that take several hours, if not days, to return an answer, even limited speedups from parallel execution can directly translate to very significant productivity gains. It has been argued that Prolog's evaluation strategy – SLD resolution – often limits the potential of the logic programming paradigm. The past years have therefore seen widening efforts at increasing Prolog's declarativeness and expressiveness. Tabling has proved to be a viable technique to efficiently overcome SLD's susceptibility to infinite loops and redundant subcomputations. Our research demonstrates that implicit or-parallelism is a natural fit for logic programs with tabling. To substantiate this belief, we have designed and implemented an or-parallel tabling engine – OPTYap – and we used a shared-memory parallel machine to evaluate its performance. To the best of our knowledge, OPTYap is the first implementation of a parallel tabling engine for logic programming systems. OPTYap builds on Yap's efficient sequential Prolog engine. Its execution model is based on the SLG-WAM for tabling, and on the environment copying for or-parallelism. Preliminary results indicate that the mechanisms proposed to parallelize search in the context of SLD resolution can indeed be effectively and naturally generalized to parallelize tabled computations, and that the resulting systems can achieve good performance on shared-memory parallel machines. More importantly, it emphasizes our belief that through applying or-parallelism and tabling to logic programs the range of applications for Logic Programming can be increased.

Abstract This paper presents a new Web‐based system, Mooshak, to handle programming contests. The system acts as a full contest manager as well as an automatic judge for programming contests. Mooshak innovates in a number of aspects: it has a scalable architecture that can be used from small single server contests to complex multi‐site contests with simultaneous public online contests and redundancy; it has a robust data management system favoring simple procedures for storing, replicating, backing up data and failure recovery using persistent objects; it has automatic judging capabilities to assist human judges in the evaluation of programs; it has built‐in safety measures to prevent users from interfering with the normal progress of contests. Mooshak is an open system implemented on the Linux operating system using the Apache HTTP server and the Tcl scripting language. This paper starts by describing the main features of the system and its architecture with reference to the automated judging, data management based on the replication of persistent objects over a network. Finally, we describe our experience using this system for managing two official programming contests. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents a multithreaded abstract machine for the TyCO process calculus. We argue that process calculi provide a powerful framework to reason about fine-grained parallel computations. They allow for the construction of formally verifiable systems on which to base high-level programming idioms, combined with efficient compilation schemes into multithreaded architectures.

We propose a programming model for distributed concurrent systems with mobile objects in the context of a process calculus. Code mobility is induced by lexical scoping on names. Objects and messages migrate towards the site where their prefixes are lexically bound. Class definitions, on the other hand, are downloaded from the site where they are defined, and are instantiated locally upon arrival. We provide several programming examples to demonstrate the expressiveness of the model. Finally, based on this model we describe an architecture for a run-time system supporting concurrent, distributed computations and code mobility.

Run-time work distribution in parallel programming systems is usually accomplished through the use of dynamic scheduling heuristics. Their sensitivity to run-time information such as global work-load, task granularity, data dependencies, locality of information, among others, is essential when trying to optimize performance. Adaptive schedulers that base their decisions on feed-back from the system are therefore of special importance. We have developed and used a general purpose parallel programming system, the pSystem, that also served as a test-bed environment on which we have experimented and studied the performance of distinct scheduling heuristics. Currently, we have two versions of the system: one based on Unix processes; and the other on Solaris threads. Threads (particularly user-level threads) are usually associated with low execution overheads, since they require minimal interaction with the operating system kernel. This suggests that lower grain parallelism may be more effectively exploited with a thread-based parallel programming system. Performance analysis of both implementations over a set of well known benchmarks, with various schedulers, shows that threads scale better under higher system loads and/or when the granularity of the tasks being executed is below a given threshold value. This paper starts with a description of the design and implementation of the pSystem computational model, followed by a detailed description of several experiments and the analysis of their results. © 1997 John Wiley & Sons, Ltd.