OpenRaiser/Intern-Atlas huggingface dataset:
The TCP-modified Engset Model Revisited
Venue: arXiv cs.NI 2014
Year: 2014

We revisit the TCP-modified Engset model proposed by Heyman et al. in [1]. The model deals with the superposition of a limited number of TCP connections alternating between file transmission and silence in a web-like fashion. We consider homogeneous sources only. (a) We take into account the effects of slow start and limited receiver window as well as small average file sizes. (b) We propose an alternative way for calculating the average connection rate in the superposition. (c) From the model we propose a way for calculating the queuing behavior; i.e., the overflow probability. (d) From this last point, we propose a new link buffer sizing rule. Comparison with extensive simulations shows that the average rate and duration, as well as, link utilization are accurately predicted for exponentially distributed file sizes. For longer tail distributions, the model remains accurate provided the receiver window is adjusted appropriately. The accuracy increases with increasing load. As concerns the queuing behavior, the same observation applies. Finally, the revisited model cannot be used to predict losses larger than about 1%. The model overestimates loss rates above that threshold.
Active Learning for Autonomous Intelligent Agents: Exploration, Curiosity, and Interaction
Venue: arXiv cs.AI 2014
Year: 2014

In this survey we present different approaches that allow an intelligent agent to explore autonomous its environment to gather information and learn multiple tasks. Different communities proposed different solutions, that are in many cases, similar and/or complementary. These solutions include active learning, exploration/exploitation, online-learning and social learning. The common aspect of all these approaches is that it is the agent to selects and decides what information to gather next. Applications for these approaches already include tutoring systems, autonomous grasping learning, navigation and mapping and human-robot interaction. We discuss how these approaches are related, explaining their similarities and their differences in terms of problem assumptions and metrics of success. We consider that such an integrated discussion will improve inter-disciplinary research and applications.
Linear Recognition of Almost Interval Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Let $\mbox{interval} + k v$, $\mbox{interval} + k e$, and $\mbox{interval} - k e$ denote the classes of graphs that can be obtained from some interval graph by adding $k$ vertices, adding $k$ edges, and deleting $k$ edges, respectively. When $k$ is small, these graph classes are called almost interval graphs. They are well motivated from computational biology, where the data ought to be represented by an interval graph while we can only expect an almost interval graph for the best. For any fixed $k$, we give linear-time algorithms for recognizing all these classes, and in the case of membership, our algorithms provide also a specific interval graph as evidence. When $k$ is part of the input, these problems are also known as graph modification problems, all NP-complete. Our results imply that they are fixed-parameter tractable parameterized by $k$, thereby resolving the long-standing open problem on the parameterized complexity of recognizing $\mbox{interval}+ k e$, first asked by Bodlaender et al. [Bioinformatics, 11:49--57, 1995]. Moreover, our algorithms for recognizing $\mbox{interval}+ k v$ and $\mbox{interval}- k e$ run in times $O(6^k \cdot (n + m))$ and $O(8^k \cdot (n + m))$, (where $n$ and $m$ stand for the numbers of vertices and edges respectively in the input graph,) significantly improving the $O(k^{2k}\cdot n^3m)$-time algorithm of Heggernes et al. [STOC 2007] and the $O(10^k \cdot n^9)$-time algorithm of Cao and Marx [SODA 2014] respectively.
Disimplicial arcs, transitive vertices, and disimplicial eliminations
Venue: arXiv cs.DM 2014
Year: 2014

In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a digraph is a pair $V \to W$ of sets of vertices such that $v \to w$ is an arc for every $v \in V$ and $w \in W$. An arc $v \to w$ is disimplicial when $N^-(w) \to N^+(v)$ is a diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.
Unsupervised Anomaly-based Malware Detection using Hardware Features
Venue: arXiv cs.CR 2014
Year: 2014

Recent works have shown promise in using microarchitectural execution patterns to detect malware programs. These detectors belong to a class of detectors known as signature-based detectors as they catch malware by comparing a program's execution pattern (signature) to execution patterns of known malware programs. In this work, we propose a new class of detectors - anomaly-based hardware malware detectors - that do not require signatures for malware detection, and thus can catch a wider range of malware including potentially novel ones. We use unsupervised machine learning to build profiles of normal program execution based on data from performance counters, and use these profiles to detect significant deviations in program behavior that occur as a result of malware exploitation. We show that real-world exploitation of popular programs such as IE and Adobe PDF Reader on a Windows/x86 platform can be detected with nearly perfect certainty. We also examine the limits and challenges in implementing this approach in face of a sophisticated adversary attempting to evade anomaly-based detection. The proposed detector is complementary to previously proposed signature-based detectors and can be used together to improve security.
Automated Tracking and Estimation for Control of Non-rigid Cloth
Venue: arXiv cs.CV 2014
Year: 2014

