OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Computation of Avoided Words
Venue: arXiv cs.DS 2016
Year: 2016

The deviation of the observed frequency of a word $w$ from its expected frequency in a given sequence $x$ is used to determine whether or not the word is avoided. This concept is particularly useful in DNA linguistic analysis. The value of the standard deviation of $w$, denoted by $std(w)$, effectively characterises the extent of a word by its edge contrast in the context in which it occurs. A word $w$ of length $k>2$ is a $ρ$-avoided word in $x$ if $std(w) \leq ρ$, for a given threshold $ρ< 0$. Notice that such a word may be completely absent from $x$. Hence computing all such words na\"ıvely can be a very time-consuming procedure, in particular for large $k$. In this article, we propose an $O(n)$-time and $O(n)$-space algorithm to compute all $ρ$-avoided words of length $k$ in a given sequence $x$ of length $n$ over a fixed-sized alphabet. We also present a time-optimal $O(σn)$-time and $O(σn)$-space algorithm to compute all $ρ$-avoided words (of any length) in a sequence of length $n$ over an alphabet of size $σ$. Furthermore, we provide a tight asymptotic upper bound for the number of $ρ$-avoided words and the expected length of the longest one. We make available an open-source implementation of our algorithm. Experimental results, using both real and synthetic data, show the efficiency of our implementation.
Energy-Efficient Resource Management in Ultra Dense Small Cell Networks: A Mean-Field Approach
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, a novel approach for joint power control and user scheduling is proposed for optimizing energy efficiency (EE), in terms of bits per unit power, in ultra dense small cell networks (UDNs). To address this problem, a dynamic stochastic game (DSG) is formulated between small cell base stations (SBSs). This game enables to capture the dynamics of both queues and channel states of the system. To solve this game, assuming a large homogeneous UDN deployment, the problem is cast as a mean field game (MFG) in which the MFG equilibrium is analyzed with the aid of two low-complexity tractable partial differential equations. User scheduling is formulated as a stochastic optimization problem and solved using the drift plus penalty (DPP) approach in the framework of Lyapunov optimization. Remarkably, it is shown that by weaving notions from Lyapunov optimization and mean field theory, the proposed solution yields an equilibrium control policy per SBS which maximizes the network utility while ensuring users' quality-of-service. Simulation results show that the proposed approach achieves up to 18:1% gains in EE and 98.2% reductions in the network's outage probability compared to a baseline model.
Identification of Photovoltaic Arrays' Maximum Power Extraction Point via Dynamic Regressor Extension and Mixing
Venue: arXiv cs.SY 2016
Year: 2016

This paper deals with the problem of identification of photovoltaic arrays' maximum power extraction point---information that is encrypted in the current-voltage characteristic equation. We propose a new parameterisation of the classical five parameter model of this function that, combined with the recently introduced identification technique of dynamic regressor extension and mixing, ensures a fast and accurate estimation of all unknown parameters. A concavity property of the current-voltage characteristic equation is then exploited to directly identify the desired voltage operating point. Realistic numerical examples via computer simulations are presented to assess the performance of the proposed approach.
A method to Implement the Kerberos User Authentication and the secured Internet Service
Venue: arXiv cs.CR 2016
Year: 2016

This paper proposes a PKINIT_AS Kerberos V5 authentication system to use public key cryptography and a method to implement the gssapi_krb authentication method and secured Internet service using it in IPSec VPN
Improved IKE Protocol Design Based On PKI/ECC
Venue: arXiv cs.CR 2016
Year: 2016

This Paper proposes an ECDH key exchange method and an ECsig Digital Signature Authentication method based on group with Koblits curve, man-in-the-middle attack prevention method for SA payload and initiator identification payload to design high intensity IKE that can be implemented in portable devices.
Designing optimal- and fast-on-average pattern matching algorithms
Venue: arXiv cs.DS 2016
Year: 2016

Given a pattern $w$ and a text $t$, the speed of a pattern matching algorithm over $t$ with regard to $w$, is the ratio of the length of $t$ to the number of text accesses performed to search $w$ into $t$. We first propose a general method for computing the limit of the expected speed of pattern matching algorithms, with regard to $w$, over iid texts. Next, we show how to determine the greatest speed which can be achieved among a large class of algorithms, altogether with an algorithm running this speed. Since the complexity of this determination make it impossible to deal with patterns of length greater than 4, we propose a polynomial heuristic. Finally, our approaches are compared with 9 pre-existing pattern matching algorithms from both a theoretical and a practical point of view, i.e. both in terms of limit expected speed on iid texts, and in terms of observed average speed on real data. In all cases, the pre-existing algorithms are outperformed.
SPARQL query processing with Apache Spark
Venue: arXiv cs.DB 2016
Year: 2016

