Search

Shuffling is the process of placing elements into a random order such that any permutation occurs with equal probability. It is an important building block in virtually all scientific areas. We engineer, - to the best of our knowledge - for the first time, a practically fast, parallel shuffling algorithm with O(√n log n) parallel depth that requires only poly-logarithmic auxiliary memory (with high probability). In an empirical evaluation, we compare our implementations with a number of existing solutions on various computer architectures. Our algorithms consistently achieve the highest through-put on all machines. Further, we demonstrate that the runtime of our parallel algorithm is comparable to the time that other algorithms may take to acquire the memory from the operating system to copy the input., LIPIcs, Vol. 265, 21st International Symposium on Experimental Algorithms (SEA 2023), pages 5:1-5:20

Physiological signal based biometric analysis has recently attracted attention as a means of meeting increasing privacy and security requirements. The real-time nature of an electrocardiogram (ECG) and the hidden nature of the information make it highly resistant to attacks. This paper focuses on three major bottlenecks of existing deep learning driven approaches: the lengthy time requirements for optimizing the hyperparameters, the slow and computationally intense identification process, and the unstable and complicated nature of ECG acquisition. We present a novel deep neural network framework for learning human identification feature representations directly from ECG time series. The proposed framework integrates deep bidirectional long short-term memory (BLSTM) and adaptive particle swarm optimization (APSO). The overall approach not only avoids the inefficient and experience-dependent search for hyperparameters, but also fully exploits the spatial information of ordinal local features and the memory characteristics of a recognition algorithm. The effectiveness of the proposed approach is thoroughly evaluated in two ECG datasets, using two protocols, simulating the influence of electrode placement and acquisition sessions in identification. Comparing four recurrent neural network structures and four classical machine learning and deep learning algorithms, we prove the superiority of the proposed algorithm in minimizing overfitting and self-learning of time series. The experimental results demonstrated an average identification rate of 97.71%, 99.41%, and 98.89% in training, validation, and test sets, respectively. Thus, this study proves that the application of APSO and LSTM techniques to biometric human identification can achieve a lower algorithm engineering effort and higher capacity for generalization.

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the allowed editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the allowed editing operations are vertex deletions). Answering an open question from the literature, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, clearly outperforming a standard CPLEX solver in most instances of an established biological test data set.

The confident high-throughput identification of small molecules is one of the most challenging tasks in mass spectrometry-based metabolomics. Annotating the molecular formula of a compound is the first step towards its structural elucidation. Yet even the annotation of molecular formulas remains highly challenging. This is particularly so for large compounds above 500 daltons, and for de novo annotations, for which we consider all chemically feasible formulas. Here we present ZODIAC, a network-based algorithm for the de novo annotation of molecular formulas. Uniquely, it enables fully automated and swift processing of complete experimental runs, providing high-quality, high-confidence molecular formula annotations. This allows us to annotate novel molecular formulas that are absent from even the largest public structure databases. Our method re-ranks molecular formula candidates by considering joint fragments and losses between fragmentation trees. We employ Bayesian statistics and Gibbs sampling. Thorough algorithm engineering ensures fast processing in practice. We evaluate ZODIAC on five datasets, producing results substantially (up to 16.5-fold) better than for several other methods, including SIRIUS, which is the state-of-the-art algorithm for molecular formula annotation at present. Finally, we report and verify several novel molecular formulas annotated by ZODIAC. To infer a previously unknown molecular formula from mass spectrometry data is a challenging, yet neglected problem. Ludwig and colleagues present a network-based approach to ranking possible formulas.

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.

Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.

We study the problem of computing isocontours in static and dynamic road networks, where the objective is to identify the boundary of the region that is reachable from a given source within a certain amount of time (or another limited resource). Although there is a wide range of practical applications for this problem (e.g., urban planning, geomarketing, visualizing the cruising range of a vehicle), there has been little research on fast algorithms for large, realistic inputs, and existing approaches tend to compute more information than necessary. Our contribution is twofold: (1) We propose compact but sufficient definitions of isocontours, based on which (2) we provide several easy-to-parallelize, scalable algorithmic approaches for faster computation. By extensive experimental analysis, we demonstrate that our techniques enable interactive isocontour computation within milliseconds even on continental networks, significantly faster than the state of the art.

