Next Issue
Volume 12, October
Previous Issue
Volume 12, August
 
 

Algorithms, Volume 12, Issue 9 (September 2019) – 24 articles

Cover Story (view full-size image): The physical movement of multibody systems on an atomistic level, taking place at the femtosecond time scale, is at the core of quantum molecular dynamics simulations. The Los Alamos National Laboratory explores novel approaches for the simulation of such systems which make use of a special type of graph partitioning to efficiently parallelize computations. For this, the density matrix of a physical system is represented as a graph where atomic orbitals become vertices and nonzero interactions become edges (left figure). After partitioning (right figure), the parts correspond to the divisions of the molecule. The tailored graph partitioning scheme ensures that running the molecular dynamics simulations independently on the parts and reassembling all individual solutions incurs no loss of accuracy. View this paper.
  • Issues are regarded as officially published after their release is announced to the table of contents alert mailing list.
  • You may sign up for e-mail alerts to receive table of contents of newly released issues.
  • PDF is the official format for papers published in both, html and pdf forms. To view the papers in pdf format, click on the "PDF Full-text" link, and use the free Adobe Reader to open them.
Order results
Result details
Section
Select all
Export citation of selected articles as:
28 pages, 920 KiB  
Article
Fairness in Algorithmic Decision-Making: Applications in Multi-Winner Voting, Machine Learning, and Recommender Systems
by Yash Raj Shrestha and Yongjie Yang
Algorithms 2019, 12(9), 199; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090199 - 18 Sep 2019
Cited by 21 | Viewed by 6110
Abstract
Algorithmic decision-making has become ubiquitous in our societal and economic lives. With more and more decisions being delegated to algorithms, we have also encountered increasing evidence of ethical issues with respect to biases and lack of fairness pertaining to algorithmic decision-making outcomes. Such [...] Read more.
Algorithmic decision-making has become ubiquitous in our societal and economic lives. With more and more decisions being delegated to algorithms, we have also encountered increasing evidence of ethical issues with respect to biases and lack of fairness pertaining to algorithmic decision-making outcomes. Such outcomes may lead to detrimental consequences to minority groups in terms of gender, ethnicity, and race. As a response, recent research has shifted from design of algorithms that merely pursue purely optimal outcomes with respect to a fixed objective function into ones that also ensure additional fairness properties. In this study, we aim to provide a broad and accessible overview of the recent research endeavor aimed at introducing fairness into algorithms used in automated decision-making in three principle domains, namely, multi-winner voting, machine learning, and recommender systems. Even though these domains have developed separately from each other, they share commonality with respect to decision-making as an application, which requires evaluation of a given set of alternatives that needs to be ranked with respect to a clearly defined objective function. More specifically, these relate to tasks such as (1) collectively selecting a fixed number of winner (or potentially high valued) alternatives from a given initial set of alternatives; (2) clustering a given set of alternatives into disjoint groups based on various similarity measures; or (3) finding a consensus ranking of entire or a subset of given alternatives. To this end, we illustrate a multitude of fairness properties studied in these three streams of literature, discuss their commonalities and interrelationships, synthesize what we know so far, and provide a useful perspective for future research. Full article
15 pages, 842 KiB  
Article
Correspondence between Multilevel Graph Partitions and Tree Decompositions
by Michael Hamann and Ben Strasser
Algorithms 2019, 12(9), 198; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090198 - 17 Sep 2019
Cited by 1 | Viewed by 3818
Abstract
We present a mapping between rooted tree decompositions and node separator based multilevel graph partitions. Significant research into both tree decompositions and graph partitions exists. We hope that our result allows for an easier knowledge transfer between the two research avenues. Full article
(This article belongs to the Special Issue Graph Partitioning: Theory, Engineering, and Applications)
Show Figures

Figure 1

