Skip to main content

About this book

The LNCS journal Transactions on Computational Science reflects recent developments in the field of Computational Science, conceiving the field not as a mere ancillary science but rather as an innovative approach supporting many other scientific disciplines. The journal focuses on original high-quality research in the realm of computational science in parallel and distributed environments, encompassing the facilitating theoretical foundations and the applications of large-scale computations and massive data processing. It addresses researchers and practitioners in areas ranging from aerospace to biochemistry, from electronics to geosciences, from mathematics to software architecture, presenting verifiable computational methods, findings, and solutions, and enabling industrial users to apply techniques of leading-edge, large-scale, high performance computational methods.

This, the 33rd issue of the Transactions on Computational Science, focusses on computational geometry and computability, with applications in IoT (Internet of Things), Bioinformatics, and WBAN (Wireless Body Area Networks). Three of the seven papers constitute extended versions of papers presented at the 18th International Workshop on Computational Geometry and Security Applications, CGSA 2017, held in Trieste, Italy, in June 2017.

Table of Contents


A Delta-Diagram Based Synthesis for Cross Layer Optimization Modeling of IoT

Internet of Things is a networking platform where billions of every day devices communicate intelligently making every day communication highly informative. The IoT defines a world-wide cyber-physical system with a plethora of applications in the fields of demotics, e-health, goods monitoring and logistics, among others. The use of cross-layer communication schemes to provide adaptive solutions for the IoT is motivated by the high heterogeneity in the hardware capabilities and the communication requirements among things. In this article, a novel Delta Diagram synthesis for the IoT is proposed to accurately capture both the high heterogeneity of the IoT and the impact of the Internet as part of the network architecture. Furthermore, a novel modified Grey Wolf Optimizer framework is proposed to obtain optimal routing paths and the communication parameters among things, by exploiting the interrelations among different layer functionalities in the IoT. Moreover, a cross-layer communication protocol is utilized to implement and test this optimization framework in practical scenarios. The results show that the proposed solution can achieve a global communication optimum and outperforms existing layered solutions. The novel Delta-diagram is a preliminary step towards providing efficient and reliable end-to-end communication in the IoT which may be extended to other dimensions of IoT like security and hardware synthesis.
Prathap Siddavaatam, Reza Sedaghat

Design and Analysis of Energy Efficient Wireless Body Area Network (WBAN) for Health Monitoring

Wireless Body Area Network (WBAN) is an upcoming research area of Wireless Sensor Networks. In WBAN, wireless sensors are either implanted within human body or worn over body to examine physiological strictures like blood pressure rate, body temperature, blood glucose level. Main emphasis is laid on making WBAN energy efficient. Network stability and increased throughput are also areas of prime concern for WBAN. Modified SIMPLE (Stable Increased Multi-hop Protocol Link Efficiency) cluster level protocol (M-SIMPLE) has been proposed and implemented. M-SIMPLE is capable of performing single and multi-hop whereas in most of the other existing protocols either of the one is possible. A cost function is required to select a parent node which comprises maximum residual energy and has minimum distance from sink. Optimal number of cluster heads are chosen to increase the efficiency. Improved stability and packet delivery is achieved which further improves the efficiency of the network.
Aakriti Khanna, Vaibhav Chaudhary, Sindhu Hak Gupta

A Revamp Approach for Training of HMM to Accelerate Classification of 16S rRNA Gene Sequences

In the era of Information Technology, the field of Bioinformatics is rapidly growing with research in various related topics. The database of biological information has become much higher than its consumption. Automatic classification of biological information is one of the critical problems in Bioinformatics. Therefore, the critical issue is to regulate and manage the enormous amount of novel information to facilitate access to this useful and valuable biological information. The specific nucleus dilemma in classifying biological information is the annotation of various biological sequences with functional features. Annotation of the significant and rapidly increasing amount of genomic sequence data requires computational tools for classification of genes in DNA sequences. This paper presents a computational method for classification of highly conserved 16S rRNA biological sequences. We took Biological sequence classification as motivation to reveal a methodology that uses Hidden Markov Models (HMMs) to classify them. This paper explains the description of the algorithms used for implementing three phases of HMM (training, decoding, and evaluation) to classify sequences into clusters that have known similar functional properties. In the implementation of the training phase, we have addressed practical issues like initial parameter selection for HMM and computational weakness for the large data set. Later in the paper, we have shown that methodology presents a classification accuracy of 91% for Bacillus and 97% for Clostridia.
Prakash Choudhary, M. P. Kurhekar

