OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Inference and Query Processing for RFID Tracking and Monitoring
Venue: arXiv cs.DB 2011
Year: 2011

In this paper, we present the design of a scalable, distributed stream processing system for RFID tracking and monitoring. Since RFID data lacks containment and location information that is key to query processing, we propose to combine location and containment inference with stream query processing in a single architecture, with inference as an enabling mechanism for high-level query processing. We further consider challenges in instantiating such a system in large distributed settings and design techniques for distributed inference and query processing. Our experimental results, using both real-world data and large synthetic traces, demonstrate the accuracy, efficiency, and scalability of our proposed techniques.
Handwritten Digit Recognition with a Committee of Deep Neural Nets on GPUs
Venue: arXiv cs.LG 2011
Year: 2011

The competitive MNIST handwritten digit recognition benchmark has a long history of broken records since 1998. The most recent substantial improvement by others dates back 7 years (error rate 0.4%) . Recently we were able to significantly improve this result, using graphics cards to greatly speed up training of simple but deep MLPs, which achieved 0.35%, outperforming all the previous more complex methods. Here we report another substantial improvement: 0.31% obtained using a committee of MLPs.
Robust Lattice Alignment for K-user MIMO Interference Channels with Imperfect Channel Knowledge
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider a robust lattice alignment design for K-user quasi-static MIMO interference channels with imperfect channel knowledge. With random Gaussian inputs, the conventional interference alignment (IA) method has the feasibility problem when the channel is quasi-static. On the other hand, structured lattices can create structured interference as opposed to the random interference caused by random Gaussian symbols. The structured interference space can be exploited to transmit the desired signals over the gaps. However, the existing alignment methods on the lattice codes for quasi-static channels either require infinite SNR or symmetric interference channel coefficients. Furthermore, perfect channel state information (CSI) is required for these alignment methods, which is difficult to achieve in practice. In this paper, we propose a robust lattice alignment method for quasi-static MIMO interference channels with imperfect CSI at all SNR regimes, and a two-stage decoding algorithm to decode the desired signal from the structured interference space. We derive the achievable data rate based on the proposed robust lattice alignment method, where the design of the precoders, decorrelators, scaling coefficients and interference quantization coefficients is jointly formulated as a mixed integer and continuous optimization problem. The effect of imperfect CSI is also accommodated in the optimization formulation, and hence the derived solution is robust to imperfect CSI. We also design a low complex iterative optimization algorithm for our robust lattice alignment method by using the existing iterative IA algorithm that was designed for the conventional IA method. Numerical results verify the advantages of the proposed robust lattice alignment method.
Representing First-Order Causal Theories by Logic Programs
Venue: arXiv cs.AI 2011
Year: 2011

Nonmonotonic causal logic, introduced by Norman McCain and Hudson Turner, became a basis for the semantics of several expressive action languages. McCain's embedding of definite propositional causal theories into logic programming paved the way to the use of answer set solvers for answering queries about actions described in such languages. In this paper we extend this embedding to nondefinite theories and to first-order causal logic.
Logical, Metric, and Algorithmic Characterisations of Probabilistic Bisimulation
Venue: arXiv cs.LO 2011
Year: 2011

Many behavioural equivalences or preorders for probabilistic processes involve a lifting operation that turns a relation on states into a relation on distributions of states. We show that several existing proposals for lifting relations can be reconciled to be different presentations of essentially the same lifting operation. More interestingly, this lifting operation nicely corresponds to the Kantorovich metric, a fundamental concept used in mathematics to lift a metric on states to a metric on distributions of states, besides the fact the lifting operation is related to the maximum flow problem in optimisation theory. The lifting operation yields a neat notion of probabilistic bisimulation, for which we provide logical, metric, and algorithmic characterisations. Specifically, we extend the Hennessy-Milner logic and the modal mu-calculus with a new modality, resulting in an adequate and an expressive logic for probabilistic bisimilarity, respectively. The correspondence of the lifting operation and the Kantorovich metric leads to a natural characterisation of bisimulations as pseudometrics which are post-fixed points of a monotone function. We also present an "on the fly" algorithm to check if two states in a finitary system are related by probabilistic bisimilarity, exploiting the close relationship between the lifting operation and the maximum flow problem.
Common Signal Analysis
Venue: arXiv cs.IT 2011
Year: 2011