26 pages, 1370 KiB  
Article
Compression Challenges in Large Scale Partial Differential Equation Solvers
by Sebastian Götschel and Martin Weiser
Algorithms 2019, 12(9), 197; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090197 - 17 Sep 2019
Cited by 4 | Viewed by 4201
Abstract
Solvers for partial differential equations (PDEs) are one of the cornerstones of computational science. For large problems, they involve huge amounts of data that need to be stored and transmitted on all levels of the memory hierarchy. Often, bandwidth is the limiting factor [...] Read more.
Solvers for partial differential equations (PDEs) are one of the cornerstones of computational science. For large problems, they involve huge amounts of data that need to be stored and transmitted on all levels of the memory hierarchy. Often, bandwidth is the limiting factor due to the relatively small arithmetic intensity, and increasingly due to the growing disparity between computing power and bandwidth. Consequently, data compression techniques have been investigated and tailored towards the specific requirements of PDE solvers over the recent decades. This paper surveys data compression challenges and discusses examples of corresponding solution approaches for PDE problems, covering all levels of the memory hierarchy from mass storage up to the main memory. We illustrate concepts for particular methods, with examples, and give references to alternatives. Full article
(This article belongs to the Special Issue Data Compression Algorithms and their Applications)
Show Figures

Figure 1

20 pages, 355 KiB  
Article
Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
by Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl and Dorothea Wagner
Algorithms 2019, 12(9), 196; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090196 - 16 Sep 2019
Cited by 14 | Viewed by 4001
Abstract
Graph partitioning has many applications. We consider the acceleration of shortest path queries in road networks using Customizable Contraction Hierarchies (CCH). It is based on computing a nested dissection order by recursively dividing the road network into parts. Recently, with FlowCutter and Inertial [...] Read more.
Graph partitioning has many applications. We consider the acceleration of shortest path queries in road networks using Customizable Contraction Hierarchies (CCH). It is based on computing a nested dissection order by recursively dividing the road network into parts. Recently, with FlowCutter and Inertial Flow, two flow-based graph bipartitioning algorithms have been proposed for road networks. While FlowCutter achieves high-quality results and thus fast query times, it is rather slow. Inertial Flow is particularly fast due to the use of geographical information while still achieving decent query times. We combine the techniques of both algorithms to achieve more than six times faster preprocessing times than FlowCutter and even faster queries on the Europe road network. We show that, using 16 cores of a shared-memory machine, this preprocessing needs four minutes. Full article
(This article belongs to the Special Issue Graph Partitioning: Theory, Engineering, and Applications)
Show Figures

Figure 1

9 pages, 2294 KiB  
Article
An Intelligent Artificial Neural Network Modeling of a Magnetorheological Elastomer Isolator
by Shiping Zhao, Yong Ma and Dingxin Leng
Algorithms 2019, 12(9), 195; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090195 - 16 Sep 2019
Cited by 4 | Viewed by 2514
Abstract
Recently, magnetorheological elastomer (MRE) has been paid increasingly attention for vibration mitigation devices with the benefits of low power cost, fail safe performances, and fast responses. To make full use of the striking advantages of MRE device, a highly precise model should be [...] Read more.
Recently, magnetorheological elastomer (MRE) has been paid increasingly attention for vibration mitigation devices with the benefits of low power cost, fail safe performances, and fast responses. To make full use of the striking advantages of MRE device, a highly precise model should be developed to predict its dynamic performances. In the work, an MRE isolator in shear–squeeze mixed mode is developed and tested under dynamic loadings. The nonlinear performances in various displacement amplitude and currents are shown. An artificial neural network model with a back-propagation algorithm is proposed to characterize the nonlinear hysteresis of MRE isolator for its implementation in vibration control applications. This model utilized the displacement, velocity, and applied current as inputs and output force as output. The results show that the proposed model has high modeling accuracy and can well portray the complicated behaviors of MRE isolator with different excitations, which shows a fundamental basis for structural vibration control. Full article
Show Figures

Figure 1

