OpenRaiser/Intern-Atlas huggingface dataset:
Dependable Management of Untrusted Distributed Systems
Venue: arXiv cs.DC 2014
Year: 2014

The conventional approach to the online management of distributed systems---represented by such standards as SNMP for network management, and WSDM for systems based on service oriented computing (SOC)---relies on the components of the managed system to cooperate in the management process, by providing the managers with the means to monitor their state and activities, and to control their behavior. Unfortunately, the trust thus placed in the cooperation of the managed components is unwarranted for many types of systems---such as systems based on SOA---making the conventional management of such systems unreliable and insecure. This paper introduces a radically new approach to the management of distributed systems, called governance-based management (GBM), which is based on a middleware that can govern the exchange of messages between system components. GBM has a substantial ability to manage distributed systems, in a reliable and secure manner, even without any trustworthy cooperation of the managed components. And it can fully incorporate the conventional management techniques wherever such cooperation can be trusted. GBM also supports a reflexive mode of management, which manages the management process itself, making it safer. However, GBM is still a work in progress, as it raises several open problems that needs to be addressed before this management technique can be put to practice.
Algorithms Visualization Tool for Students and Lectures in Computer Science
Venue: arXiv cs.CY 2014
Year: 2014

The best way to understand complex data structures or algorithm is to see them in action. The present work presents a new tool, especially useful for students and lecturers in computer science. It is written in Java and developed at Bordeaux University of Sciences and Technology. Its purposes is to help students in understanding classical algorithms by illustrating them in different ways: graphical (animated), formal, and descriptive. We think that it can be useful to everyone interested in algorithms, in particular to students in computer science that want to beef up their readings and university lecturers in their major effort to enhance the data structures and algorithms course. The main new thing of this tool is the fact of making it possible to the user to animate their own algorithms.
Sign Language Gibberish for syntactic parsing evaluation
Venue: arXiv cs.CL 2014
Year: 2014

Sign Language (SL) automatic processing slowly progresses bottom-up. The field has seen proposition to handle the video signal, to recognize and synthesize sublexical and lexical units. It starts to see the development of supra-lexical processing. But the recognition, at this level, lacks data. The syntax of SL appears very specific as it uses massively the multiplicity of articulators and its access to the spatial dimensions. Therefore new parsing techniques are developed. However these need to be evaluated. The shortage on real data restrains the corpus-based models to small sizes. We propose here a solution to produce data-sets for the evaluation of parsers on the specific properties of SL. The article first describes the general model used to generates dependency grammars and the phrase generation from these lasts. It then discusses the limits of approach. The solution shows to be of particular interest to evaluate the scalability of the techniques on big models.
Structured Sparse Method for Hyperspectral Unmixing
Venue: arXiv cs.CV 2014
Year: 2014

Hyperspectral Unmixing (HU) has received increasing attention in the past decades due to its ability of unveiling information latent in hyperspectral data. Unfortunately, most existing methods fail to take advantage of the spatial information in data. To overcome this limitation, we propose a Structured Sparse regularized Nonnegative Matrix Factorization (SS-NMF) method from the following two aspects. First, we incorporate a graph Laplacian to encode the manifold structures embedded in the hyperspectral data space. In this way, the highly similar neighboring pixels can be grouped together. Second, the lasso penalty is employed in SS-NMF for the fact that pixels in the same manifold structure are sparsely mixed by a common set of relevant bases. These two factors act as a new structured sparse constraint. With this constraint, our method can learn a compact space, where highly similar pixels are grouped to share correlated sparse representations. Experiments on real hyperspectral data sets with different noise levels demonstrate that our method outperforms the state-of-the-art methods significantly.
Multiagent Conflict Resolution for a Specification Network of Discrete-Event Coordinating Agents
Venue: arXiv cs.MA 2014
Year: 2014

This paper presents a novel compositional approach to distributed coordination module (CM) synthesis for multiple discrete-event agents in the formal languages and automata framework. The approach is supported by two original ideas. The first is a new formalism called the Distributed Constraint Specification Network (DCSN) that can comprehensibly describe the networking constraint relationships among distributed agents. The second is multiagent conflict resolution planning, which entails generating and using AND/OR graphs to compactly represent conflict resolution (synthesis-process) plans for a DCSN. Together with the framework of local CM design developed in the authors' earlier work, the systematic approach supports separately designing local and deconflicting CM's for individual agents in accordance to a selected conflict resolution plan. Composing the agent models and the CM's designed furnishes an overall nonblocking coordination solution that meets the set of inter-agent constraints specified in a given DCSN.
The Deterministic Time-Linearity of Service Provided by Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