The number of linked data sources and the size of the linked open data graph keep growing every day. As a consequence, semantic RDF services are more and more confronted to various "big data" problems. Query processing is one of them and needs to be efficiently addressed with executions over scalable, highly available and fault tolerant frameworks. Data management systems requiring these properties are rarely built from scratch but are rather designed on top of an existing cluster computing engine. In this work, we consider the processing of SPARQL queries with Apache Spark. We propose and compare five different query processing approaches based on different join execution models and Spark components. A detailed experimentation, on real-world and synthetic data sets, emphasizes that two approaches tailored for the RDF data model outperform the other ones on all major query shapes, i.e., star, snowflake, chain and hybrid.
Complexity Hierarchies and Higher-Order Cons-Free Rewriting
Venue: arXiv cs.CC 2016
Year: 2016

Constructor rewriting systems are said to be cons-free if, roughly, constructor terms in the right-hand sides of rules are subterms of constructor terms in the left-hand side; the computational intuition is that rules cannot build new data structures. It is well-known that cons-free programming languages can be used to characterize computational complexity classes, and that cons-free first-order term rewriting can be used to characterize the set of polynomial-time decidable sets. We investigate cons-free higher-order term rewriting systems, the complexity classes they characterize, and how these depend on the order of the types used in the systems. We prove that, for every k $\geq$ 1, left-linear cons-free systems with type order k characterize E$^k$TIME if arbitrary evaluation is used (i.e., the system does not have a fixed reduction strategy). The main difference with prior work in implicit complexity is that (i) our results hold for non-orthogonal term rewriting systems with possible rule overlaps with no assumptions about reduction strategy, (ii) results for such term rewriting systems have previously only been obtained for k = 1, and with additional syntactic restrictions on top of cons-freeness and left-linearity. Our results are apparently among the first implicit characterizations of the hierarchy E = E$^1$TIME $\subseteq$ E$^2$TIME $\subseteq$ .... Our work confirms prior results that having full non-determinism (via overlaps of rules) does not directly allow characterization of non-deterministic complexity classes like NE. We also show that non-determinism makes the classes characterized highly sensitive to minor syntactic changes such as admitting product types or non-left-linear rules.
deepMiRGene: Deep Neural Network based Precursor microRNA Prediction
Venue: arXiv cs.LG 2016
Year: 2016

Since microRNAs (miRNAs) play a crucial role in post-transcriptional gene regulation, miRNA identification is one of the most essential problems in computational biology. miRNAs are usually short in length ranging between 20 and 23 base pairs. It is thus often difficult to distinguish miRNA-encoding sequences from other non-coding RNAs and pseudo miRNAs that have a similar length, and most previous studies have recommended using precursor miRNAs instead of mature miRNAs for robust detection. A great number of conventional machine-learning-based classification methods have been proposed, but they often have the serious disadvantage of requiring manual feature engineering, and their performance is limited as well. In this paper, we propose a novel miRNA precursor prediction algorithm, deepMiRGene, based on recurrent neural networks, specifically long short-term memory networks. deepMiRGene automatically learns suitable features from the data themselves without manual feature engineering and constructs a model that can successfully reflect structural characteristics of precursor miRNAs. For the performance evaluation of our approach, we have employed several widely used evaluation metrics on three recent benchmark datasets and verified that deepMiRGene delivered comparable performance among the current state-of-the-art tools.
A Distributed Model Predictive Control Framework for Road-Following Formation Control of Car-like Vehicles (Extended Version)
Venue: arXiv cs.RO 2016
Year: 2016

This work presents a novel framework for the formation control of multiple autonomous ground vehicles in an on-road environment. Unique challenges of this problem lie in 1) the design of collision avoidance strategies with obstacles and with other vehicles in a highly structured environment, 2) dynamic reconfiguration of the formation to handle different task specifications. In this paper, we design a local MPC-based tracking controller for each individual vehicle to follow a reference trajectory while satisfying various constraints (kinematics and dynamics, collision avoidance, \textit{etc.}). The reference trajectory of a vehicle is computed from its leader's trajectory, based on a pre-defined formation tree. We use logic rules to organize the collision avoidance behaviors of member vehicles. Moreover, we propose a methodology to safely reconfigure the formation on-the-fly. The proposed framework has been validated using high-fidelity simulations.
DSP Implementation of a Direct Adaptive Feedfoward Control Algorithm for Rejecting Repeatable Runout in Hard Disk Drives
Venue: arXiv cs.SY 2016
Year: 2016