24 pages, 4163 KiB  
Article
Unsteady State Lightweight Iris Certification Based on Multi-Algorithm Parallel Integration
by Liu Shuai, Liu Yuanning, Zhu Xiaodong, Zhang Kuo, Ding Tong, Li Xinlong and Wang Chaoqun
Algorithms 2019, 12(9), 194; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090194 - 12 Sep 2019
Cited by 6 | Viewed by 2845
Abstract
Aimed at the one-to-one certification problem of unsteady state iris at different shooting times, a multi-algorithm parallel integration general model structure is proposed in this paper. The iris in the lightweight constrained state affected by defocusing, deflection, and illumination is taken as the [...] Read more.
Aimed at the one-to-one certification problem of unsteady state iris at different shooting times, a multi-algorithm parallel integration general model structure is proposed in this paper. The iris in the lightweight constrained state affected by defocusing, deflection, and illumination is taken as the research object, the existing algorithms are combined into the model structure effectively, and a one-to-one certification algorithm for lightweight constrained state unsteady iris was designed based on multi-algorithm integration and maximum trusted decision. In this algorithm, a sufficient number of iris internal feature points from the unstable state texture were extracted as effective iris information through the image processing layer composed of various filtering processing algorithms, thereby eliminating defocused interference. In the feature recognition layer, iris deflection interference was excluded by the improved methods of Gabor and Hamming and Haar and BP for the stable features extracted by the image processing layer, and two certification results were obtained by means of parallel recognition. The correct number of certifications for an algorithm under a certain lighting condition were counted. The method with the most correct number was set as the maximum trusted method under this lighting condition, and the results of the maximum trusted method were taken as the final decision, thereby eliminating the effect of illumination. Experiments using the JLU and CASIA iris libraries under the prerequisites in this paper show that the correct recognition rate of the algorithm can reach a high level of 98% or more, indicating that the algorithm can effectively improve the accuracy of the one-to-one certification of lightweight constrained state unsteady iris. Compared with the latest architecture algorithms, such as CNN and deep learning, the proposed algorithm is more suitable for the prerequisites presented in this paper, which has good environmental inclusiveness and can better improve existing traditional algorithms’ effectiveness through the design of a parallel integration model structure. Full article
Show Figures

Figure 1

23 pages, 18770 KiB  
Article
Combining Satellite Images and Cadastral Information for Outdoor Autonomous Mapping and Navigation: A Proof-of-Concept Study in Citric Groves
by Joaquín Torres-Sospedra and Patricio Nebot
Algorithms 2019, 12(9), 193; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090193 - 11 Sep 2019
Cited by 1 | Viewed by 2695
Abstract
The development of robotic applications for agricultural environments has several problems which are not present in the robotic systems used for indoor environments. Some of these problems can be solved with an efficient navigation system. In this paper, a new system is introduced [...] Read more.
The development of robotic applications for agricultural environments has several problems which are not present in the robotic systems used for indoor environments. Some of these problems can be solved with an efficient navigation system. In this paper, a new system is introduced to improve the navigation tasks for those robots which operate in agricultural environments. Concretely, the paper focuses on the problem related to the autonomous mapping of agricultural parcels (i.e., an orange grove). The map created by the system will be used to help the robots navigate into the parcel to perform maintenance tasks such as weed removal, harvest, or pest inspection. The proposed system connects to a satellite positioning service to obtain the real coordinates where the robotic system is placed. With these coordinates, the parcel information is downloaded from an online map service in order to autonomously obtain a map of the parcel in a readable format for the robot. Finally, path planning is performed by means of Fast Marching techniques using the robot or a team of two robots. This paper introduces the proof-of-concept and describes all the necessary steps and algorithms to obtain the path planning just from the initial coordinates of the robot. Full article
Show Figures

Figure 1

30 pages, 1194 KiB  
Article
Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
by Syed Aizaz Ali Shah, Maximilian Stark and Gerhard Bauch
Algorithms 2019, 12(9), 192; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090192 - 10 Sep 2019
Cited by 12 | Viewed by 4274
Abstract
The information bottleneck method is a generic clustering framework from the field of machine learning which allows compressing an observed quantity while retaining as much of the mutual information it shares with the quantity of primary relevance as possible. The framework was recently [...] Read more.
The information bottleneck method is a generic clustering framework from the field of machine learning which allows compressing an observed quantity while retaining as much of the mutual information it shares with the quantity of primary relevance as possible. The framework was recently used to design message-passing decoders for low-density parity-check codes in which all the arithmetic operations on log-likelihood ratios are replaced by table lookups of unsigned integers. This paper presents, in detail, the application of the information bottleneck method to polar codes, where the framework is used to compress the virtual bit channels defined in the code structure and show that the benefits are twofold. On the one hand, the compression restricts the output alphabet of the bit channels to a manageable size. This facilitates computing the capacities of the bit channels in order to identify the ones with larger capacities. On the other hand, the intermediate steps of the compression process can be used to replace the log-likelihood ratio computations in the decoder with table lookups of unsigned integers. Hence, a single procedure produces a polar encoder as well as its tailored, quantized decoder. Moreover, we also use a technique called message alignment to reduce the space complexity of the quantized decoder obtained using the information bottleneck framework. Full article
(This article belongs to the Special Issue Coding Theory and Its Application)
Show Figures

