EvoMiner: frequent subtree mining in phylogenetic databases

The problem of mining collections of trees to identify common patterns, called frequent subtrees (FSTs), arises often when trying to interpret the results of phylogenetic analysis. FST mining generalizes the well-known maximum agreement subtree problem. Here we present EvoMiner, a new algorithm for mining frequent subtrees in collections of phylogenetic trees. EvoMiner is an Apriori-like levelwise method, which uses a novel phylogeny-specific constant-time candidate generation scheme, an efficient fingerprinting-based technique for downward closure, and a lowest-common-ancestor-based support counting step that requires neither costly subtree operations nor database traversal. Our algorithm achieves speedups of up to 100 times or more over Phylominer, the current state-of-the-art algorithm for mining phylogenetic trees. EvoMiner can also work in depth-first enumeration mode to use less memory at the expense of speed. We demonstrate the utility of FST mining as a way to extract meaningful phylogenetic information from collections of trees when compared to maximum agreement subtrees and majority-rule trees—two commonly used approaches in phylogenetic analysis for extracting consensus information from a collection of trees over a common leaf set.     

Dense subgraph maintenance under streaming edge weight updates for real-time story identification

Recent years have witnessed an unprecedented proliferation of social media. People around the globe author, everyday, millions of blog posts, social network status updates, etc. This rich stream of information can be used to identify, on an ongoing basis, emerging stories, and events that capture popular attention. Stories can be identified via groups of tightly coupled real-world entities, namely the people, locations, products, etc, that are involved in the story. The sheer scale and rapid evolution of the data involved necessitate highly efficient techniques for identifying important stories at every point of time. The main challenge in real-time story identification is the maintenance of dense subgraphs (corresponding to groups of tightly coupled entities) under streaming edge weight updates (resulting from a stream of user-generated content). This is the first work to study the efficient maintenance of dense subgraphs under such streaming edge weight updates. For a wide range of definitions of density, we derive theoretical results regarding the magnitude of change that a single edge weight update can cause. Based on these, we propose a novel algorithm, DynDens, which outperforms adaptations of existing techniques to this setting and yields meaningful, intuitive results. Our approach is validated by a thorough experimental evaluation on large-scale real and synthetic datasets.     

Distributed Streams Algorithms for Sliding Windows

Massive data sets often arise as physically distributed, parallel data streams, and it is important to estimate various aggregates and statistics on the union of these streams. This paper presents algorithms for estimating aggregate functions over a “sliding window” of the N most recent data items in one or more streams. Our results include: 1. For a single stream,we present the first ε-approximation scheme for the number of 1’s in a sliding window that is optimal in both worst case time and space. We also present the first ε-approximation scheme for the sum of integers in [0..R] in a sliding window that is optimal in both worst case time and space (assuming R is at most polynomial in N). Both algorithms are deterministic and use only logarithmic memory words. 2. In contrast, we show that any deterministic algorithm that estimates, to within a small constant relative error, the number of 1’s (or the sum of integers) in a sliding window on the union of distributed streams requires Ω(N) space. 3. We present the first (randomized) (ε, δ)-approximation scheme for the number of 1’s in a sliding window on the union of distributed streams that uses only logarithmic memory words. We also present the first (ε, δ)-approximation scheme for the number of distinct values in a sliding window on distributed streams that uses only logarithmic memory words. Our results are obtained using a novel family of synopsis data structures called waves.     

MOTION PLANNING OF AN INTELLIGENT ROBOT USING GA MOTIVATED TEMPORAL ASSOCIATIVE MEMORY

ABSTRACT

The paper discusses the concept of re-planning for a mobile robot in the presence of semidynamic obstacles. The navigational planning is done by employing genetic algorithm until it reaches the goal point. The path segments traversed by the mobile robot are stored by a simple matrix, employing temporal associative memory. During subsequent traversal, the robot utilizes the previously stored matrix to avoid an obstacle path. In case of deadlock, the robot back tracks using TAM and finds alternative paths to reach the goal. This algorithm has been realized on a Pioneer 2DX mobile robot of ActiveMedia Robotic LLC, USA, through client server architecture. The result shows that the robot reaches the goal within a vicinity of a 20 mm radius.     

Green synthetic route of carbon quantum dot-reinforced graphene oxide-poly(vinylidene fluoride-co-hexa fluoropropylene) nanocomposites: Toward high dielectric constant and suppressed loss

A simple and green method was developed to fabricate carbon quantum dot@ graphene oxide filled poly (vinylidene fluoride-co-hexa-fluoropropylene) [CQD@GO-P(VDF-HFP)] nanocomposite films via solution casting technique. The synthetic approach was to bring CQD from bilva leafs, a renewable and sustainable resource. The effect of CQD on dielectric properties, dielectric constant, and dielectric loss in the presence of GO along with P (VDF-HFP) matrix were investigated. The result showed that the nanocomposites having 1.5 wt % of CQD@GO-P(VDF-HFP) with higher dielectric constant (≈144) at 100 Hz and suppressed loss (<1) at 1000 Hz, which is well supported by field emission scanning electron microscopy (FESEM) study. The FESEM study shows a river iceland morphology with a channel-like structure along with voids and pores that may provide a conducting network, which tends to have Maxwell Wagner-Sillars or interfacial polarization results in a high-end properties outcome. Furthermore, the suppressed loss enhanced the possibility of end use performance of CQD@GO-P(VDF-HFP) matrix with a referral memorandum of percolation theory. Thus, the present work demonstrated a new approach to develop high dielectric constant and negligible loss materials in the field of embedded devices for electronic industries through green synthetic approach. © 2019 Wiley Periodicals, Inc. J. Appl. Polym. Sci. 2019 , 136, 47850.     

Electromagnetic forward and inverse scattering analysis of a one‐dimensional collision system

A one‐dimensional electromagnetic scattering analysis in presence of a colliding system is presented. A detailed analysis of higher order Doppler effect, due to multiple electromagnetic field reflection upon the two moving objects is performed, invoking the center of momentum frame and taking all possible range of velocity into account. A quasi‐stationary based finite difference time domain numerical method is then performed in order to test the proposed mathematical model for forward scattering analysis. Further, a spectral‐temporal mathematical derivation is performed for the inverse scattering analysis to compute the spatial and temporal information of the target system.     

Quad notch UWB antenna using combination of slots and split‐ring resonator

A novel coplanar waveguide fed UWB antenna with quad notch band characteristics has been proposed in this work. The antenna layout is designed based on a combination of well‐known geometrical shapes: a half ellipse patch, rectangle, and triangle. The shape of the ground plane is partially tapered rectangular. The overall dimension of the antenna is 41.5 × 32 mm. The antenna uses three U‐shaped slots at the top surface to create three notched band characteristics. A split‐ring resonator is then introduced at the bottom surface of the antenna. With the integration of split‐ring resonator at the bottom surface, an additional notch band at 7.25 to 7.75 (6.7%) GHz is created in the antenna. The designed antenna has an operating impedance bandwidth (VSWR ≤2) ranges from 3.03 to 12.34 GHz except in quad frequency stop bands of 3.3 to 3.7 (11.4%), 5.15 to 5.35 (3.8%), 5.725 to 5.825 (1.7%), and 7.25 to 7.75 (6.7%) GHz. The proposed antennas are successfully designed, prototyped, and measured. The simulated and measured results are extensively studied and discussed. Correlation between the time‐domain transmitting antenna input signal and the received antenna output signal is calculated in order to ensure that the proposed antenna can be used in pulse‐communication systems. This antenna finds applications in medical imaging, military radar systems, and other common UWB applications.