OpenRaiser/Intern-Atlas huggingface dataset:
Towards Bridging IoT and Cloud Services: Proposing Smartphones as Mobile and Autonomic Service Gateways
Venue: arXiv cs.OS 2011
Year: 2011

Computing is currently getting at the same time incredibly in the small with sensors/actuators embedded in our every- day objects and also greatly in the large with data and ser- vice clouds accessible anytime, anywhere. This Internet of Things is physically closed to the user but suffers from weak run-time execution environments. Cloud Environments provide powerful data storage and computing power but can not be easily accessed and integrate the final-user context- awareness. We consider smartphones are set to become the universal interface between these two worlds. In this position paper, we propose a middleware approach where smartphones provide service gateways to bridge the gap between IoT services and Cloud services. Since smartphones are mobile gateways, they should be able to (re)configure themself according to their place, things discovered around, and their own resources such battery. Several issues are discussed: collaborative event-based context management, adaptive and opportunistic service deployment and invocation, multi-criteria (user- and performance-oriented) optimization decision algorithm.
Paraconsistency and Topological Semantics
Venue: arXiv cs.LO 2011
Year: 2011

The well-studied notion of deductive explosion describes the situation where any formula can be deduced from an inconsistent set of formulas. Paraconsistent logic, on the other hand, is the umbrella term for logical systems where the logical consequence relation is not explosive. In this work, we investigate the relationship between some different topological spaces and paraconsistency.
Lifted Graphical Models: A Survey
Venue: arXiv cs.AI 2011
Year: 2011

This article presents a survey of work on lifted graphical models. We review a general form for a lifted graphical model, a par-factor graph, and show how a number of existing statistical relational representations map to this formalism. We discuss inference algorithms, including lifted inference algorithms, that efficiently compute the answers to probabilistic queries. We also review work in learning lifted graphical models from data. It is our belief that the need for statistical relational models (whether it goes by that name or another) will grow in the coming decades, as we are inundated with data which is a mix of structured and unstructured, with entities and relations extracted in a noisy manner from text, and with the need to reason effectively with this data. We hope that this synthesis of ideas from many different research groups will provide an accessible starting point for new researchers in this expanding field.
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles
Venue: arXiv cs.DS 2011
Year: 2011

Point-set embeddings and large-angle crossings are two areas of graph drawing that independently have received a lot of attention in the past few years. In this paper, we consider problems in the intersection of these two areas. Given the point-set-embedding scenario, we are interested in how much we gain in terms of computational complexity, curve complexity, and generality if we allow large-angle crossings as compared to the planar case. We investigate two drawing styles where only bends or both bends and edges must be drawn on an underlying grid. We present various results for drawings with one, two, and three bends per edge.
Decision Making for Rapid Information Acquisition in the Reconnaissance of Random Fields
Venue: arXiv cs.SY 2011
Year: 2011

Research into several aspects of robot-enabled reconnaissance of random fields is reported. The work has two major components: the underlying theory of information acquisition in the exploration of unknown fields and the results of experiments on how humans use sensor-equipped robots to perform a simulated reconnaissance exercise. The theoretical framework reported herein extends work on robotic exploration that has been reported by ourselves and others. Several new figures of merit for evaluating exploration strategies are proposed and compared. Using concepts from differential topology and information theory, we develop the theoretical foundation of search strategies aimed at rapid discovery of topological features (locations of critical points and critical level sets) of a priori unknown differentiable random fields. The theory enables study of efficient reconnaissance strategies in which the tradeoff between speed and accuracy can be understood. The proposed approach to rapid discovery of topological features has led in a natural way to to the creation of parsimonious reconnaissance routines that do not rely on any prior knowledge of the environment. The design of topology-guided search protocols uses a mathematical framework that quantifies the relationship between what is discovered and what remains to be discovered. The quantification rests on an information theory inspired model whose properties allow us to treat search as a problem in optimal information acquisition. A central theme in this approach is that "conservative" and "aggressive" search strategies can be precisely defined, and search decisions regarding "exploration" vs. "exploitation" choices are informed by the rate at which the information metric is changing.
Time Consistent Discounting
Venue: arXiv cs.AI 2011
Year: 2011