Figure 1

20 pages, 877 KiB  
Article
Feedback-Based Integration of the Whole Process of Data Anonymization in a Graphical Interface
by Bernhard Meindl and Matthias Templ
Algorithms 2019, 12(9), 191; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090191 - 10 Sep 2019
Cited by 2 | Viewed by 4538
Abstract
The interactive, web-based point-and-click application presented in this article, allows anonymizing data without any knowledge in a programming language. Anonymization in data mining, but creating safe, anonymized data is by no means a trivial task. Both the methodological issues as well as know-how [...] Read more.
The interactive, web-based point-and-click application presented in this article, allows anonymizing data without any knowledge in a programming language. Anonymization in data mining, but creating safe, anonymized data is by no means a trivial task. Both the methodological issues as well as know-how from subject matter specialists should be taken into account when anonymizing data. Even though specialized software such as sdcMicro exists, it is often difficult for nonexperts in a particular software and without programming skills to actually anonymize datasets without an appropriate app. The presented app is not restricted to apply disclosure limitation techniques but rather facilitates the entire anonymization process. This interface allows uploading data to the system, modifying them and to create an object defining the disclosure scenario. Once such a statistical disclosure control (SDC) problem has been defined, users can apply anonymization techniques to this object and get instant feedback on the impact on risk and data utility after SDC methods have been applied. Additional features, such as an Undo Button, the possibility to export the anonymized dataset or the required code for reproducibility reasons, as well its interactive features, make it convenient both for experts and nonexperts in R—the free software environment for statistical computing and graphics—to protect a dataset using this app. Full article
(This article belongs to the Special Issue Statistical Disclosure Control for Microdata)
Show Figures

Figure 1

16 pages, 904 KiB  
Article
Parallelism Strategies for Big Data Delayed Transfer Entropy Evaluation
by Jonas R. Dourado, Jordão Natal de Oliveira Júnior and Carlos D. Maciel
Algorithms 2019, 12(9), 190; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090190 - 09 Sep 2019
Cited by 5 | Viewed by 3130
Abstract
Generated and collected data have been rising with the popularization of technologies such as Internet of Things, social media, and smartphone, leading big data term creation. One class of big data hidden information is causality. Among the tools to infer causal relationships, there [...] Read more.
Generated and collected data have been rising with the popularization of technologies such as Internet of Things, social media, and smartphone, leading big data term creation. One class of big data hidden information is causality. Among the tools to infer causal relationships, there is Delay Transfer Entropy (DTE); however, it has a high demanding processing power. Many approaches were proposed to overcome DTE performance issues such as GPU and FPGA implementations. Our study compared different parallel strategies to calculate DTE from big data series using a heterogeneous Beowulf cluster. Task Parallelism was significantly faster in comparison to Data Parallelism. With big data trend in sight, these results may enable bigger datasets analysis or better statistical evidence. Full article
(This article belongs to the Special Issue Algorithms for Large Scale Data Analysis)
Show Figures

Figure 1

16 pages, 380 KiB  
Article
Parameterised Enumeration for Modification Problems
by Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive and Heribert Vollmer
Algorithms 2019, 12(9), 189; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090189 - 09 Sep 2019
Cited by 9 | Viewed by 2902
Abstract
Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how [...] Read more.
Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size. Full article
(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)
Show Figures

Figure 1

28 pages, 412 KiB  
Article
A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
by Ronald de Haan and Stefan Szeider
Algorithms 2019, 12(9), 188; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090188 - 09 Sep 2019
Cited by 4 | Viewed by 3332
Abstract
We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or [...] Read more.
We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. Full article
(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)
Show Figures

Figure 1

19 pages, 11617 KiB  
Article
Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
by Hristo N. Djidjev, Georg Hahn, Susan M. Mniszewski, Christian F. A. Negre and Anders M. N. Niklasson
Algorithms 2019, 12(9), 187; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090187 - 07 Sep 2019
Cited by 7 | Viewed by 3130
Abstract
The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have [...] Read more.
The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero–nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime. Full article
(This article belongs to the Special Issue Graph Partitioning: Theory, Engineering, and Applications)
Show Figures