Multi-robot systems (MRS) are a reference solution for many prominent real-world applications, e.g. management of warehouses or exploration of unknown environments. One of the most fundamental computational problems in MRS is that of planning the assignment of tasks to robots when such tasks have deadlines, i.e. constraints on when the execution must take place. The problem, when multiple objective functions of interest need to be optimized, is both NP-Hard and hard to approximate, and few heuristics are known in the literature to handle it. Unfortunately, none of them guarantees that the trajectories used by the robots when moving between tasks’ locations are collision-free at planning time. Rather, they implement a reactive behavior, i.e. they abort the execution of a planned task whenever something goes wrong, e.g. trajectories of robots intersect or a deadline is missed due to some obstacle. This approach induces negative effects on the global performance of the system in the form of waste of energy, due to high distances traveled by the fleet members, or in the form of high convergence time to execute tasks. Therefore, planning the assignments of temporally constrained tasks with the guarantee of avoiding collisions can be a desirable feature for multi-robot systems. In this paper, we present CFAT-D (Collision-Free Allocation of Tasks having Deadlines), a new algorithm that can allocate temporally constrained tasks while guaranteeing that used trajectories are collision-free at planning time. We prove CFAT-D to be correct and showcase its effectiveness through an extensive experimental evaluation. Finally, we provide a roadmap toward the practical implementation of the new strategy in real-world environments.

Since its early formulations, the genome assembly problem has attracted lots of interest from algorithm theoretic as well as from algorithm engineering point of view. In this problem, which is an inversion problem by nature, one is asked to reconstruct the entire DNA sequence from the short, randomly picked sequence fragments that a DNA sequencing instrument is able to read. In this study, the De Bruijn graph method will be examined to reconstruct the Genome. And discussed preferred k-mer length for this algorithm in ideal conditions.

In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools., LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 6:1-6:18

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter at most two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the editing operations are vertex deletions). Answering an open question, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then, focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.

Cloud computing, and particularly mobile cloud computing, contains a great deal of uncertainty. User requirements are changeable, and environmental factors, such as network delay and bandwidth availability, as well as changing prices, make efficient allocation of resources challenging. Stochastic optimization is a technique designed to solve optimization problems, such as for resource allocation, in a way that accounts for the uncertainty of future parameters. It is a flexible and powerful technique, and in this thesis I demonstrate three key areas where it can be used with great efficacy. The two key resources in mobile cloud computing are computation and bandwidth. The problem of migrating computation to the cloud through virtual machines (VMs) has been addressed in prior work, as has the problem of routing bandwidth through a network effectively. However, to provision resources in the cloud, these two must be allocated in concert, as they are interdependent. Without sufficient bandwidth, efficient computation will be wasted, and a clear network path is worthless if the destination lacks computing power. Many cloud services (e.g., Amazon) offer a reservation option for VMs that can be used to reduce costs if uncertainty is properly accounted for. Likewise, the recent development of Software Defined Networking (SDN) allows the creation of flexible, multi-tenant networks allowing bandwidth reservation. In this thesis I apply stochastic optimization to the problem of jointly provisioning VMs and bandwidth despite uncertain user demand and price information and show results to demonstrate the importance of joint allocation. Much of research in mobile cloud computing focuses on the problem of energy efficiency in mobile devices. In addition to offloading to the cloud, the rise of the Bring-Your-Own-Device (BYOD) paradigm has inspired research into offloading to local equipment (such as a desktop PC). Users who require low latency or a larger screen may prefer not to offload to the cloud, so I propose a model where users can travel to a location (such as a library) and offload their computation to local equipment. Due to a variety of factors, such as user battery levels, number of users, and application requirements, deterministic methods are inadequate. I apply stochastic optimization to the problem to maximize the number of users able to access equipment. The third major issue in cloud computing is the problem of computer security. Mobile users offloading to the cloud, or to local equipment, require reassurance that their data and communications will be secure. Thus, Security-as-a-Service (SECaaS) has arisen to provide security in the cloud without taxing the user's processing resources. However, no security is perfect, and a successful cyber attack is inevitable. Cyber insurance provides compensation in the event of a successful attack. In this thesis I consider a joint provisioning of cyber insurance and SECaaS using stochastic optimization to reserve security services and purchase insurance policies, allowing for uncertainty in attack probabilities, attack success and pricing. I find that cyber insurance can be used to encourage security investment. This thesis contributes to the field of mobile cloud computing in two major ways. The first is the application of stochastic optimization to three vital and related areas in computation offloading, bandwidth provisioning, and cyber security and insurance. In each case I provide numerical results based on parameters derived from real usage data, such as cluster usage traces, mobile user movements, and honeypot attack data. These numerical results show the effectiveness of stochastic optimization as it accounts for uncertainty in a way that is necessary for a realistic model of cloud computing. Secondly, I provide performance optimizations and sensitivity analyses for each problem area. As some decision variables are integer values, I employ two methods (a scenario tree reduction method and a partial Lagrange multiplier algorithm) to significantly improve the solution runtime and show their effectiveness through analytical and numerical results. I formulate two linear programs to perform the sensitivity analysis, giving precise values for the sensitivity range of parameter values. In summary, in this thesis I focus on the application of stochastic optimization to key areas in mobile cloud computing. Existing research either fails to account for uncertainty, or fails to consider interdependent resources in a suitably rich joint approach. To the best of my knowledge, this is the first work to consider joint VM and bandwidth provisioning under uncertainty, to propose the local equipment offloading model, and to apply multi-stage recourse and real test data and sensitivity analysis to joint SECaaS and cyber insurance provisioning. Thus each contribution introduces novel system models, with solution improvements, analysis, and test data that has not been considered until now. Doctor of Philosophy (SCE)

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