A possibly immortal agent tries to maximise its summed discounted rewards over time, where discounting is used to avoid infinite utilities and encourage the agent to value current rewards more than future ones. Some commonly used discount functions lead to time-inconsistent behavior where the agent changes its plan over time. These inconsistencies can lead to very poor behavior. We generalise the usual discounted utility model to one where the discount function changes with the age of the agent. We then give a simple characterisation of time-(in)consistent discount functions and show the existence of a rational policy for an agent that knows its discount function is time-inconsistent.
Attacker Control and Impact for Confidentiality and Integrity
Venue: arXiv cs.PL 2011
Year: 2011

Language-based information flow methods offer a principled way to enforce strong security properties, but enforcing noninterference is too inflexible for realistic applications. Security-typed languages have therefore introduced declassification mechanisms for relaxing confidentiality policies, and endorsement mechanisms for relaxing integrity policies. However, a continuing challenge has been to define what security is guaranteed when such mechanisms are used. This paper presents a new semantic framework for expressing security policies for declassification and endorsement in a language-based setting. The key insight is that security can be characterized in terms of the influence that declassification and endorsement allow to the attacker. The new framework introduces two notions of security to describe the influence of the attacker. Attacker control defines what the attacker is able to learn from observable effects of this code; attacker impact captures the attacker's influence on trusted locations. This approach yields novel security conditions for checked endorsements and robust integrity. The framework is flexible enough to recover and to improve on the previously introduced notions of robustness and qualified robustness. Further, the new security conditions can be soundly enforced by a security type system. The applicability and enforcement of the new policies is illustrated through various examples, including data sanitization and authentication.
Singular Perturbation Approximations for a Class of Linear Quantum Systems
Venue: arXiv cs.SY 2011
Year: 2011

This paper considers the use of singular perturbation approximations for a class of linear quantum systems arising in the area of linear quantum optics. The paper presents results on the physical realizability properties of the approximate system arising from singular perturbation model reduction.
Complex Optimization in Answer Set Programming
Venue: arXiv cs.LO 2011
Year: 2011

Preference handling and optimization are indispensable means for addressing non-trivial applications in Answer Set Programming (ASP). However, their implementation becomes difficult whenever they bring about a significant increase in computational complexity. As a consequence, existing ASP systems do not offer complex optimization capacities, supporting, for instance, inclusion-based minimization or Pareto efficiency. Rather, such complex criteria are typically addressed by resorting to dedicated modeling techniques, like saturation. Unlike the ease of common ASP modeling, however, these techniques are rather involved and hardly usable by ASP laymen. We address this problem by developing a general implementation technique by means of meta-programming, thus reusing existing ASP systems to capture various forms of qualitative preferences among answer sets. In this way, complex preferences and optimization capacities become readily available for ASP applications.
BioSimplify: an open source sentence simplification engine to improve recall in automatic biomedical information extraction
Venue: arXiv cs.CL 2011
Year: 2011

BioSimplify is an open source tool written in Java that introduces and facilitates the use of a novel model for sentence simplification tuned for automatic discourse analysis and information extraction (as opposed to sentence simplification for improving human readability). The model is based on a "shot-gun" approach that produces many different (simpler) versions of the original sentence by combining variants of its constituent elements. This tool is optimized for processing biomedical scientific literature such as the abstracts indexed in PubMed. We tested our tool on its impact to the task of PPI extraction and it improved the f-score of the PPI tool by around 7%, with an improvement in recall of around 20%. The BioSimplify tool and test corpus can be downloaded from https://biosimplify.sourceforge.net.
SAT-Based Termination Analysis Using Monotonicity Constraints over the Integers
Venue: arXiv cs.LO 2011
Year: 2011

We describe an algorithm for proving termination of programs abstracted to systems of monotonicity constraints in the integer domain. Monotonicity constraints are a non-trivial extension of the well-known size-change termination method. While deciding termination for systems of monotonicity constraints is PSPACE complete, we focus on a well-defined and significant subset, which we call MCNP, designed to be amenable to a SAT-based solution. Our technique is based on the search for a special type of ranking function defined in terms of bounded differences between multisets of integer values. We describe the application of our approach as the back-end for the termination analysis of Java Bytecode (JBC). At the front-end, systems of monotonicity constraints are obtained by abstracting information, using two different termination analyzers: AProVE and COSTA. Preliminary results reveal that our approach provides a good trade-off between precision and cost of analysis.
Revisiting Degree Distribution Models for Social Graph Analysis
Venue: arXiv cs.SI 2011
Year: 2011