A direct adaptive feedforward control method for tracking repeatable runout (RRO) in bit patterned media recording (BPMR) hard disk drives (HDD) is proposed. The technique estimates the system parameters and the residual RRO simultaneously and constructs a feedforward signal based on a known regressor. An improved version of the proposed algorithm to avoid matrix inversion and reduce computation complexity is given. Results for both MATLAB simulation and digital signal processor (DSP) implementation are provided to verify the effectiveness of the proposed algorithm.
Relationship Queries on Large graphs using Pregel
Venue: arXiv cs.DB 2016
Year: 2016

Large-scale graph-structured data arising from social networks, databases, knowledge bases, web graphs, etc. is now available for analysis and mining. Graph-mining often involves 'relationship queries', which seek a ranked list of interesting interconnections among a given set of entities, corresponding to nodes in the graph. While relationship queries have been studied for many years, using various terminologies, e.g., keyword-search, Steiner-tree in a graph etc., the solutions proposed in the literature so far have not focused on scaling relationship queries to large graphs having billions of nodes and edges, such are now publicly available in the form of 'linked-open-data'. In this paper, we present an algorithm for distributed keyword search (DKS) on large graphs, based on the graph-parallel computing paradigm Pregel. We also present an analytical proof that our algorithm produces an optimally ranked list of answers if run to completion. Even if terminated early, our algorithm produces approximate answers along with bounds. We describe an optimized implementation of our DKS algorithm along with time-complexity analysis. Finally, we report and analyze experiments using an implementation of DKS on Giraph the graph-parallel computing framework based on Pregel, and demonstrate that we can efficiently process relationship queries on large-scale subsets of linked-open-data.
Improved Algorithms for the Evacuation Route Planning Problem
Venue: arXiv cs.DS 2016
Year: 2016

Emergency evacuation is the process of movement of people away from the threat or actual occurrence of hazards such as natural disasters, terrorist attacks, fires and bombs. In this paper, we focus on evacuation from a building, but the ideas can be applied to city and region evacuation. We define the problem and show how it can be modeled using graphs. The resulting optimization problem can be formulated as an integer linear program. Though this can be solved exactly, this approach does not scale well for graphs with thousands of nodes and several hundred thousands of edges. This is impractical for large graphs. We study a special case of this problem, where there is only a single source and a single sink. For this case, we give an improved algorithm \emph{Single Source Single Sink Evacuation Route Planner (SSEP)}, whose evacuation time is always at most that of a famous algorithm \emph{Capacity Constrained Route Planner (CCRP)}, and whose running time is strictly less than that of CCRP. We prove this mathematically and give supporting results by extensive experiments. We also study randomized behavior model of people and give some interesting results.
Response Selection with Topic Clues for Retrieval-based Chatbots
Venue: arXiv cs.CL 2016
Year: 2016

We consider incorporating topic information into message-response matching to boost responses with rich content in retrieval-based chatbots. To this end, we propose a topic-aware convolutional neural tensor network (TACNTN). In TACNTN, matching between a message and a response is not only conducted between a message vector and a response vector generated by convolutional neural networks, but also leverages extra topic information encoded in two topic vectors. The two topic vectors are linear combinations of topic words of the message and the response respectively, where the topic words are obtained from a pre-trained LDA model and their weights are determined by themselves as well as the message vector and the response vector. The message vector, the response vector, and the two topic vectors are fed to neural tensors to calculate a matching score. Empirical study on a public data set and a human annotated data set shows that TACNTN can significantly outperform state-of-the-art methods for message-response matching.
Primary Traffic Characterization and Secondary Transmissions
Venue: arXiv cs.NI 2016
Year: 2016

Channel idle time distribution based secondary transmission strategies have been studied intensively in the literature. Under various performance metrics, the ultimate performance of secondary devices are eventually dictated by the presumed channel idle time distribution. Such distributions can take any arbitrary form in practice. In this work, we study idle time distributions in wireless local area networks (WLAN) using large amount of the channel idle time data collected in real-world WLAN networks. We demonstrate with experimental data that the channel idle time distribution can be closely modeled by hyper-exponential distribution. Furthermore, one can treat the primary packet arrival process as a semi-Markov modulated Poisson process. Several secondary transmission strategies are discussed under this model. It is shown that using only one hyper-exponential distribution, the secondary user can achieve a desirable performance when the primary packet arrival process is stationary. However, experimental data suggests that in practice, this process is not stationary and the secondary user can experience a large performance loss with stationary transmission strategy. We propose a novel transmission strategy that achieves suboptimal secondary user performance when the idle time distribution is not stationary. The performances of secondary transmission strategies are demonstrated using experimental data.
Linear Distances between Markov Chains
Venue: arXiv cs.FL 2016
Year: 2016

We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.
Computing Real Roots of Real Polynomials ... and now For Real!
Venue: arXiv cs.MS 2016
Year: 2016