Figure 1

20 pages, 14320 KiB  
Article
Semi-Supervised Manifold Alignment Using Parallel Deep Autoencoders
by Fayeem Aziz, Aaron S. W. Wong and Stephan Chalup
Algorithms 2019, 12(9), 186; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090186 - 06 Sep 2019
Cited by 3 | Viewed by 4436
Abstract
The aim of manifold learning is to extract low-dimensional manifolds from high-dimensional data. Manifold alignment is a variant of manifold learning that uses two or more datasets that are assumed to represent different high-dimensional representations of the same underlying manifold. Manifold alignment can [...] Read more.
The aim of manifold learning is to extract low-dimensional manifolds from high-dimensional data. Manifold alignment is a variant of manifold learning that uses two or more datasets that are assumed to represent different high-dimensional representations of the same underlying manifold. Manifold alignment can be successful in detecting latent manifolds in cases where one version of the data alone is not sufficient to extract and establish a stable low-dimensional representation. The present study proposes a parallel deep autoencoder neural network architecture for manifold alignment and conducts a series of experiments using a protein-folding benchmark dataset and a suite of new datasets generated by simulating double-pendulum dynamics with underlying manifolds of dimensions 2, 3 and 4. The dimensionality and topological complexity of these latent manifolds are above those occurring in most previous studies. Our experimental results demonstrate that the parallel deep autoencoder performs in most cases better than the tested traditional methods of semi-supervised manifold alignment. We also show that the parallel deep autoencoder can process datasets of different input domains by aligning the manifolds extracted from kinematics parameters with those obtained from corresponding image data. Full article
Show Figures

Figure 1

16 pages, 411 KiB  
Article
Consensus Tracking by Iterative Learning Control for Linear Heterogeneous Multiagent Systems Based on Fractional-Power Error Signals
by Yu-Juan Luo, Cheng-Lin Liu and Guang-Ye Liu
Algorithms 2019, 12(9), 185; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090185 - 05 Sep 2019
Cited by 3 | Viewed by 2288
Abstract
This paper deals with the consensus tracking problem of heterogeneous linear multiagent systems under the repeatable operation environment, and adopts a proportional differential (PD)-type iterative learning control (ILC) algorithm based on the fractional-power tracking error. According to graph theory and operator theory, convergence [...] Read more.
This paper deals with the consensus tracking problem of heterogeneous linear multiagent systems under the repeatable operation environment, and adopts a proportional differential (PD)-type iterative learning control (ILC) algorithm based on the fractional-power tracking error. According to graph theory and operator theory, convergence condition is obtained for the systems under the interconnection topology that contains a spanning tree rooted at the reference trajectory named as the leader. Our algorithm based on fractional-power tracking error achieves a faster convergence rate than the usual PD-type ILC algorithm based on the integer-order tracking error. Simulation examples illustrate the correctness of our proposed algorithm. Full article
Show Figures

Figure 1

17 pages, 2175 KiB  
Article
Fault Diagnosis of Rolling Bearing Using Multiscale Amplitude-Aware Permutation Entropy and Random Forest
by Yinsheng Chen, Tinghao Zhang, Wenjie Zhao, Zhongming Luo and Kun Sun
Algorithms 2019, 12(9), 184; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090184 - 04 Sep 2019
Cited by 22 | Viewed by 3296
Abstract
A rolling bearing is an important connecting part between rotating machines. It is susceptible to mechanical stress and wear, which affect the running state of bearings. In order to effectively identify the fault types and analyze the fault severity of rolling bearings, a [...] Read more.
A rolling bearing is an important connecting part between rotating machines. It is susceptible to mechanical stress and wear, which affect the running state of bearings. In order to effectively identify the fault types and analyze the fault severity of rolling bearings, a rolling bearing fault diagnosis method based on multiscale amplitude-aware permutation entropy (MAAPE) and random forest is proposed in this paper. The vibration signals of rolling bearings to be analyzed are decomposed into different coarse-grained time series by using the coarse-graining procedure in multiscale entropy, highlighting the fault dynamic characteristics of vibration signals at different scales. The fault features contained in the coarse-grained time series at different time scales are extracted by using amplitude-aware permutation entropy’s sensitive characteristics to signal amplitude and frequency changes to form fault feature vectors. The fault feature vector set is used to establish the random forest multi-classifier, and the fault type identification and fault severity analysis of rolling bearings is realized through random forest. In order to demonstrate the feasibility and effectiveness of the proposed method, experiments were fully conducted in this paper. The experimental results show that multiscale amplitude-aware permutation entropy can effectively extract fault features of rolling bearings from vibration signals, and the extracted feature vectors have high separability. Compared with other rolling bearing fault diagnosis methods, the proposed method not only has higher fault type identification accuracy, but also can analyze the fault severity of rolling bearings to some extent. The identification accuracy of four fault types is up to 96.0% and the fault recognition accuracy under different fault severity reached 92.8%. Full article
(This article belongs to the Special Issue Algorithms for Fault Detection and Diagnosis)
Show Figures