In the paper, we study the service process $S(t)$ of an independent and identically distributed (\textit{i.i.d.}) Nakagami-$m$ fading channel, which is defined as the amount of service provided, i.e., the integral of the instantaneous channel capacity over time $t$. By using the Characteristic Function (CF) approach and the infinitely divisible law, it is proved that, other than certain generally recognized curve form {or a stochastic process}, the channel service process $S(t)$ is a deterministic linear function of time $t$, namely, $S(t)=c_m^\ast\cdot t$ where $c_m^\ast$ is a constant determined by the fading parameter $m$. Furthermore, we extend it to general \textit{i.i.d.} fading channels and present an explicit form of the constant service rate $c_p^\ast$. The obtained work provides such a new insight on the system design of joint source/channel coding that there exists a coding scheme such that a receiver can decode with zero error probability and zero high layer queuing delay, if the transmitter maintains a constant data rate no more than $c_p^\ast$. Finally, we verify our analysis through Monte Carlo simulations.
MPISE: Symbolic Execution of MPI Programs
Venue: arXiv cs.DC 2014
Year: 2014

Message Passing Interfaces (MPI) plays an important role in parallel computing. Many parallel applications are implemented as MPI programs. The existing methods of bug detection for MPI programs have the shortage of providing both input and non-determinism coverage, leading to missed bugs. In this paper, we employ symbolic execution to ensure the input coverage, and propose an on-the-fly schedule algorithm to reduce the interleaving explorations for non-determinism coverage, while ensuring the soundness and completeness. We have implemented our approach as a tool, called MPISE, which can automatically detect the deadlock and runtime bugs in MPI programs. The results of the experiments on benchmark programs and real world MPI programs indicate that MPISE finds bugs effectively and efficiently. In addition, our tool also provides diagnostic information and replay mechanism to help understanding bugs.
Blind Recognition of Touched Keys: Attack and Countermeasures
Venue: arXiv cs.CR 2014
Year: 2014

In this paper, we introduce a novel computer vision based attack that discloses inputs on a touch enabled device, while the attacker cannot see any text or popups from a video of the victim tapping on the touch screen. In the attack, we use the optical flow algorithm to identify touching frames where the finger touches the screen surface. We innovatively use intersections of detected edges of the touch screen to derive the homography matrix mapping the touch screen surface in video frames to a reference image of the virtual keyboard. We analyze the shadow formation around the fingertip and use the k-means clustering algorithm to identify touched points. Homography can then map these touched points to keys of the virtual keyboard. Our work is substantially different from existing work. We target password input and are able to achieve a high success rate. We target scenarios like classrooms, conferences and similar gathering places and use a webcam or smartphone camera. In these scenes, single-lens reflex (SLR) cameras and high-end camcorders used in related work will appear suspicious. To defeat such computer vision based attacks, we design, implement and evaluate the Privacy Enhancing Keyboard (PEK) where a randomized virtual keyboard is used to input sensitive information.
Improved Approximation Algorithms for Box Contact Representations
Venue: arXiv cs.DS 2014
Year: 2014