This report is a summary of research conducted on cloth tracking for automated textile manufacturing during a two semester long research course at Georgia Tech. This work was completed in 2009. Advances in current sensing technology such as the Microsoft Kinect would now allow me to relax certain assumptions and generally improve the tracking performance. This is because a major part of my approach described in this paper was to track features in a 2D image and use these to estimate the cloth deformation. Innovations such as the Kinect would improve estimation due to the automatic depth information obtained when tracking 2D pixel locations. Additionally, higher resolution camera images would probably give better quality feature tracking. However, although I would use different technology now to implement this tracker, the algorithm described and implemented in this paper is still a viable approach which is why I am publishing this as a tech report for reference. In addition, although the related work is a bit exhaustive, it will be useful to a reader who is new to methods for tracking and estimation as well as modeling of cloth.
Link and Location Based Routing Mechanism for Energy Efficiency in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

In Wireless Sensor Networks, sensed data are reported to the sink by the available nodes in the communication range. The sensed data should be reported to the sink with the frequency expected by the sink. In order to have a communication between source and sink, Link based routing is used. Link based routing aims to achieve an energy efficient and reliable routing path. This mechanism considers the status (current energy level in terms of Joules) of each node, link condition (number of transmissions that the Cluster Head (CH)and the Gateway (GW) candidates conducts) and the transmit power (power required for transmission in terms of Joules). A metric called Predicted Transmission Count (PTX) for each node is calculated using its status, link condition and transmit power. The node which has highest PTX will have the highest priority and it will be the potential candidate to act as CH or GW. Thus the selection of proper CH or GW reduces the energy consumption, and the network lifetime is increased.
Feature Extraction of ECG Signal Using HHT Algorithm
Venue: arXiv cs.CV 2014
Year: 2014

This paper describe the features extraction algorithm for electrocardiogram (ECG) signal using Huang Hilbert Transform and Wavelet Transform. ECG signal for an individual human being is different due to unique heart structure. The purpose of feature extraction of ECG signal would allow successful abnormality detection and efficient prognosis due to heart disorder. Some major important features will be extracted from ECG signals such as amplitude, duration, pre-gradient, post-gradient and so on. Therefore, we need a strong mathematical model to extract such useful parameter. Here an adaptive mathematical analysis model is Hilbert-Huang transform (HHT). This new approach, the Hilbert-Huang transform, is implemented to analyze the non-linear and nonstationary data. It is unique and different from the existing methods of data analysis and does not require an a priori functional basis. The effectiveness of the proposed scheme is verified through the simulation.
Continuous Features Discretization for Anomaly Intrusion Detectors Generation
Venue: arXiv cs.NI 2014
Year: 2014

Network security is a growing issue, with the evolution of computer systems and expansion of attacks. Biological systems have been inspiring scientists and designs for new adaptive solutions, such as genetic algorithms. In this paper, we present an approach that uses the genetic algorithm to generate anomaly net- work intrusion detectors. In this paper, an algorithm propose use a discretization method for the continuous features selected for the intrusion detection, to create some homogeneity between values, which have different data types. Then,the intrusion detection system is tested against the NSL-KDD data set using different distance methods. A comparison is held amongst the results, and it is shown by the end that this proposed approach has good results, and recommendations is given for future experiments.
Statistical Structure Learning, Towards a Robust Smart Grid
Venue: arXiv cs.LG 2014
Year: 2014