Figure 1

17 pages, 5197 KiB  
Article
An Intelligent Warning Method for Diagnosing Underwater Structural Damage
by Kexin Li, Jun Wang and Dawei Qi
Algorithms 2019, 12(9), 183; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090183 - 30 Aug 2019
Cited by 3 | Viewed by 3128
Abstract
A number of intelligent warning techniques have been implemented for detecting underwater infrastructure diagnosis to partially replace human-conducted on-site inspections. However, the extensively varying real-world situation (e.g., the adverse environmental conditions, the limited sample space, and the complex defect types) can lead to [...] Read more.
A number of intelligent warning techniques have been implemented for detecting underwater infrastructure diagnosis to partially replace human-conducted on-site inspections. However, the extensively varying real-world situation (e.g., the adverse environmental conditions, the limited sample space, and the complex defect types) can lead to challenges to the wide adoption of intelligent warning techniques. To overcome these challenges, this paper proposed an intelligent algorithm combing gray level co-occurrence matrix (GLCM) with self-organization map (SOM) for accurate diagnosis of the underwater structural damage. In order to optimize the generative criterion for GLCM construction, a triangle algorithm was proposed based on orthogonal experiments. The constructed GLCM were utilized to evaluate the texture features of the regions of interest (ROI) of micro-injury images of underwater structures and extracted damage image texture characteristic parameters. The digital feature screening (DFS) method was used to obtain the most relevant features as the input for the SOM network. According to the unique topology information of the SOM network, the classification result, recognition efficiency, parameters, such as the network layer number, hidden layer node, and learning step, were optimized. The robustness and adaptability of the proposed approach were tested on underwater structure images through the DFS method. The results showed that the proposed method revealed quite better performances and can diagnose structure damage in underwater realistic situations. Full article
(This article belongs to the Special Issue Algorithms for Fault Detection and Diagnosis)
Show Figures

Figure 1

32 pages, 1908 KiB  
Article
A Novel Hybrid Genetic-Whale Optimization Model for Ontology Learning from Arabic Text
by Rania M. Ghoniem, Nawal Alhelwa and Khaled Shaalan
Algorithms 2019, 12(9), 182; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090182 - 29 Aug 2019
Cited by 9 | Viewed by 3931
Abstract
Ontologies are used to model knowledge in several domains of interest, such as the biomedical domain. Conceptualization is the basic task for ontology building. Concepts are identified, and then they are linked through their semantic relationships. Recently, ontologies have constituted a crucial part [...] Read more.
Ontologies are used to model knowledge in several domains of interest, such as the biomedical domain. Conceptualization is the basic task for ontology building. Concepts are identified, and then they are linked through their semantic relationships. Recently, ontologies have constituted a crucial part of modern semantic webs because they can convert a web of documents into a web of things. Although ontology learning generally occupies a large space in computer science, Arabic ontology learning, in particular, is underdeveloped due to the Arabic language’s nature as well as the profundity required in this domain. The previously published research on Arabic ontology learning from text falls into three categories: developing manually hand-crafted rules, using ordinary supervised/unsupervised machine learning algorithms, or a hybrid of these two approaches. The model proposed in this work contributes to Arabic ontology learning in two ways. First, a text mining algorithm is proposed for extracting concepts and their semantic relations from text documents. The algorithm calculates the concept frequency weights using the term frequency weights. Then, it calculates the weights of concept similarity using the information of the ontology structure, involving (1) the concept’s path distance, (2) the concept’s distribution layer, and (3) the mutual parent concept’s distribution layer. Then, feature mapping is performed by assigning the concepts’ similarities to the concept features. Second, a hybrid genetic-whale optimization algorithm was proposed to optimize ontology learning from Arabic text. The operator of the G-WOA is a hybrid operator integrating GA’s mutation, crossover, and selection processes with the WOA’s processes (encircling prey, attacking of bubble-net, and searching for prey) to fulfill the balance between both exploitation and exploration, and to find the solutions that exhibit the highest fitness. For evaluating the performance of the ontology learning approach, extensive comparisons are conducted using different Arabic corpora and bio-inspired optimization algorithms. Furthermore, two publicly available non-Arabic corpora are used to compare the efficiency of the proposed approach with those of other languages. The results reveal that the proposed genetic-whale optimization algorithm outperforms the other compared algorithms across all the Arabic corpora in terms of precision, recall, and F-score measures. Moreover, the proposed approach outperforms the state-of-the-art methods of ontology learning from Arabic and non-Arabic texts in terms of these three measures. Full article
Show Figures