Given a polyline consisting of n segments, we study the problem of selecting k of its segments such that the maximum induced gap length without a selected segment is minimized. This optimization problem has applications in the domains of trajectory visualization (see Fig. 1) and facility location. We design several heuristics and exact algorithms for simple polylines, along with algorithm engineering techniques to achieve good practical running times even for large values of n and k. The fastest exact algorithm is based on dynamic programming and exhibits a running time of \(\mathcal {O}(nk)\) while using space linear in n. Furthermore, we consider incremental problem variants. For the case where a given set of k segments shall be augmented by a single additional segment, we devise an optimal algorithm which runs in \(\mathcal {O}(k + \log n)\) on a suitable polyline representation. If not only a single segment but \(k'\) segments shall be added, we can compute the optimal segment set in time \(\mathcal {O}(nk')\) by modifying the dynamic programming approach for the original problem. Experiments on large sets of real-world trajectories as well as artificial polylines show the trade-offs between quality and running time of the different approaches.

We present a fast and compact index for top- k document retrieval on general string collections, in which given a string pattern, the index returns the k documents where it appears most often. We adapt a linear-space and optimal-time theoretical solution, whose implementation poses various algorithm engineering challenges. Although a naive implementation of the optimal solution is estimated to require around 80 n bytes for a text collection of n symbols, our implementation requires 2.5 n to 3.0 n bytes, text included, and answers queries within microseconds. This outperforms all previous practical indexes by orders of magnitude; the only index using less space is hundreds of times slower. Our index can be built on collections of hundreds of gigabytes and on tokenized text collections.

A compressed suffix tree usually consists of three components: a compressed suffix array, a compressed LCP-array, and a succinct representation of the suffix tree topology. There are parallel algorithms that construct the suffix array and the LCP-array, but none for the third component. In this article, we present parallel algorithms on shared memory architectures that construct the balanced parentheses sequence (BPS), an explicit succinct representation of the suffix tree topology, as well as the enhanced balanced parentheses representation (eBPR), an implicit succinct representation of the suffix tree topology. For both representations, this article presents a sequential construction algorithm (a new one for the BPS), a linear work and O (log n ) time parallel construction algorithm, and a heuristic parallel construction algorithm that works very well in practice. The experimental results show that our methods are well suited for real-world applications.

Phat is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.

Determining travel demand within a region of interest takes a considerable calibration effort, requiring transportation surveys, traffic counts, and empirical trip volumes. However, there is a need for demand calculation without substantial calibration, for example to generate large-scale benchmark data for evaluating transportation algorithms. In this work, we present several approaches for demand calculation that take as input only publicly available data, such as population and POI densities. Our algorithms build upon the recently proposed radiation model, which is inspired by job search models in economics. We show that a straightforward implementation of the radiation model does not scale to continental road networks, taking months even on a modern 16-core server. Therefore, we introduce more scalable implementations, substantially decreasing the running time by five orders of magnitude from months to seconds. An extensive experimental evaluation shows that the output of our algorithms is in accordance with demand data used in production systems. Compared to simple approaches previously used in algorithmic publications to generate benchmark data, our algorithms output demand data of better quality, take less time, and have similar implementation complexity.

The main objective here is to use the time-frequency techniques for the analysis of biomolecular sequences. The mathematical definitions of Cohen's class time-frequency distributions (CTFDs) are firstly reviewed. Some other useful time-frequency distributions (TFDs), such as the Short-time Fourier Transform (STFT), the wavelet transform (WT), the Choi-Williams Distribution (CWVD), the Wigner-Ville Distribution (WVD), the Smoothed Pseudo Wigner-Ville Distribution (SPWVD) and the Reassigned Smoothed Pseudo Wigner-Ville Distribution (RSPWVD), are introduced. Their performance in revealing the information of different types of signals and computational cost are evaluated. Among them the reassigned and smoothed TFDs (RSTFDs), such as the RSPWVD, can achieve a very satisfying compromise between the sharpness and the ‘cleanness’ (noise removal) measures of spectrum. DOCTOR OF PHILOSOPHY (SCE)