Robust control and maintenance of the grid relies on accurate data. Both PMUs and state estimators are prone to false data injection attacks. Thus, it is crucial to have a mechanism for fast and accurate detection of an agent maliciously tampering with the data---for both preventing attacks that may lead to blackouts, and for routine monitoring and control tasks of current and future grids. We propose a decentralized false data injection detection scheme based on Markov graph of the bus phase angles. We utilize the Conditional Covariance Test (CCT) to learn the structure of the grid. Using the DC power flow model, we show that under normal circumstances, and because of walk-summability of the grid graph, the Markov graph of the voltage angles can be determined by the power grid graph. Therefore, a discrepancy between calculated Markov graph and learned structure should trigger the alarm. Local grid topology is available online from the protection system and we exploit it to check for mismatch. Should a mismatch be detected, we use correlation anomaly score to detect the set of attacked nodes. Our method can detect the most recent stealthy deception attack on the power grid that assumes knowledge of bus-branch model of the system and is capable of deceiving the state estimator, damaging power network observatory, control, monitoring, demand response and pricing schemes. Specifically, under the stealthy deception attack, the Markov graph of phase angles changes. In addition to detect a state of attack, our method can detect the set of attacked nodes. To the best of our knowledge, our remedy is the first to comprehensively detect this sophisticated attack and it does not need additional hardware. Moreover, our detection scheme is successful no matter the size of the attacked subset. Simulation of various power networks confirms our claims.
Five Modular Redundancy with Mitigation Technique to Recover the Error Module
Venue: arXiv cs.AR 2014
Year: 2014

Hazard radiation can lead the system fault therefore Fault Tolerance is required. Fault Tolerant is a system, which is designed to keep operations running, despite the degradation in the specific module is happening. Many fault tolerances have been developed to handle the problem, to find the most robust and efficient in the possible technology. This paper will present the Five Modular Redundancy (FMR) with Mitigation Technique to Recover the Error Module. With Dynamic Partial Reconfiguration technology that have already available today, such fault tolerance technique can be implemented successfully. The project showed the robustness of the system is increased and module which is error can be recovered immediately.
Improving Performance of a Group of Classification Algorithms Using Resampling and Feature Selection
Venue: arXiv cs.LG 2014
Year: 2014

In recent years the importance of finding a meaningful pattern from huge datasets has become more challenging. Data miners try to adopt innovative methods to face this problem by applying feature selection methods. In this paper we propose a new hybrid method in which we use a combination of resampling, filtering the sample domain and wrapper subset evaluation method with genetic search to reduce dimensions of Lung-Cancer dataset that we received from UCI Repository of Machine Learning databases. Finally, we apply some well- known classification algorithms (Naïve Bayes, Logistic, Multilayer Perceptron, Best First Decision Tree and JRIP) to the resulting dataset and compare the results and prediction rates before and after the application of our feature selection method on that dataset. The results show a substantial progress in the average performance of five classification algorithms simultaneously and the classification error for these classifiers decreases considerably. The experiments also show that this method outperforms other feature selection methods with a lower cost.
Excuse Me! or The Courteous Theatregoers' Problem
Venue: arXiv cs.DM 2014
Year: 2014

Consider a theatre consisting of $m$ rows each containing $n$ seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers and their willingness to get up so as to create free space that will allow passage to others. Thus, courtesy facilitates and may well increase the overall seat occupancy of the theatre. We say a theatregoer is courteous if (s)he will get up to let others pass. Otherwise, the theatregoer is selfish. A set of theatregoers is $p$-courteous if each theatregoer in the set is courteous with probability $p$, randomly and independently. It is assumed that the behaviour of a theatregoer does not change during the occupancy of the row. In this paper, we are interested in the following question: what is the expected number of occupied seats as a function of the total number of seats in a theatre, $n$, and the probability that a theatregoer is courteous, $p$? We study and analyze interesting variants of this problem reflecting behaviour of the theatregoers as entirely selfish, and $p$-courteous for a row of seats with one or two entrances and as a consequence for a theatre with $m$ rows of seats with multiple aisles. We also consider the case where seats in a row are chosen according to the geometric distribution and the Zipf distibrution (as opposed to the uniform distribution) and provide bounds on the occupancy of a row (and thus the theatre) in each case.
Performance and Robustness Analysis of Stochastic Jump Linear Systems using Wasserstein metric
Venue: arXiv cs.SY 2014
Year: 2014

This paper focuses on the performance and the robustness analysis of stochastic jump linear systems. The state trajectory under stochastic jump process becomes random variables, which brings forth the probability distributions in the system state. Therefore, we need to adopt a proper metric to measure the system performance with respect to stochastic switching. In this perspective, Wasserstein metric that assesses the distance between probability density functions is applied to provide the performance and the robustness analysis. Both the transient and steady-state performance of the systems with given initial state uncertainties can be measured in this framework. Also, we prove that the convergence of this metric implies the mean square stability. Overall, this study provides a unifying framework for the performance and the robustness analysis of general stochastic jump linear systems, but not necessarily Markovian jump process that is commonly used for stochastic switching. The practical usefulness and efficiency of the proposed method are verified through numerical examples.
Node Removal Vulnerability of the Largest Component of a Network
Venue: arXiv cs.SI 2014
Year: 2014