Very recent work introduces an asymptotically fast subdivision algorithm, denoted ANewDsc, for isolating the real roots of a univariate real polynomial. The method combines Descartes' Rule of Signs to test intervals for the existence of roots, Newton iteration to speed up convergence against clusters of roots, and approximate computation to decrease the required precision. It achieves record bounds on the worst-case complexity for the considered problem, matching the complexity of Pan's method for computing all complex roots and improving upon the complexity of other subdivision methods by several magnitudes. In the article at hand, we report on an implementation of ANewDsc on top of the RS root isolator. RS is a highly efficient realization of the classical Descartes method and currently serves as the default real root solver in Maple. We describe crucial design changes within ANewDsc and RS that led to a high-performance implementation without harming the theoretical complexity of the underlying algorithm. With an excerpt of our extensive collection of benchmarks, available online at http://anewdsc.mpi-inf.mpg.de/, we illustrate that the theoretical gain in performance of ANewDsc over other subdivision methods also transfers into practice. These experiments also show that our new implementation outperforms both RS and mature competitors by magnitudes for notoriously hard instances with clustered roots. For all other instances, we avoid almost any overhead by integrating additional optimizations and heuristics.
When Theory and Reality Collide: Demystifying the Effectiveness of Ambient Sensing for NFC-based Proximity Detection by Applying Relay Attack Data
Venue: arXiv cs.CR 2016
Year: 2016

Over the past decade, smartphones have become the point of convergence for many applications and services. There is a growing trend in which traditional smart-card based services like banking, transport and access control are being provisioned through smartphones. Smartphones with Near Field Communication (NFC) capability can emulate a contactless smart card; popular examples of such services include Google Pay and Apple Pay. Similar to contactless smart cards, NFC-based smartphone transactions are susceptible to relay attacks. For contactless smart cards, distance-bounding protocols are proposed to counter such attacks; for NFC-based smartphone transactions, ambient sensors have been proposed as potential countermeasures. In this study, we have empirically evaluated the suitability of ambient sensors as a proximity detection mechanism for contactless transactions. To provide a comprehensive analysis, we also collected relay attack data to ascertain whether ambient sensors are able to thwart such attacks effectively. We initially evaluated 17 sensors before selecting 7 sensors for in-depth analysis based on their effectiveness as potential proximity detection mechanisms within the constraints of a contactless transaction scenario. Each sensor was used to record 1000 legitimate and relay (illegitimate) contactless transactions at four different physical locations. The analysis of these transactions provides an empirical foundation on which to determine whether ambient sensors provide a strong proximity detection mechanism for security-sensitive applications like banking, transport and high-security access control.
Scalable Device-to-Device Communications For Frequency Reuse >> 1
Venue: arXiv cs.NI 2016
Year: 2016

Proximity based applications are becoming fast growing markets suggesting that Device-to-Device (D2D) communications is becoming an essential part of future mobile data networks. We propose scalable admission and power control methods for D2D communications underlay cellular networks to increase the reuse of frequency resources and thus network capacity while maintaining QoS to all users. The aim of the proposed methods is to maximize the number of D2D links under QoS constraints, therefore maximizing network frequency reuse, while considering different levels of complexity and available channel state information (CSI) in a multi-cell environment. Numerical results show that by using D2D and the proposed multi-cell interference coordination and low power transmission method, the network spectral efficiency can be increased by as much as ten times, while low outage probability can be assured to provided QoS for all users.
Towards an Appropriate Beamforming Scheme for Initial Cell Discovery in mmW 5G Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Beamforming is an essential requirement to combat high pathloss and to improve signal-to-noise ratio during initial cell discovery in future millimeter wave cellular networks. The choice of an appropriate beamforming is directly coupled with its energy consumption. The energy consumption is even of more concern at a battery limited mobile station (MS). In this work, we provide an energy consumption based comparison of different beamforming schemes while considering both a low power and a high power analog-to-digital converter (ADC) for a millimeter wave based receiver at the MS. We analyze both context information (CI) (GPS positioning based) and non context information based schemes, and show that analog beamforming with CI (where mobile station's positioning information is already available) can result in a lower energy consumption, while in all other scenarios digital beamforming has a lower energy consumption than analog and hybrid beamforming. We also show that under certain scenarios recently proposed phase shifters network architecture can result in a lower energy consumption than other beamforming schemes. Moreover, we show that the energy consumption trend among different beamforming schemes is valid irrespective of the number of ADC bits. Finally, we propose a new signaling structure which utilizes a relatively higher frequency sub-carrier for primary synchronization signals compared to other signaling, which allows a further reduction in initial cell search delay and energy consumption of the MS.