Search

The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliability of transmission channels. Among them, one of the most interesting and successful examples with a highly positive impact in terms of the quality of urban environments and societal and economical welfare is a system of semi-autonomous connected vehicles, where IoT devices, data centers, and fleets of smart vehicles equipped with communication and computational resources are combined into a heterogeneous and distributed infrastructure, unifying hardware, networks, and software. In order to efficiently provide various services (e.g., patrolling, pickup and delivery, monitoring), these systems typically rely on collecting and broadcasting large amounts of data (e.g., sensor data, GPS traces, or maps), which need to be properly collected and processed in a timely manner. As is well documented in the literature, one of the most effective ways to achieve this purpose, especially in a real-time context, is to adopt a graph model of the data (e.g., to model communication networks, roads, or interactions between vehicles) and to employ suitable graph algorithms to solve properly defined computational problems of interest (e.g., shortest paths or distributed consensus). While research in this context has been extensive from a theoretical perspective, works that have focused on the implementation, deployment, and evaluation of the practical performance of graph algorithms for real-world systems of autonomous vehicles have been much rarer. In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous connected vehicles that is currently being tested in the city of L'Aquila (Italy). Then, we present an overview of the computational challenges arising in the considered application domain and provide a systematic survey of known algorithmic results for one of the most relevant classes of computational problems that have to be addressed in said domain, namely, pickup and delivery problems. Finally, we discuss implementation issues, adopted software tools, and the deployment and testing phases concerning one of the algorithmic components of the mentioned real-world system dedicated to handling a specific problem of the above class, namely, the pickup and delivery multi-vehicle problem with time windows. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a directed and weighted graph with a vertex set V of size n and an edge set E of size m such that each edge (u , v) ∈ E has a real-valued weight w (u , c) . An arborescence in G is a subgraph T = (V , E ′) such that, for a vertex u ∈ V , which is the root, there is a unique path in T from u to any other vertex v ∈ V . The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with a minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely, edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well-known problem with applications in several domains such as network design optimization and phylogenetic inference. In this paper, we revisit the algorithmic ideas proposed by several authors for this problem. We provide detailed pseudocode, as well as implementation details, and we present experimental results regarding large scale-free networks and phylogenetic inference. Our implementation is publicly available. [ABSTRACT FROM AUTHOR]

Linear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a theoretical perspective, but their practical performance was unclear. Here, we address this gap. We provide the first implementation of the combinatorial solver by Kelner et al. (STOC 2013), which is appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix (which is SDD) corresponds to a graph; solving symmetric Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our experiments are ambivalent. While they confirm the predicted nearly-linear running time, the constant factors make the solver much slower for reasonable inputs than basic methods with higher asymptotic complexity. We were also not able to use the solver effectively as a smoother or preconditioner. Moreover, while spanning trees with lower stretch indeed reduce the solver's running time, we experience again a discrepancy in practice: in our experiments, simple spanning tree algorithms perform better than those with a guaranteed low stretch. We expect that our results provide insights for future improvements of combinatorial linear solvers. [ABSTRACT FROM AUTHOR]