Adaptive filters that self-adjust their transfer functions according to optimizing algorithms are powerful adaptive systems with numerous applications in the fields of signal processing, communications, radar, sonar, seismology, navigation systems and biomedical engineering. An adaptive signal processing algorithm, e.g., the least mean squares (LMS) algorithm and the recursive least square (RLS) algorithm, is used to deal with adaptation of adaptive filters. The adaptive algorithms are expected to be computationally simple, numerically robust, fast convergent and low fluctuant. Unfortunately, none of the adaptive algorithms developed so far perfectly fulfils these requirements. The stability and convergence performance of the widely-used adaptive algorithms also haven’t been fully explored. This work aims to deal with performance analysis and enhancements for the adaptive algorithms and their applications. We first develop a new variable step-size adjustment scheme for the LMS algorithm using a quotient form of filtered quadratic output errors. Compared to the existing approaches, the proposed scheme reduces the convergence sensitivity to the power of the measurement noise and improves the steady-state performance and tracking capability for comparable transient behavior, with negligible increase in the computational costs. We then develop variable step-size approaches for the normalized least mean squares (NLMS) algorithm. We derive the optimal step-size which minimizes the mean square deviation at each iteration, and propose four approximated step-sizes according to the correlation properties of the additive noise and the variations of the input excitation. We next analyze the stability and performance of the transform-domain LMS algorithms which preprocess the inputs with a fixed data-independent orthogonal transform such as

Complex engineering design (CED) optimization problems in science and engineering commonly have large design spaces. In such design spaces, typically thousands of exact fitness evaluations are required to locate a near optimal design. Often in photonics, electromagnetic, aerospace, biomedical and microwave circuits detailed design processes, variable-fidelity analysis codes are employed to strike a balance between design cost, time and estimation accuracy. Nevertheless, in analysis and design optimization processes where high-fidelity analysis codes are used, each exact fitness evaluation requiring the simulation of analysis codes may cost hours of supercomputer time. Therefore, the overwhelming part of the total run time in CED optimization is usually taken up by the simulation of analysis codes. This often poses a serious impediment to the practical application of high-fidelity analysis codes and evolutionary algorithms to CED optimization problems. In this dissertation work, the research focus has been placed on the use of multiple surrogate models in standard memetic algorithm (MA) to mitigate the costly CED optimization process. In this thesis, a novel hierarchical surrogate-assisted memetic algorithm (HSAMA) combining both global and local surrogate models for accelerating the optimization process is proposed and described. The performance of the proposed algorithm is analyzed by using a series of commonly used benchmark test functions. Furthermore, the proposed algorithm is also applied to aerodynamic shape design. Numerical results show that the HSAMA algorithm is capable of achieving good designs efficiently under a limited computational budget. Further, the impact of uncertainty introduced by approximation errors, i.e., ‘curse and blessing of uncertainty ’, is illustrated and demonstrated on surrogate-assisted memetic algorithm (SAMA). Inspired by this finding, a novel multi-surrogates assisted memetic i ATTENTION: The Singapore Copyright Act applies to the use of this document. Nanyang Technological University Library

This research is emphasized on the study of low complexity multiuser detection algorithms for code-division multiple-access (CDMA) communications systems. Three efficient detectors are proposed in this thesis. These detectors include the weighted polynomial expansion (WPE) detector, the blind cascaded modular detector and the blind RAKE structure cascaded modular detector. The WPE detector can effectively approximate the decorrelating detector and MMSE detector. The blind cascaded modular detector is proposed to implement the blind minimum output energy (MOE) detector. The detector is relatively simple and has a low complexity compared with conventional blind MOE detectors. The RAKE structure cascaded modular detector has been proposed to handle the signature mismatch problem in DS-CDMA system over multipath fading channel. The detector does not require the knowledge of the fading channel and can achieve good performance with a simple structure compared with other blind receivers that need to estimate the channel information. DOCTOR OF PHILOSOPHY (EEE)