Degree distribution models are incredibly important tools for analyzing and understanding the structure and formation of social networks, and can help guide the design of efficient graph algorithms. In particular, the Power-law degree distribution has long been used to model the structure of online social networks, and is the basis for algorithms and heuristics in graph applications such as influence maximization and social search. Along with recent measurement results, our interest in this topic was sparked by our own experimental results on social graphs that deviated significantly from those predicted by a Power-law model. In this work, we seek a deeper understanding of these deviations, and propose an alternative model with significant implications on graph algorithms and applications. We start by quantifying this artifact using a variety of real social graphs, and show that their structures cannot be accurately modeled using elementary distributions including the Power-law. Instead, we propose the Pareto-Lognormal (PLN) model, verify its goodness-of-fit using graphical and statistical methods, and present an analytical study of its asymptotical differences with the Power-law. To demonstrate the quantitative benefits of the PLN model, we compare the results of three wide-ranging graph applications on real social graphs against those on synthetic graphs generated using the PLN and Power-law models. We show that synthetic graphs generated using PLN are much better predictors of degree distributions in real graphs, and produce experimental results with errors that are orders-of-magnitude smaller than those produced by the Power-law model.
A State-Based Characterisation of the Conflict Preorder
Venue: arXiv cs.FL 2011
Year: 2011

This paper proposes a way to effectively compare the potential of processes to cause conflict. In discrete event systems theory, two concurrent systems are said to be in conflict if they can get trapped in a situation where they are both waiting or running endlessly, forever unable to complete their common task. The conflict preorder is a process-algebraic pre-congruence that compares two processes based on their possible conflicts in combination with other processes. This paper improves on previous theoretical descriptions of the conflict preorder by introducing less conflicting pairs as a concrete state-based characterisation. Based on this characterisation, an effective algorithm is presented to determine whether two processes are related according to the conflict preorder.
Fuzzy Consensus and Synchronization: Theory and Application to Critical Infrastructure Protection Problems
Venue: arXiv cs.SY 2011
Year: 2011

In this paper the Distributed Consensus and Synchronization problems with fuzzy-valued initial conditions are introduced, in order to obtain a shared estimation of the state of a system based on partial and distributed observations, in the case where such a state is affected by ambiguity and/or vagueness. The Discrete-Time Fuzzy Systems (DFS) are introduced as an extension of scalar fuzzy difference equations and some conditions for their stability and representation are provided. The proposed framework is then applied in the field of Critical Infrastructures; the consensus framework is used to represent a scenario where human operators, each able to observe directly the state of a given infrastructure (or of a given area considering vast and geographically dispersed infrastructures), reach an agreement on the overall situation, whose severity is expressed in a linguistic, fuzzy way; conversely synchronization is used to provide a distributed interdependency estimation system, where an array of interdependency models is synchronized via partial observation.
Max-Weight Scheduling in Queueing Networks with Heavy-Tailed Traffic
Venue: arXiv cs.NI 2011
Year: 2011

We consider the problem of packet scheduling in single-hop queueing networks, and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric we use the delay stability of traffic flows: a traffic flow is delay stable if its expected steady-state delay is finite, and delay unstable otherwise. First, we show that a heavy-tailed traffic flow is delay unstable under any scheduling policy. Then, we focus on the celebrated Max-Weight scheduling policy, and show that a light-tailed flow that conflicts with a heavy-tailed flow is also delay unstable. This is true irrespective of the rate or the tail distribution of the light-tailed flow, or other scheduling constraints in the network. Surprisingly, we show that a light-tailed flow can be delay unstable, even when it does not conflict with heavy-tailed traffic. Furthermore, delay stability in this case may depend on the rate of the light-tailed flow. Finally, we turn our attention to the class of Max-Weight-a scheduling policies; we show that if the a-parameters are chosen suitably, then the sum of the a-moments of the steady-state queue lengths is finite. We provide an explicit upper bound for the latter quantity, from which we derive results related to the delay stability of traffic flows, and the scaling of moments of steady-state queue lengths with traffic intensity.
An Efficient Real Time Method of Fingertip Detection
Venue: arXiv cs.CV 2011
Year: 2011