Figure 1

15 pages, 359 KiB  
Article
A FEAST Algorithm for the Linear Response Eigenvalue Problem
by Zhongming Teng and Linzhang Lu
Algorithms 2019, 12(9), 181; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090181 - 29 Aug 2019
Cited by 2 | Viewed by 3193
Abstract
In the linear response eigenvalue problem arising from quantum chemistry and physics, one needs to compute several positive eigenvalues together with the corresponding eigenvectors. For such a task, in this paper, we present a FEAST algorithm based on complex contour integration for the [...] Read more.
In the linear response eigenvalue problem arising from quantum chemistry and physics, one needs to compute several positive eigenvalues together with the corresponding eigenvectors. For such a task, in this paper, we present a FEAST algorithm based on complex contour integration for the linear response eigenvalue problem. By simply dividing the spectrum into a collection of disjoint regions, the algorithm is able to parallelize the process of solving the linear response eigenvalue problem. The associated convergence results are established to reveal the accuracy of the approximated eigenspace. Numerical examples are presented to demonstrate the effectiveness of our proposed algorithm. Full article
Show Figures

Figure 1

16 pages, 1875 KiB  
Article
Nearest Embedded and Embedding Self-Nested Trees
by Romain Azaïs
Algorithms 2019, 12(9), 180; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090180 - 29 Aug 2019
Cited by 2 | Viewed by 2968
Abstract
Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in [...] Read more.
Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in 2010. The procedure consists of computing a self-nested approximation, called the nearest embedding self-nested tree, that both embeds the plant and is the closest to it. In this paper, we propose a new algorithm that computes the nearest embedding self-nested tree with a smaller overall complexity, but also the nearest embedded self-nested tree. We show from simulations that the latter is mostly the closest to the initial data, which suggests that this better approximation should be used as a privileged measure of the degree of self-similarity of plants. Full article
(This article belongs to the Special Issue Data Compression Algorithms and their Applications)
Show Figures

Figure 1

16 pages, 3702 KiB  
Article
A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
by Zongyang Li, Yefei Wang and Le Wang
Algorithms 2019, 12(9), 179; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090179 - 26 Aug 2019
Cited by 1 | Viewed by 3233
Abstract
A fast particle-locating method is proposed for the hybrid Euler–Lagrangian models on the arbitrary polyhedral mesh, which is of essential importance to improve the computational efficiency by searching the host cells for the tracked particles very efficiently. A background grid, i.e., a uniform [...] Read more.
A fast particle-locating method is proposed for the hybrid Euler–Lagrangian models on the arbitrary polyhedral mesh, which is of essential importance to improve the computational efficiency by searching the host cells for the tracked particles very efficiently. A background grid, i.e., a uniform Cartesian grid with a grid spacing much smaller than computational mesh, is constructed over the whole computational domain. The many-to-many mapping relation between the computational mesh and the background grid is then specified through a recursive tetrahedron neighbor searching procedure, after the tetrahedral decomposition of computational cells and a mapping inverse operation. Finally, the host cell is straightforwardly identified by the point-in-cell test among the optional elements determined based on the mapping relation. The proposed method is checked on three meshes with different types of the cells and compared with the existing methods in the literatures. The results reveal that the present method is highly efficient and easy to implement on the arbitrary polyhedral mesh. Full article
Show Figures