Computing shortest-path distances is a fundamental primitive in the context of graph data mining, since this kind of information is essential in a broad range of prominent applications, which include social network analysis, data routing, web search optimization, database design and route planning. Standard algorithms for shortest paths (e.g., Dijkstra's) do not scale well with the graph size, as they take more than a second or huge memory overheads to answer a single query on the distance for large-scale graph datasets. Hence, they are not suited to mine distances from big graphs, which are becoming the norm in most modern application contexts. Therefore, to achieve faster query answering, smarter and more scalable methods have been designed, the most effective of them based on precomputing and querying a compact representation of the transitive closure of the input graph, called the 2-hop-cover labeling. To use such approaches in realistic time-evolving scenarios, when the managed graph undergoes topological modifications over time, specific dynamic algorithms, carefully updating the labeling as the graph evolves, have been introduced. In fact, recomputing from scratch the 2-hop-cover structure every time the graph changes is not an option, as it induces unsustainable time overheads. While the state-of-the-art dynamic algorithm to update a 2-hop-cover labeling against incremental modifications (insertions of arcs/vertices, arc weights decreases) offers very fast update times, the only known solution for decremental modifications (deletions of arcs/vertices, arc weights increases) is still far from being considered practical, as it requires up to tens of seconds of processing per update in several prominent classes of real-world inputs, as experimentation shows. In this paper, we introduce a new dynamic algorithm to update 2-hop-cover labelings against decremental changes. We prove its correctness, formally analyze its worst-case performance, and assess its effectiveness through an experimental evaluation employing both real-world and synthetic inputs. Our results show that it improves, by up to several orders of magnitude, upon average update times of the only existing decremental algorithm, thus representing a step forward towards real-time distance mining in general, massive time-evolving graphs. [ABSTRACT FROM AUTHOR]

To realize the application of super-resolution technology from theory to practice, and to improve microsatellite spatial resolution, we propose a special super-resolution algorithm based on the multi-modality super-CMOS sensor which can adapt to the limited operation capacity of microsatellite computers. First, we designed an oblique sampling mode with the sensor rotated at an angle of 26.56 ∘ (arctan 1 2) to obtain high overlap ratio images with sub-pixel displacement. Secondly, the proposed super-resolution algorithm was applied to reconstruct the final high-resolution image. Because the satellite equipped with this sensor is scheduled to be launched this year, we also designed the simulation mode of conventional sampling and the oblique sampling of the sensor to obtain the comparison and experimental data. Lastly, we evaluated the super-resolution quality of images, the effectiveness, the practicality, and the efficiency of the algorithm. The results of the experiments showed that the satellite-using super-resolution algorithm combined with multi-modality super-CMOS sensor oblique-mode sampling can increase the spatial resolution of an image by about 2 times. The algorithm is simple and highly efficient, and can realize the super-resolution reconstruction of two remote-sensing images within 0.713 s, which has good performance on the microsatellite. [ABSTRACT FROM AUTHOR]

The purpose of this special issue of Algorithms was to attract papers presenting original research in the area of algorithm engineering. In particular, submissions concerning the design, analysis, implementation, tuning, and experimental evaluation of discrete algorithms and data structures, and/or addressing methodological issues and standards in algorithmic experimentation were encouraged. Papers dealing with advanced models of computing, including memory hierarchies, cloud architectures, and parallel processing were also welcome. In this regard, we solicited contributions from all most prominent areas of applied algorithmic research, which include but are not limited to graphs, databases, computational geometry, big data, networking, combinatorial aspects of scientific computing, and computational problems in the natural sciences or engineering. [ABSTRACT FROM AUTHOR]

Designing advanced health monitoring systems is still an active research topic. Wearable and remote monitoring devices enable monitoring of physiological and clinical parameters (heart rate, respiration rate, temperature, etc.) and analysis using cloud-centric machine-learning applications and decision-support systems to predict critical clinical states. This paper moves from a totally cloud-centric concept to a more distributed one, by transferring sensor data processing and analysis tasks to the edges of the network. The resulting solution enables the analysis and interpretation of sensor-data traces within the wearable device to provide actionable alerts without any dependence on cloud services. In this paper, we use a supervised-learning approach to detect heartbeats and classify arrhythmias. The system uses a window-based feature definition that is suitable for execution within an asymmetric multicore embedded processor that provides a dedicated core for hardware assisted pattern matching. We evaluate the performance of the system in comparison with various existing approaches, in terms of achieved accuracy in the detection of abnormal events. The results show that the proposed embedded system achieves a high detection rate that in some cases matches the accuracy of the state-of-the-art algorithms executed in standard processors. [ABSTRACT FROM AUTHOR]

From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: plane-sweep, torch, quickhull, and throw-away. With a new set of space-efficient implementations, the experimental results—in the integer-arithmetic setting—are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them. [ABSTRACT FROM AUTHOR]

A new phase of evolution of Machine-to-Machine (M2M) communication has started where vertical Internet of Things (IoT) deployments dedicated to a single application domain gradually change to multi-purpose IoT infrastructures that service different applications across multiple industries. New networking technologies are being deployed operating over sub-GHz frequency bands that enable multi-tenant connectivity over long distances and increase network capacity by enforcing low transmission rates to increase network capacity. Such networking technologies allow cloud-based platforms to be connected with large numbers of IoT devices deployed several kilometres from the edges of the network. Despite the rapid uptake of Long-power Wide-area Networks (LPWANs), it remains unclear how to organize the wireless sensor network in a scaleable and adaptive way. This paper introduces a hierarchical communication scheme that utilizes the new capabilities of Long-Range Wireless Sensor Networking technologies by combining them with broadly used 802.11.4-based low-range low-power technologies. The design of the hierarchical scheme is presented in detail along with the technical details on the implementation in real-world hardware platforms. A platform-agnostic software firmware is produced that is evaluated in real-world large-scale testbeds. The performance of the networking scheme is evaluated through a series of experimental scenarios that generate environments with varying channel quality, failing nodes, and mobile nodes. The performance is evaluated in terms of the overall time required to organize the network and setup a hierarchy, the energy consumption and the overall lifetime of the network, as well as the ability to adapt to channel failures. The experimental analysis indicate that the combination of long-range and short-range networking technologies can lead to scalable solutions that can service concurrently multiple applications. [ABSTRACT FROM AUTHOR]