The connectivity structure of a network can be very sensitive to removal of certain nodes in the network. In this paper, we study the sensitivity of the largest component size to node removals. We prove that minimizing the largest component size is equivalent to solving a matrix one-norm minimization problem whose column vectors are orthogonal and sparse and they form a basis of the null space of the associated graph Laplacian matrix. A greedy node removal algorithm is then proposed based on the matrix one-norm minimization. In comparison with other node centralities such as node degree and betweenness, experimental results on US power grid dataset validate the effectiveness of the proposed approach in terms of reduction of the largest component size with relatively few node removals.
Speeding Up Logico-Numerical Strategy Iteration (extended version)
Venue: arXiv cs.LO 2014
Year: 2014

We introduce an efficient combination of polyhedral analysis and predicate partitioning. Template polyhedral analysis abstracts numerical variables inside a program by one polyhedron per control location, with a priori fixed directions for the faces. The strongest inductive invariant in such an abstract domain may be computed by upward strategy iteration. If the transition relation includes disjunctions and existential quantifiers (a succinct representation for an exponential set of paths), this invariant can be computed by a combination of strategy iteration and satisfiability modulo theory (SMT) solving. Unfortunately, the above approaches lead to unacceptable space and time costs if applied to a program whose control states have been partitioned according to predicates. We therefore propose a modification of the strategy iteration algorithm where the strategies are stored succinctly, and the linear programs to be solved at each iteration step are simplified according to an equivalence relation. We have implemented the technique in a prototype tool and we demonstrate on a series of examples that the approach performs significantly better than previous strategy iteration techniques.
LIPS: A Light Intensity Based Positioning System For Indoor Environments
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents LIPS, a Light Intensity based Positioning System for indoor environments. The system uses off-the-shelf LED lamps as signal sources, and uses light sensors as signal receivers. The design is inspired by the observation that a light sensor has deterministic sensitivity to both distance and incident angle of light signal, an under-utilized feature of photodiodes now widely found on mobile devices. We develop a stable and accurate light intensity model to capture the phenomenon, based on which a new positioning principle, Multi-Face Light Positioning (MFLP), is established that uses three collocated sensors to uniquely determine the receiver's position, assuming merely a single source of light. We have implemented a prototype on both dedicated embedded systems and smartphones. Experimental results show average positioning accuracy within 0.4 meters across different environments, with high stability against interferences from obstacles, ambient lights, temperature variation, etc.
Scalable RDF Data Compression using X10
Venue: arXiv cs.DC 2014
Year: 2014

The Semantic Web comprises enormous volumes of semi-structured data elements. For interoperability, these elements are represented by long strings. Such representations are not efficient for the purposes of Semantic Web applications that perform computations over large volumes of information. A typical method for alleviating the impact of this problem is through the use of compression methods that produce more compact representations of the data. The use of dictionary encoding for this purpose is particularly prevalent in Semantic Web database systems. However, centralized implementations present performance bottlenecks, giving rise to the need for scalable, efficient distributed encoding schemes. In this paper, we describe an encoding implementation based on the asynchronous partitioned global address space (APGAS) parallel programming model. We evaluate performance on a cluster of up to 384 cores and datasets of up to 11 billion triples (1.9 TB). Compared to the state-of-art MapReduce algorithm, we demonstrate a speedup of 2.6-7.4x and excellent scalability. These results illustrate the strong potential of the APGAS model for efficient implementation of dictionary encoding and contributes to the engineering of larger scale Semantic Web applications.
String Reconstruction from Substring Compositions
Venue: arXiv cs.DM 2014
Year: 2014

Motivated by mass-spectrometry protein sequencing, we consider a simply-stated problem of reconstructing a string from the multiset of its substring compositions. We show that all strings of length 7, one less than a prime, or one less than twice a prime, can be reconstructed uniquely up to reversal. For all other lengths we show that reconstruction is not always possible and provide sometimes-tight bounds on the largest number of strings with given substring compositions. The lower bounds are derived by combinatorial arguments and the upper bounds by algebraic considerations that precisely characterize the set of strings with the same substring compositions in terms of the factorization of bivariate polynomials. The problem can be viewed as a combinatorial simplification of the turnpike problem, and its solution may shed light on this long-standing problem as well. Using well known results on transience of multi-dimensional random walks, we also provide a reconstruction algorithm that reconstructs random strings over alphabets of size $\ge4$ in optimal near-quadratic time.