: A System for Web Block Classification

Web blocks such as navigation menus, advertisements, headers, and footers are key components of Web pages that define not only the appearance, but also the way humans interact with different parts of the page. For machines, however, classifying and interacting with these blocks is a surprisingly hard task. Yet, Web block classification has varied applications in the fields of wrapper induction, assistance to visually impaired people, Web adaptation, Web page topic clustering, and Web search. Our system for Web block classification, \({{\textsc {ber}}}_{y}{\textsc {l}}\), performs automated classification of Web blocks through a combination of machine learning and declarative, model-driven feature extraction based on Datalog rules. \({{\textsc {ber}}}_{y}{\textsc {l}}\) uses refined feature sets for the classification of individual blocks to achieve accurate classification for all the block types we have observed so far. The high accuracy is achieved through these carefully selected features, some even tuned to the specific block type. At the same time, \({{\textsc {ber}}}_{y}{\textsc {l}}\) avoids a high cost of feature engineering through a model-driven rather than programmatic approach to extracting features. Not only does this reduce the time for feature engineering, the model-driven, declarative approach also allows for semi-automatic optimisation of the feature extraction system. We perform evaluation to validate these claims on a selected range of Web blocks.
Andrey Kravchenko

The Refutation of Amdahl’s Law and Its Variants

Amdahl’s law, imposing a restriction on the speedup achievable by a multiple number of processors, based on the concept of sequential and parallelizable fractions of computations, has been used to justify, among others, asymmetric chip multiprocessor architectures and concerns of “dark silicon”. This paper demonstrates flaws in Amdahl’s law that (i) in theory no inherently sequential fractions of computations exist (ii) sequential fractions appearing in practice are different from parallelizable fractions and usually have different growth rates of time requirements and that (iii) the time requirement of sequential fractions can be proportional to the number of processors. However, mathematical analyses are also provided to demonstrate that sequential fractions have negligible effect on speedup if the growth rate of the time requirement of the parallelizable fraction is higher than that of the sequential fraction. Examples are given that Amdahl’s law and its variants fail to represent limits to parallel computation. In particular, Gustafson’s law, claimed to be a refutation of Amdahl’s law by some authors, is shown to contradict established theoretical results. We can conclude that no simple formula or law governing concurrency exists.
F. Dévai

A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane

In this paper we propose a 1-round algorithm for approximate point placement in the plane in an adversarial model. The distance query graph presented to the adversary is chordal. The remaining distances are determined using a distance matrix completion algorithm for chordal graphs, based on a result by Bakonyi and Johnson [SIAM Journal on Matrix Analysis and Applications 16 (1995)]. The layout of the points is determined from the complete distance matrix in two ways: using the traditional Young-Householder approach as well as a Stochastic Proximity Embedding (SPE) method due to Agrafiotis [Journal of Computational Chemistry 24 (2003)].
Md. Zamilur Rahman, Udayamoorthy Navaneetha Krishnan, Cory Jeane, Asish Mukhopadhyay, Yash P. Aneja

Neighbourhood Graphs and Locally Minimal Triangulations

Neighbourhood (or proximity) graphs, such as nearest neighbour graph, closest pairs, relative neighbourhood graph and k-nearest neighbour graph are useful tools in many tasks inspecting mutual relations, similarity and closeness of objects. Some of neighbourhood graphs are subsets of Delaunay triangulation (DT) and this relation can be used for efficient computation of these graphs. This paper concentrates on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and shows that, although generally these graphs are not LMT subgraphs, in most cases LMT contains all or many edges of these graphs. This fact can also be used for the neighbourhood graphs computation, namely in kinetic problems, because LMT computation is easier.
Ivana Kolingerová, Tomáš Vomáčka, Martin Maňák, Andrej Ferko


Additional information