Figure 1

13 pages, 279 KiB  
Article
Adaptive-Size Dictionary Learning Using Information Theoretic Criteria
by Bogdan Dumitrescu and Ciprian Doru Giurcăneanu
Algorithms 2019, 12(9), 178; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090178 - 25 Aug 2019
Cited by 5 | Viewed by 3315
Abstract
Finding the size of the dictionary is an open issue in dictionary learning (DL). We propose an algorithm that adapts the size during the learning process by using Information Theoretic Criteria (ITC) specialized to the DL problem. The algorithm is built on top [...] Read more.
Finding the size of the dictionary is an open issue in dictionary learning (DL). We propose an algorithm that adapts the size during the learning process by using Information Theoretic Criteria (ITC) specialized to the DL problem. The algorithm is built on top of Approximate K-SVD (AK-SVD) and periodically removes the less used atoms or adds new random atoms, based on ITC evaluations for a small number of candidate sub-dictionaries. Numerical experiments on synthetic data show that our algorithm not only finds the true size with very good accuracy, but is also able to improve the representation error in comparison with AK-SVD knowing the true size. Full article
(This article belongs to the Special Issue Dictionary Learning Algorithms and Applications)
Show Figures

Figure 1

15 pages, 397 KiB  
Article
Simple K-Medoids Partitioning Algorithm for Mixed Variable Data
by Weksi Budiaji and Friedrich Leisch
Algorithms 2019, 12(9), 177; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090177 - 24 Aug 2019
Cited by 33 | Viewed by 5373
Abstract
A simple and fast k-medoids algorithm that updates medoids by minimizing the total distance within clusters has been developed. Although it is simple and fast, as its name suggests, it nonetheless has neglected local optima and empty clusters that may arise. With the [...] Read more.
A simple and fast k-medoids algorithm that updates medoids by minimizing the total distance within clusters has been developed. Although it is simple and fast, as its name suggests, it nonetheless has neglected local optima and empty clusters that may arise. With the distance as an input to the algorithm, a generalized distance function is developed to increase the variation of the distances, especially for a mixed variable dataset. The variation of the distances is a crucial part of a partitioning algorithm due to different distances producing different outcomes. The experimental results of the simple k-medoids algorithm produce consistently good performances in various settings of mixed variable data. It also has a high cluster accuracy compared to other distance-based partitioning algorithms for mixed variable data. Full article
(This article belongs to the Special Issue Clustering Algorithms and Their Applications)
Show Figures

Figure 1

17 pages, 2432 KiB  
Article
Online EEG Seizure Detection and Localization
by Amirsalar Mansouri, Sanjay P. Singh and Khalid Sayood
Algorithms 2019, 12(9), 176; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090176 - 23 Aug 2019
Cited by 13 | Viewed by 5006
Abstract
Epilepsy is one of the three most prevalent neurological disorders. A significant proportion of patients suffering from epilepsy can be effectively treated if their seizures are detected in a timely manner. However, detection of most seizures requires the attention of trained neurologists—a scarce [...] Read more.
Epilepsy is one of the three most prevalent neurological disorders. A significant proportion of patients suffering from epilepsy can be effectively treated if their seizures are detected in a timely manner. However, detection of most seizures requires the attention of trained neurologists—a scarce resource. Therefore, there is a need for an automatic seizure detection capability. A tunable non-patient-specific, non-seizure-specific method is proposed to detect the presence and locality of a seizure using electroencephalography (EEG) signals. This multifaceted computational approach is based on a network model of the brain and a distance metric based on the spectral profiles of EEG signals. This computationally time-efficient and cost-effective automated epileptic seizure detection algorithm has a median latency of 8 s, a median sensitivity of 83%, and a median false alarm rate of 2.9%. Hence, it is capable of being used in portable EEG devices to aid in the process of detecting and monitoring epileptic patients. Full article
Show Figures

Figure 1

Previous Issue
Next Issue
Back to TopTop