A common signal is defined for any two signals which have non-zero correlation. A mathematical method is provided to extract the best obtainable common signal between the two signals. This analysis is extended to extracting common signal among three signals.
Automatic Synthesis of Switching Controllers for Linear Hybrid Automata
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we study the problem of automatically generating switching controllers for the class of Linear Hybrid Automata, with respect to safety objectives. We identify and solve inaccuracies contained in previous characterizations of the problem, providing a sound and complete symbolic fixpoint procedure, based on polyhedral abstractions of the state space. We also prove the termination of each iteration of the procedure. Some promising experimental results are presented, based on an implementation of the fixpoint procedure on top of the tool PHAVer.
Trust Based Participant Driven Privacy Control in Participatory Sensing
Venue: arXiv cs.NI 2011
Year: 2011

Widespread use of sensors and multisensory personal devices generate a lot of personal information. Sharing this information with others could help in various ways. However, this information may be misused when shared with all. Sharing of information between trusted parties overcomes this problem. This paper describes a model to share information based on interactions and opinions to build trust among peers. It also considers institutional and other controls, which influence the behaviour of the peers. The trust and control build confidence. The computed confidence bespeaks whether to reveal information or not thereby increasing trusted cooperation among peers.
Energy Management Policies for Energy-Neutral Source-Channel Coding
Venue: arXiv cs.IT 2011
Year: 2011

In cyber-physical systems where sensors measure the temporal evolution of a given phenomenon of interest and radio communication takes place over short distances, the energy spent for source acquisition and compression may be comparable with that used for transmission. Additionally, in order to avoid limited lifetime issues, sensors may be powered via energy harvesting and thus collect all the energy they need from the environment. This work addresses the problem of energy allocation over source acquisition/compression and transmission for energy-harvesting sensors. At first, focusing on a single-sensor, energy management policies are identified that guarantee a maximal average distortion while at the same time ensuring the stability of the queue connecting source and channel encoders. It is shown that the identified class of policies is optimal in the sense that it stabilizes the queue whenever this is feasible by any other technique that satisfies the same average distortion constraint. Moreover, this class of policies performs an independent resource optimization for the source and channel encoders. Analog transmission techniques as well as suboptimal strategies that do not use the energy buffer (battery) or use it only for adapting either source or channel encoder energy allocation are also studied for performance comparison. The problem of optimizing the desired trade-off between average distortion and delay is then formulated and solved via dynamic programming tools. Finally, a system with multiple sensors is considered and time-division scheduling strategies are derived that are able to maintain the stability of all data queues and to meet the average distortion constraints at all sensors whenever it is feasible.
Design and classification of dynamic multi-objective optimization problems
Venue: arXiv cs.NE 2011
Year: 2011

In this work we provide a formal model for the different time-dependent components that can appear in dynamic multi-objective optimization problems, along with a classification of these components. Four main classes are identified, corresponding to the influence of the parameters, objective functions, previous states of the dynamic system and, last, environment changes, which in turn lead to online optimization problems. For illustration purposes, examples are provided for each class identified - by no means standing as the most representative ones or exhaustive in scope.
When is social computation better than the sum of its parts?
Venue: arXiv cs.IT 2011
Year: 2011

Social computation, whether in the form of searches performed by swarms of agents or collective predictions of markets, often supplies remarkably good solutions to complex problems. In many examples, individuals trying to solve a problem locally can aggregate their information and work together to arrive at a superior global solution. This suggests that there may be general principles of information aggregation and coordination that can transcend particular applications. Here we show that the general structure of this problem can be cast in terms of information theory and derive mathematical conditions that lead to optimal multi-agent searches. Specifically, we illustrate the problem in terms of local search algorithms for autonomous agents looking for the spatial location of a stochastic source. We explore the types of search problems, defined in terms of the statistical properties of the source and the nature of measurements at each agent, for which coordination among multiple searchers yields an advantage beyond that gained by having the same number of independent searchers. We show that effective coordination corresponds to synergy and that ineffective coordination corresponds to independence as defined using information theory. We classify explicit types of sources in terms of their potential for synergy. We show that sources that emit uncorrelated signals provide no opportunity for synergetic coordination while sources that emit signals that are correlated in some way, do allow for strong synergy between searchers. These general considerations are crucial for designing optimal algorithms for particular search problems in real world settings.
Numerical Experiments for Darcy Flow on a Surface Using Mixed Exterior Calculus Methods
Venue: arXiv cs.NA 2011
Year: 2011