While the performance of many neural network and machine learning schemes has been improved through the automated design of various components of their architectures, the automated improvement of Adaptive Resonance Theory (ART) neural networks remains relatively unexplored. Recent work introduced a genetic programming (GP) approach to improve the performance of the Fuzzy ART neural network employing a hyper-heuristic approach to tailor Fuzzy ART's category choice function to specific problems. The GP method showed promising results. However, GP is not the only tool that can be used for automatic improvement. Among other methods, Nested Monte Carlo Search (NMCS) was recently applied to expression discovery and outperformed traditional evolutionary approaches by finding better solutions in fewer evaluations. This work applies NMCS to the discovery of new Fuzzy ART category choice functions targeted to specific problems with results demonstrating its ability to find better performing Fuzzy ART networks than the GP approach.

We study the problem of minimizing overall trip time for battery electric vehicles in road networks. As battery capacity is limited, stops at charging stations may be inevitable. Careful route planning is crucial, since charging stations are scarce and recharging is time-consuming. We extend the Constrained Shortest Path problem for electric vehicles with realistic models of charging stops, including varying charging power and battery swapping stations. While the resulting problem is NP-hard, we propose a combination of algorithmic techniques to achieve good performance in practice. Extensive experimental evaluation shows that our approach (CHArge) enables computation of optimal solutions on realistic inputs, even of continental scale. Finally, we investigate heuristic variants of CHArge that derive high-quality routes in well below a second on sensible instances., Comment: 43 pages, 12 figure, 6 tables

We investigate the practicality of approximation schemes for optimization problems in planar graphs based on balanced separators. The first polynomial-time approximation schemes (PTASes) for problems in planar graphs were based on balanced separators, wherein graphs are recursively decomposed into small enough pieces in which optimal solutions can be found by brute force or other methods. However, this technique was supplanted by the more modern and (theoretically) more efficient approach of decomposing a planar graph into graphs of bounded treewidth, in which optimal solutions are found by dynamic programming. While the latter approach has been tested experimentally, the former approach has not.

Software tools based on the maximum likelihood method and Bayesian methods are widely used for phylogenetic tree inference. This article surveys recent research on parallelization and performance optimization of state-of-the-art tree inference tools. We outline advances in shared-memory multicore parallelization, optimizations for efficient Graphics Processing Unit (GPU) execution, as well as large-scale distributed-memory parallelization.

Since the initial visions proposed in the SmartDust project fifteen years ago, Wireless Sensor Networks have seen a tremendous development, leading to the realization of the Internet of Things (IoT). Today, there is a large variety of hardware and software to choose from that is easy to set up and use. Even though there is an increasing number of real-world applications that employ large deployments of IoT devices, the wireless nature of communication in combination with the low-end capabilities of the devices raises security and privacy issues that have not been properly addressed. Considering also that sensor node brands are very different in their capabilities, providing a single solution is very challenging.In this paper we adopt Elliptic Curve Cryptography (ECC) as an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources, i.e., speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. We provide a generic implementation of ECC that runs on different host operating systems, such as Contiki, TinyOS, iSenseOS, ScatterWeb and Arduino. Furthermore, it runs on smartphone platforms such as Android and iPhone and also any linux based systems (e.g., raspberryPi). Our implementation does not contain any platform-specific specializations, allowing a single implementation to run natively on heterogeneous networks.We look into the Smart Parking application domain and provide a solution that protects the privacy of the users by totally avoiding the exchange of confidential information. We also show how to protect a user's privacy by adapting the tool of zero knowledge proofs (ZKP) with our ECC implementation. We study the performance of our system in an real-world outdoor IoT testbed and analyze the execution time and network overhead for each available hardware platform. Our code is available as open source software and can be used from developers who wish to achieve certain levels of security and privacy in their applications.

In this paper, a variant of the Genetic Algorithm is used to place sensors optimally on a Large Space Structure for the purpose of modal identification. The selection and reproduction schemes of the Genetic Algorithm are modified and a new operator called forced mutation is introduced. These changes are shown to improve the convergence of the algorithm and to lead to near optimal sensor locations. genetic programming combined with neural networks could be incredibly slow, thus impractical. As with many problems, you have to constrain what you are attempting to create.

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&rsquo, 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.

We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes. We find that even though the worst-case complexity of the best undirected KSP algorithm O(k(m + n log n)) is significantly better than that of the popular and considerably simpler directed KSP algorithm O(kn(m + n log n)), the two algorithms are fairly competitive in terms of their empirical performance on small diameter graphs. Furthermore, we show that a few simple optimisations help to bridge the gap between these KSP algorithms even more. However, on moderate to large diameter graphs, the undirected KSP algorithm is considerably faster than the directed algorithms, both in sequential and parallel settings. In terms of the parallelisation strategy, simply replacing the shortest path subroutine by parallel Δ-stepping algorithm can provide a good speed-up for many KSP algorithms on random graphs. In contrast, for graphs with skewed degree distribution, a more complex strategy of parallelizing the different deviations and then parallelizing the shortest path computation inside the deviations with the remaining threads, provides a better performance.