We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called \textsc{Contact Representation of Word Networks} (\textsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. \textsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{Max-Crown}, in which realizing each desired adjacency yields a certain profit. We present the first $O(1)$-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-hard on bipartite graphs of bounded maximum degree.
Comparing Numerical Integration Schemes for Time-Continuous Car-Following Models
Venue: arXiv cs.CE 2014
Year: 2014

When simulating trajectories by integrating time-continuous car-following models, standard integration schemes such as the forth-order Runge-Kutta method (RK4) are rarely used while the simple Euler's method is popular among researchers. We compare four explicit methods: Euler's method, ballistic update, Heun's method (trapezoidal rule), and the standard forth-order RK4. As performance metrics, we plot the global discretization error as a function of the numerical complexity. We tested the methods on several time-continuous car-following models in several multi-vehicle simulation scenarios with and without discontinuities such as stops or a discontinuous behavior of an external leader. We find that the theoretical advantage of RK4 (consistency order~4) only plays a role if both the acceleration function of the model and the external data of the simulation scenario are sufficiently often differentiable. Otherwise, we obtain lower (and often fractional) consistency orders. Although, to our knowledge, Heun's method has never been used for integrating car-following models, it turns out to be the best scheme for many practical situations. The ballistic update always prevails Euler's method although both are of first order.
Clinical TempEval
Venue: arXiv cs.CL 2014
Year: 2014

We describe the Clinical TempEval task which is currently in preparation for the SemEval-2015 evaluation exercise. This task involves identifying and describing events, times and the relations between them in clinical text. Six discrete subtasks are included, focusing on recognising mentions of times and events, describing those mentions for both entity types, identifying the relation between an event and the document creation time, and identifying narrative container relations.
Energy Efficient Scheduling and Routing via Randomized Rounding
Venue: arXiv cs.DS 2014
Year: 2014

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
An efficient, variational approximation of the best fitting multi-Bernoulli filter
Venue: arXiv cs.SY 2014
Year: 2014

The joint probabilistic data association (JPDA) filter is a popular tracking methodology for problems involving well-spaced targets, but it is rarely applied in problems with closely-spaced targets due to its complexity in these cases, and due to the well-known phenomenon of coalescence. This paper addresses these difficulties using random finite sets (RFSs) and variational inference, deriving a highly tractable, approximate method for obtaining the multi-Bernoulli distribution that minimises the set Kullback-Leibler (KL) divergence from the true posterior, working within the RFS framework to incorporate uncertainty in target existence. The derivation is interpreted as an application of expectation-maximisation (EM), where the missing data is the correspondence of Bernoulli components (i.e., tracks) under each data association hypothesis. The missing data is shown to play an identical role to the selection of an ordered distribution in the same ordered family in the set JPDA algorithm. Subsequently, a special case of the proposed method is utilised to provide an efficient approximation of the minimum mean optimal sub-pattern assignment estimator. The performance of the proposed methods is demonstrated in challenging scenarios in which up to twenty targets come into close proximity.
Towards an Interaction-based Integration of MKM Services into End-User Applications
Venue: arXiv cs.HC 2014
Year: 2014

The Semantic Alliance (SAlly) Framework, first presented at MKM 2012, allows integration of Mathematical Knowledge Management services into typical applications and end-user workflows. From an architecture allowing invasion of spreadsheet programs, it grew into a middle-ware connecting spreadsheet, CAD, text and image processing environments with MKM services. The architecture presented in the original paper proved to be quite resilient as it is still used today with only minor changes. This paper explores extensibility challenges we have encountered in the process of developing new services and maintaining the plugins invading end-user applications. After an analysis of the underlying problems, I present an augmented version of the SAlly architecture that addresses these issues and opens new opportunities for document type agnostic MKM services.
Online Local Learning via Semidefinite Programming
Venue: arXiv cs.LG 2014
Year: 2014

In many online learning problems we are interested in predicting local information about some universe of items. For example, we may want to know whether two items are in the same cluster rather than computing an assignment of items to clusters; we may want to know which of two teams will win a game rather than computing a ranking of teams. Although finding the optimal clustering or ranking is typically intractable, it may be possible to predict the relationships between items as well as if you could solve the global optimization problem exactly. Formally, we consider an online learning problem in which a learner repeatedly guesses a pair of labels (l(x), l(y)) and receives an adversarial payoff depending on those labels. The learner's goal is to receive a payoff nearly as good as the best fixed labeling of the items. We show that a simple algorithm based on semidefinite programming can obtain asymptotically optimal regret in the case where the number of possible labels is O(1), resolving an open problem posed by Hazan, Kale, and Shalev-Schwartz. Our main technical contribution is a novel use and analysis of the log determinant regularizer, exploiting the observation that log det(A + I) upper bounds the entropy of any distribution with covariance matrix A.
Nonlinear Feedback Control of Axisymmetric Aerial Vehicles
Venue: arXiv cs.SY 2014
Year: 2014

We investigate the use of simple aerodynamic models for the feedback control of aerial vehicles with large flight envelopes. Thrust-propelled vehicles with a body shape symmetric with respect to the thrust axis are considered. Upon a condition on the aerodynamic characteristics of the vehicle, we show that the equilibrium orientation can be explicitly determined as a function of the desired flight velocity. This allows for the adaptation of previously proposed control design approaches based on the thrust direction control paradigm. Simulation results conducted by using measured aerodynamic characteristics of quasi-axisymmetric bodies illustrate the soundness of the proposed approach.
Differential Amplify-and-Forward Relaying in Time-Varying Rayleigh Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers the performance of differential amplify-and-forward (D-AF) relaying over time-varying Rayleigh fading channels. Using the auto-regressive time-series model to characterize the time-varying nature of the wireless channels, new weights for the maximum ratio combining (MRC) of the received signals at the destination are proposed. Expression for the pair-wise error probability (PEP) is provided and used to obtain an approximation of the total average bit error probability (BEP). The obtained BEP approximation clearly shows how the system performance depends on the auto-correlation of the direct and the cascaded channels and an irreducible error floor exists at high signal-to-noise ratio (SNR). Simulation results also demonstrate that, for fast-fading channels, the new MRC weights lead to a better performance when compared to the classical combining scheme. Our analysis is verified with simulation results in different fading scenarios.
There are Plane Spanners of Maximum Degree 4
Venue: arXiv cs.CG 2014
Year: 2014

Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner, if for any pair of vertices u,v in E the distance between u and v in G is at most t times their distance in E. A spanner is plane if its edges do not cross. This paper considers the question: "What is the smallest maximum degree that can always be achieved for a plane spanner of E?" Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper we show that the complete Euclidean graph always contains a plane spanner of maximum degree at most 4 and make a big step toward closing the question. Our construction leads to an efficient algorithm for obtaining the spanner from Chew's L1-Delaunay triangulation.
An Efficient Method for Face Recognition System In Various Assorted Conditions
Venue: arXiv cs.CV 2014
Year: 2014

In the beginning stage, face verification is done using easy method of geometric algorithm models, but the verification route has now developed into a scientific progress of complicated geometric representation and identical procedure. In recent years the technologies have boosted face recognition system into the healthy focus. Researchers currently undergoing strong research on finding face recognition system for wider area information taken under hysterical elucidation dissimilarity. The proposed face recognition system consists of a narrative expositionindiscreet preprocessing method, a hybrid Fourier-based facial feature extraction and a score fusion scheme. We have verified the face recognition in different lightening conditions (day or night) and at different locations (indoor or outdoor). Preprocessing, Image detection, Feature- extraction and Face recognition are the methods used for face verification system. This paper focuses mainly on the issue of toughness to lighting variations. The proposed system has obtained an average of 88.1% verification rate on Two-Dimensional images under different lightening conditions.
Towards Active Logic Programming
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we present the new logic programming language DALI, aimed at defining agents and agent systems. A main design objective for DALI has been that of introducing in a declarative fashion all the essential features, while keeping the language as close as possible to the syntax and semantics of the plain Horn--clause language. Special atoms and rules have been introduced, for representing: external events, to which the agent is able to respond (reactivity); actions (reactivity and proactivity); internal events (previous conclusions which can trigger further activity); past and present events (to be aware of what has happened). An extended resolution is provided, so that a DALI agent is able to answer queries like in the plain Horn--clause language, but is also able to cope with the different kinds of events, and exhibit a (rational) reactive and proactive behaviour.
Petascale computations for Large-scale Atomic and Molecular collisions
Venue: arXiv cs.DC 2014
Year: 2014

Petaflop architectures are currently being utilized efficiently to perform large scale computations in Atomic, Molecular and Optical Collisions. We solve the Schroedinger or Dirac equation for the appropriate collision problem using the R-matrix or R-matrix with pseudo-states approach. We briefly outline the parallel methodology used and implemented for the current suite of Breit-Pauli and DARC codes. Various examples are shown of our theoretical results compared with those obtained from Synchrotron Radiation facilities and from Satellite observations. We also indicate future directions and implementation of the R-matrix codes on emerging GPU architectures.
Yet Another Graph Partitioning Problem is NP-Hard
Venue: arXiv cs.CC 2014
Year: 2014

Recently a large number of graph separator problems have been proven to be \textsc{NP-Hard}. Amazingly we have found that $α$-Subgraph-Balanced-Vertex-Separator, an important variant, has been overlooked. In this work ``Yet Another Graph Partitioning Problem is NP-Hard" we present the surprising result that $α$-Subgraph-Balanced-Vertex-Separator is $NP$-Hard. This is despite the fact that the constraints of our new problem are harder to satisfy than the original problem.