There are very few results on mixed finite element methods on surfaces. A theory for the study of such methods was given recently by Holst and Stern, using a variational crimes framework in the context of finite element exterior calculus. However, we are not aware of any numerical experiments where mixed finite elements derived from discretizations of exterior calculus are used for a surface domain. This short note shows results of our preliminary experiments using mixed methods for Darcy flow (hence scalar Poisson's equation in mixed form) on surfaces. We demonstrate two numerical methods. One is derived from the primal-dual Discrete Exterior Calculus and the other from lowest order finite element exterior calculus. The programming was done in the language Python, using the PyDEC package which makes the code very short and easy to read. The qualitative convergence studies seem to be promising.
Constructing and Sampling Graphs with a Prescribed Joint Degree Distribution
Venue: arXiv cs.DS 2011
Year: 2011

One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work has shown that while these generative models do have the right degree distribution, they are not good models for real life networks due to their differences on other important metrics like conductance. We believe this is, in part, because many of these real-world networks have very different joint degree distributions, i.e. the probability that a randomly selected edge will be between nodes of degree k and l. Assortativity is a sufficient statistic of the joint degree distribution, and it has been previously noted that social networks tend to be assortative, while biological and technological networks tend to be disassortative. We suggest understanding the relationship between network structure and the joint degree distribution of graphs is an interesting avenue of further research. An important tool for such studies are algorithms that can generate random instances of graphs with the same joint degree distribution. This is the main topic of this paper and we study the problem from both a theoretical and practical perspective. We provide an algorithm for constructing simple graphs from a given joint degree distribution, and a Monte Carlo Markov Chain method for sampling them. We also show that the state space of simple graphs with a fixed degree distribution is connected via end point switches. We empirically evaluate the mixing time of this Markov Chain by using experiments based on the autocorrelation of each edge. These experiments show that our Markov Chain mixes quickly on real graphs, allowing for utilization of our techniques in practice.
Programming Massively Parallel Architectures using MARTE: a Case Study
Venue: arXiv cs.DC 2011
Year: 2011

Nowadays, several industrial applications are being ported to parallel architectures. These applications take advantage of the potential parallelism provided by multiple core processors. Many-core processors, especially the GPUs(Graphics Processing Unit), have led the race of floating-point performance since 2003. While the performance improvement of general- purpose microprocessors has slowed significantly, the GPUs have continued to improve relentlessly. As of 2009, the ratio between many-core GPUs and multicore CPUs for peak floating-point calculation throughput is about 10 times. However, as parallel programming requires a non-trivial distribution of tasks and data, developers find it hard to implement their applications effectively. Aiming to improve the use of many-core processors, this work presents an case-study using UML and MARTE profile to specify and generate OpenCL code for intensive signal processing applications. Benchmark results show us the viability of the use of MDE approaches to generate GPU applications.
A Reference Based, Tree Structured Time Synchronization Approach and its Analysis in WSN
Venue: arXiv cs.DC 2011
Year: 2011

Time synchronization for wireless sensor networks (WSNs) has been studied in recent years as a fundamental and significant research issue. Many applications based on these WSNs assume local clocks at each sensor node that need to be synchronized to a common notion of time. Time synchronization in a WSN is critical for accurate time stamping of events and fine-tuned coordination among the sensor nodes to reduce power consumption. This paper proposes a bidirectional, reference based, tree structured time synchronization service for WSNs along with network evaluation phase. This offers a push mechanism for (i) accurate and (ii) low overhead for global time synchronization. Analysis study of proposed approach shows that it is lightweight as the number of required broadcasting messages is constant in one broadcasting domain.
User Modeling Combining Access Logs, Page Content and Semantics
Venue: arXiv cs.IR 2011
Year: 2011

The paper proposes an approach to modeling users of large Web sites based on combining different data sources: access logs and content of the accessed pages are combined with semantic information about the Web pages, the users and the accesses of the users to the Web site. The assumption is that we are dealing with a large Web site providing content to a large number of users accessing the site. The proposed approach represents each user by a set of features derived from the different data sources, where some feature values may be missing for some users. It further enables user modeling based on the provided characteristics of the targeted user subset. The approach is evaluated on real-world data where we compare performance of the automatic assignment of a user to a predefined user segment when different data sources are used to represent the users.
Ubiquitous Positioning: A Taxonomy for Location Determination on Mobile Navigation System
Venue: arXiv cs.HC 2011
Year: 2011

The location determination in obstructed area can be very challenging especially if Global Positioning System are blocked. Users will find it difficult to navigate directly on-site in such condition, especially indoor car park lot or obstructed environment. Sometimes, it needs to combine with other sensors and positioning methods in order to determine the location with more intelligent, reliable and ubiquity. By using ubiquitous positioning in mobile navigation system, it is a promising ubiquitous location technique in a mobile phone since as it is a familiar personal electronic device for many people. However, as research on ubiquitous positioning systems goes beyond basic methods there is an increasing need for better comparison of proposed ubiquitous positioning systems. System developers are also lacking of good frameworks for understanding different options during building ubiquitous positioning systems. This paper proposes taxonomy to address both of these problems. The proposed taxonomy has been constructed from a literature study of papers and articles on positioning estimation that can be used to determine location everywhere on mobile navigation system. For researchers the taxonomy can also be used as an aid for scoping out future research in the area of ubiquitous positioning.
Nested Refinements for Dynamic Languages
Venue: arXiv cs.PL 2011
Year: 2011

Programs written in dynamic languages make heavy use of features --- run-time type tests, value-indexed dictionaries, polymorphism, and higher-order functions --- that are beyond the reach of type systems that employ either purely syntactic or purely semantic reasoning. We present a core calculus, System D, that merges these two modes of reasoning into a single powerful mechanism of nested refinement types wherein the typing relation is itself a predicate in the refinement logic. System D coordinates SMT-based logical implication and syntactic subtyping to automatically typecheck sophisticated dynamic language programs. By coupling nested refinements with McCarthy's theory of finite maps, System D can precisely reason about the interaction of higher-order functions, polymorphism, and dictionaries. The addition of type predicates to the refinement logic creates a circularity that leads to unique technical challenges in the metatheory, which we solve with a novel stratification approach that we use to prove the soundness of System D.
Algorithms for computing the greatest simulations and bisimulations between fuzzy automata
Venue: arXiv cs.FL 2011
Year: 2011

Recently, two types of simulations (forward and backward simulations) and four types of bisimulations (forward, backward, forward-backward, and backward-forward bisimulations) between fuzzy automata have been introduced. If there is at least one simulation/bisimulation of some of these types between the given fuzzy automata, it has been proved that there is the greatest simulation/bisimulation of this kind. In the present paper, for any of the above-mentioned types of simulations/bisimulations we provide an effective algorithm for deciding whether there is a simulation/bisimulation of this type between the given fuzzy automata, and for computing the greatest one, whenever it exists. The algorithms are based on the method developed in [J. Ignjatović, M. Ćirić, S. Bogdanović, On the greatest solutions to certain systems of fuzzy relation inequalities and equations, Fuzzy Sets and Systems 161 (2010) 3081-3113], which comes down to the computing of the greatest post-fixed point, contained in a given fuzzy relation, of an isotone function on the lattice of fuzzy relations.
Using Variable Threshold to Increase Capacity in a Feedback Neural Network
Venue: arXiv cs.NE 2011
Year: 2011

The article presents new results on the use of variable thresholds to increase the capacity of a feedback neural network. Non-binary networks are also considered in this analysis.
Defeating Internet attacks and Spam using "disposable" Mobile IPv6 home addresses
Venue: arXiv cs.CR 2011
Year: 2011

We propose a model of operation for next generation wireless Internet, in which a mobile host has hundreds of "disposable" Mobile IPv6 home addresses. Each correspondent is distributed a different disposable home address. If attacked on a given home address, the mobile user can block packets to that address and become unreachable to the attacker. Blocking one address does not affect other addresses. Other correspondents can still reach the mobile host. A new home address can also be requested via e-mail, instant messaging, or directly from the target host using a protocol that we develop. This model is especially useful against battery exhausting Denial-of-Service (DoS) attacks and CPU exhausting distributed DoS attacks, since it seems to be the only viable solution, currently. We show however that this model can also be used to defeat other attacks and also to stop spam.
Power Consumption of LDPC Decoders in Software Radio
Venue: arXiv cs.IT 2011
Year: 2011

LDPC code is a powerful error correcting code and has been applied to many advanced communication systems. The prosperity of software radio has motivated us to investigate the implementation of LDPC decoders on processors. In this paper, we estimate and compare complexity and power consumption of LDPC decoding algorithms running on general purpose processors. Using the estimation results, we show two power control schemes for software radio: SNR-based algorithm diversity and joint transmit power and receiver energy management. Overall, this paper discusses general concerns about using processors as the software radio platform for the implementation of LDPC decoders.