The study of network representations of physical, biological, and social phenomena can help us better understand their structure and functional dynamics as well as formulate predictive models of these phenomena. However, due to the scarcity of real-world network data owing to factors such as cost and effort required in collection of network data and the sensitivity of this data towards theft and misuse, engineers and researchers often rely on synthetic data for simulations, hypothesis testing, decision making, and algorithm engineering. An important characteristic of infrastructure networks such as roads, water distribution and other utility systems is that they can be (almost fully) embedded in a plane, therefore to simulate these system we need realistic networks which are also planar. While the currently-available synthetic network generators can model networks that exhibit realism, they do not guarantee or achieve planarity. In this paper we present a flexible algorithm that can synthesize realistic networks that are planar. The method follows a multi-scale randomized editing approach generating a hierarchy of coarsened networks of a given planar graph and introducing edits at various levels in the hierarchy. The method preserves the structural properties with minimal bias including the planarity of the network, while introducing realistic variability at multiple scales. Reproducibility: All datasets and algorithm implementation presented in this work are available at https://bit.ly/2CjOUAS

Combinatory Process Synthesis (CPS) is a special case of software synthesis that can be used to manage variability by synthetizing target-specific processes from a repository of components. While conducted CPS research mainly addresses formal aspects of algorithm engineering, no structured methodology is available that enables the broader industrial application. This study addresses this gap and proposes a procedural model for CPS. The presented research bases on the Design Science Research principles. A case study in the healthcare sector shows the successful applicability of the elaborated procedure.

Energy grids are facing various challenges, such as new appliances and volatile generation. As grid reliability and cost benefits are endangered, managing appliances becomes increasingly important. Demand Response (DR) is one possibility to contribute to this task by shifting and managing electrical loads. DR can address multiple objectives. However, current research lacks of algorithms addressing these objectives sufficiently. Thus, we aim to develop a DR algorithm that considers multiple DR objectives. For evaluation, we implemented the algorithm and formulated demonstration cases for a simulation. The evaluated algorithm contributes for example to users and energy providers by realizing various benefits.

Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For $n$-vertex and $m$-edge graphs, the best known algorithms run in $\widetilde{O}(m\sqrt{n})$ time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) new (near-)linear-time data reduction rules for both the unweighted and the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementations for computing matchings in real-world graphs: the average speedup factor is 4.7 in the unweighted case and 12.72 in the weighted case., Comment: An extended abstract of this work appeared at ESA '18. This version has a new coauthor (Tomohiro Koana) and an extended experimental section including comparison against two further implementations for finding matchings. Moreover, it contains further data reduction rules (theoretical and practical findings) for Maximum-Cardinality Matching and improved theoretical bounds on the kernel sizes

Selecting the most appropriate algorithm to use when attempting to solve a black-box continuous optimization problem is a challenging task. Such problems typically lack algebraic expressions, it is not possible to calculate derivative information, and the problem may exhibit uncertainty or noise. In many cases, the input and output variables are analyzed without considering the internal details of the problem. Algorithm selection requires expert knowledge of search algorithm efficacy and skills in algorithm engineering and statistics. Even with the necessary knowledge and skills, success is not guaranteed.In this paper, we present a survey of methods for algorithm selection in the black-box continuous optimization domain. We start the review by presenting Rice's (1976) selection framework. We describe each of the four component spaces - problem, algorithm, performance and characteristic - in terms of requirements for black-box continuous optimization problems. This is followed by an examination of exploratory landscape analysis methods that can be used to effectively extract the problem characteristics. Subsequently, we propose a classification of the landscape analysis methods based on their order, neighborhood structure and computational complexity. We then discuss applications of the algorithm selection framework and the relationship between it and algorithm portfolios, hybrid meta-heuristics, and hyper-heuristics. The paper concludes with the identification of key challenges and proposes future research directions.