Fingertips detection has been used in many applications, and it is very popular and commonly used in the area of Human Computer Interaction these days. This paper presents a novel time efficient method that will lead to fingertip detection after cropping the irrelevant parts of input image. Binary silhouette of the input image is generated using HSV color space based skin filter and hand cropping done based on histogram of the hand image. The cropped image will be used to figure out the fingertips.
A Hybrid Trajectory Clustering for Predicting User Navigation
Venue: arXiv cs.NI 2011
Year: 2011

Wireless sensor networks (WSNs) suffers from the hot spot problem where the sensor nodes closest to the base station are need to relay more packet than the nodes farther away from the base station. Thus, lifetime of sensory network depends on these closest nodes. Clustering methods are used to extend the lifetime of a wireless sensor network. However, current clustering algorithms usually utilize two techniques; selecting cluster heads with more residual energy, and rotating cluster heads periodically to distribute the energy consumption among nodes in each cluster and lengthen the network lifetime. Most of the algorithms use random selection for selecting the cluster heads. Here, we propose a novel trajectory clustering technique for selecting the cluster heads in WSNs. Our algorithm selects the cluster heads based on traffic and rotates periodically. It provides the first trajectory based clustering technique for selecting the cluster heads and to extenuate the hot spot problem by prolonging the network lifetime.
Optimization with Sparsity-Inducing Penalties
Venue: arXiv cs.LG 2011
Year: 2011

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. They were first dedicated to linear variable selection but numerous extensions have now emerged such as structured sparsity or kernel selection. It turns out that many of the related estimation problems can be cast as convex optimization problems by regularizing the empirical risk with appropriate non-smooth norms. The goal of this paper is to present from a general perspective optimization tools and techniques dedicated to such sparsity-inducing penalties. We cover proximal methods, block-coordinate descent, reweighted $\ell_2$-penalized techniques, working-set and homotopy methods, as well as non-convex formulations and extensions, and provide an extensive set of experiments to compare various algorithms from a computational point of view.
Searching for Voltage Graph-Based LDPC Tailbiting Codes with Large Girth
Venue: arXiv cs.IT 2011
Year: 2011

The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-ones matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.
Wireless Capacity With Arbitrary Gain Matrix
Venue: arXiv cs.DS 2011
Year: 2011

Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size.
Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we present an algorithm, called conauto-2.0, that can efficiently compute a set of generators of the automorphism group of a graph, and test whether two graphs are isomorphic, finding an isomorphism if they are. This algorithm uses the basic individualization/refinement technique, and is an improved version of the algorithm conauto, which has been shown to be very fast for random graphs and several families of hard graphs. In this paper, it is proved that, under some circumstances, it is not only possible to prune the search space (using already found generators of the automorphism group), but also to infer new generators without the need of explicitly finding an automorphism of the graph. This result is especially suited for graphs with regularly connected components, and can be applied in any isomorphism testing and canonical labeling algorithm (that use the individualization/refinement technique) to significantly improve its performance. Additionally, a dynamic target cell selection function is used to adapt to different graphs. The resulting algorithm preserves all the nice features of conauto, but reduces the time for testing graphs with regularly connected components and other hard graph families. We run extensive experiments, which show that the most popular algorithms (namely, nauty, bliss, Traces, and saucy) are slower than conauto-2.0, among others, for the graph families based on components.
Capacity Region of Vector Gaussian Interference Channels with Generally Strong Interference
Venue: arXiv cs.IT 2011
Year: 2011

An interference channel is said to have strong interference if for all input distributions, the receivers can fully decode the interference. This definition of strong interference applies to discrete memoryless, scalar and vector Gaussian interference channels. However, there exist vector Gaussian interference channels that may not satisfy the strong interference condition but for which the capacity can still be achieved by jointly decoding the signal and the interference. This kind of interference is called generally strong interference. Sufficient conditions for a vector Gaussian interference channel to have generally strong interference are derived. The sum-rate capacity and the boundary points of the capacity region are also determined.