Compressed Suffix Arrays (CSAs) offer the same functionality as classical suffix arrays (SAs), and more, within space close to that of the compressed text, and in addition they can reproduce any text fragment. Furthermore, their pattern search times are comparable to those of SAs. This combination has made CSAs extremely successful substitutes for SAs in space-demanding applications. Their weakest point is that they are orders of magnitude slower when retrieving the precise positions of pattern occurrences. SAs have other well-known shortcomings, inherited by CSAs, such as not retrieving those positions in a useful order. In this paper we present new techniques that, on the one hand, improve the current space/time tradeoffs for retrieving pattern occurrences in CSAs, and on the other, efficiently support extended pattern locating functionalities, such as retrieving occurrences in text order or limiting the occurrences to within a text window. Our experimental results display considerable savings with respect to the baseline techniques in many cases of interest: in some cases we outperform their time by a factor of two or three.

We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present a fast preprocessing method for computing multiple good alternatives and apply this result in an online setting. This setting makes our result applicable in legacy systems with negligible memory overhead. An extensive experimental analysis on a continental-sized real- world road network proves the performance of our algorithm and supports the general systematic algorithm engineering approach. We also show how to combine our results with the competing concept of alternative graphs that encode many alternative paths at once.

There are many historical itineraries that describe routes as a list of settlements and the travel distances along the way. They are an important source of information for various kinds of research in the humanities, providing insights into for example the development of human mobility and historical road networks.In this paper, we develop an approach for aligning these itineraries with a modern gazetteer (database of places). We combine textual information (historical toponyms) and spatial information (travel distances) into a Hidden Markov model. Naively calculating a maximum likelihood explanation is slow, but careful algorithm engineering achieves high performance suitable for user interaction.We demonstrate the practical potential of our approach by geo-referencing 48 itineraries (containing 691 stops) from two important historical guidebooks published in 1563 and 1597: our approach is fast and accurate. Additionally, we show how to use sensitivity analysis to power an efficient user interface for quality assurance.

The main goal of this chapter is to present a novel adaptation of the classical simplex algorithm for a data-flow architecture. Due to the recent reemergence of the data-flow paradigm, most of the algorithms need to be reengineered in order to use the features of the new platform. By exploring various possibilities of implementations and by extensive empirical testing we manage to show the suitability of the data-flow paradigm for the simplex algorithm, as well as pinpoint the strengths and some of the weaknesses of the used architecture.

Route planning applications designed for electric vehicles have to consider a number of additional constraints. With the limited range and comparatively long charging times, it is of utmost importance to consider energy consumption in routing applications. However, recently published algorithmic approaches for electric vehicle routing focus solely on specific aspects of this problem, such as optimizing energy consumption as single criterion. In this work, we present first steps towards a holistic framework for computing shortest paths for electric vehicles with limited range. This includes the possibility of driving instructions, such as driving speed adjustments to save energy, realistic modeling of battery charging procedures, and the integration of turn costs.

Complex network analysis is concerned with identifying statistically significant patterns in large and complex networks. A complex network is an abstract model of a complex system; it represents a well-chosen set of entities as nodes and one or more types of relationships between them as edges. Methods from complex network analysis have been used to identify small molecules called miRNAs that are able to stop breast cancer [13], to understand possible privacy breaches [9], or to analyze how humans solve complex problems [10]. As many areas in our globalized world tend to get more interconnected, the methods from complex network analysis became more important: for complex systems with an underlying network structure, the framework of complex network analysis provides the potential to identify central nodes, to describe deviating substructures, and to reveal the interaction between structure and function of complex networks. Based on this potential impact of network analysis on many fields of society, my work concentrates on understanding when to use which kind of network measure to analyze complex networks and where their limits are, a field I call network analysis literacy. This question can easily be generalized to data analysis literacy which can be even more generalized to the influence of our modern IT-systems on the individual, on organizations, and on society at large, which culminates in a new field of study called socioinformatics.

In the past, parallel processing was a specialized approach to high-performance computing. Today, we have to rethink the computational cores of algorithmic and data structures applications. In this article we discuss how this process of rethinking can be understood using algorithm engineering.

In this work, we present the Smart Grid Algorithm Engineering (SGAE) process model for application-oriented research and development in information and communication technology (ICT) for power systems. The SGAE process model is motivated by the main objective of contributing application-oriented research results for distributed control concepts on a sound methodological background. With this process model, we strive for an engineering aspiration within the domain of Smart Grids. The process model is set up with an initial conceptualisation phase followed by an iterable cycle of five phases with both analytical and experimental parts, giving detailed information on inputs and results for each phase and identifying the needed actors for each phase. Simulation of large-scale Smart Grid scenarios is a core component of SGAE. We therefore elaborate on tooling and techniques needed in that context and illustrate the whole process model using an application example from a finished research and development project.

DeepQA is a large-scale natural language processing (NLP) question-and-answer system that responds across a breadth of structured and unstructured data, from hundreds of analytics that are combined with over 50 models, trained through machine learning. After the 2011 historic milestone of defeating the two best human players in the Jeopardy! game show, the technology behind IBM Watson, DeepQA, is undergoing gamification into real-world business problems. Gamifying a business domain for Watson is a composite of functional, content, and training adaptation for nongame play. During domain gamification for medical, financial, government, or any other business, each system change affects the machine-learning process. As opposed to the original Watson Jeopardy!, whose class distribution of positive-to-negative labels is 1:100, in adaptation the computed training instances, question-and-answer pairs transformed into true-false labels, result in a very low positive-to-negative ratio of 1:100 000. Such initial extreme class imbalance during domain gamification poses a big challenge for the Watson machine-learning pipelines. The combination of ingested corpus sets, question-and-answer pairs, configuration settings, and NLP algorithms contribute toward the challenging data state. We propose several data engineering techniques, such as answer key vetting and expansion, source ingestion, oversampling classes, and question set modifications to increase the computed true labels. In addition, algorithm engineering, such as an implementation of the Newton-Raphson logistic regression with a regularization term, relaxes the constraints of class imbalance during training adaptation. We conclude by empirically demonstrating that data and algorithm engineering are complementary and indispensable to overcome the challenges in this first Watson gamification for real-world business problems.

Best connections in real networks are usually found by applying Dijkstra's shortest paths algorithm. Unfortunately, networks deriving from real-world applications are huge, yielding unsustainable times to compute shortest paths. Therefore, considerable research has been conducted in recent years to accelerate Dijkstra's algorithm on typical instances of transportation and communication networks, such as road networks. These efforts have led to the development of many so called speed-up techniques, as for example Arc-Flags. The main drawback of many of these techniques, including Arc-Flags, is that they do not work well in the realistic dynamic scenarios where the networks change over time. In this article, we introduce a new data structure, named Road-Signs, which is used to update the Arc-Flags of a graph in fully dynamic scenarios. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and does not require large space consumption for sparse networks. We develop a fully dynamic algorithm for updating Arc-Flags, by updating Road-Signs, each time that a modification occurs on an edge of the network. We show that this algorithm is better than recomputation from scratch of Arc-Flags in terms of the affected parameters of the input, which makes this solution suitable to be efficient in practice. However, it is not better than recomputation from scratch in the worst case. We also propose an experimental study to evaluate the practical performance of the new dynamic algorithm. To this aim, we use real-world road networks subject to sequences of weight change operations. Our experiments show a significant speed-up in the updating phase with respect to the recomputation from scratch of Arc-Flags.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 633, 243-259 2014

The field of network science is a highly interdisciplinary area, for the empirical analysis of network data, it draws algorithmic methodologies from several research fields. Hence, research procedures and descriptions of the technical results often differ, sometimes widely. In this paper we focus on methodologies for the experimental part of algorithm engineering for network analysis&mdash, an important ingredient for a research area with empirical focus. More precisely, we unify and adapt existing recommendations from different fields and propose universal guidelines&mdash, including statistical analyses&mdash, for the systematic evaluation of network analysis algorithms. This way, the behavior of newly proposed algorithms can be properly assessed and comparisons to existing solutions become meaningful. Moreover, as the main technical contribution, we provide , a highly automated tool to perform and analyze experiments following our guidelines. To illustrate the merits of and our guidelines, we apply them in a case study: we design, perform, visualize and evaluate experiments of a recent algorithm for approximating betweenness centrality, an important problem in network analysis. In summary, both our guidelines and shall modernize and complement previous efforts in experimental algorithmics, they are not only useful for network analysis, but also in related contexts.

Succinct data structures provide the same functionality as their corresponding traditional data structure in compact space. We improve on functions rank and select, which are the basic building blocks of FM-indexes and other succinct data structures. First, we present a cache-optimal, uncompressed bitvector representation that outperforms all existing approaches. Next, we improve, in both space and time, on a recent result by Navarro and Providel on compressed bitvectors. Last, we show techniques to perform rank and select on 64-bit words that are up to three times faster than existing methods. In our experimental evaluation, we first show how our improvements affect cache and runtime performance of both operations on data sets larger than commonly used in the evaluation of succinct data structures. Our experiments show that our improvements to these basic operations significantly improve the runtime performance and compression effectiveness of FM-indexes on small and large data sets. To our knowledge, our improvements result in FM-indexes that are either smaller or faster than all current state of the art implementations. Copyright © 2013 John Wiley & Sons, Ltd.