OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Continued Fraction Expansion Based IIR Realization of Fractional Order Differ-Integrators with Genetic Algorithm
Venue: arXiv cs.SY 2012
Year: 2012

Rational approximation of fractional order (FO) differ-integrators via Continued Fraction Expansion (CFE) is a well known technique. In this paper, the nominal structures of various generating functions are optimized using Genetic Algorithm (GA) to minimize the deviation in magnitude and phase response between the original FO element and the rationalized discrete time filter in Infinite Impulse Response (IIR) structure. The optimized filter based realizations show better approximation of the FO elements in comparison with the existing methods and is demonstrated by the frequency response of the IIR filters.
S3A: Secure System Simplex Architecture for Enhanced Security of Cyber-Physical Systems
Venue: arXiv cs.CR 2012
Year: 2012

Until recently, cyber-physical systems, especially those with safety-critical properties that manage critical infrastructure (e.g. power generation plants, water treatment facilities, etc.) were considered to be invulnerable against software security breaches. The recently discovered 'W32.Stuxnet' worm has drastically changed this perception by demonstrating that such systems are susceptible to external attacks. Here we present an architecture that enhances the security of safety-critical cyber-physical systems despite the presence of such malware. Our architecture uses the property that control systems have deterministic execution behavior, to detect an intrusion within 0.6 μs while still guaranteeing the safety of the plant. We also show that even if an attack is successful, the overall state of the physical system will still remain safe. Even if the operating system's administrative privileges have been compromised, our architecture will still be able to protect the physical system from coming to harm.
Tag-Aware Recommender Systems: A State-of-the-art Survey
Venue: arXiv cs.IR 2012
Year: 2012

In the past decade, Social Tagging Systems have attracted increasing attention from both physical and computer science communities. Besides the underlying structure and dynamics of tagging systems, many efforts have been addressed to unify tagging information to reveal user behaviors and preferences, extract the latent semantic relations among items, make recommendations, and so on. Specifically, this article summarizes recent progress about tag-aware recommender systems, emphasizing on the contributions from three mainstream perspectives and approaches: network-based methods, tensor-based methods, and the topic-based methods. Finally, we outline some other tag-related works and future challenges of tag-aware recommendation algorithms.
FLOW-Methode - Methodenbeschreibung zur Anwendung von FLOW
Venue: arXiv cs.SE 2012
Year: 2012

Information of many kinds is flowing in software projects and organizations. Requirements have to flow from the customer to the developers. Testers need to know the requirements as well. Boundary conditions and design decisions have to be at the right place at the right time. Information flow analysis with FLOW facilitates modeling of mode and route of the flow of information and experience independent of the development methodology. Experience often acts as a control factor, because experienced developers can process and route information more efficiently. Therefore, experience needs to be at the right place at the right time, too. However, most valuable experiences never get documented. Since information and experience is flowing in agile as well as in traditional environments, the FLOW method does not distinguish between agile and traditional, but only between how the flows are shaped. ---- In Softwareprojekten fließen vielerlei Informationen. Anforderungen müssen vom Kunden zu den Entwicklern gelangen. Auch Tester müssen die Anforderungen kennen. Randbedingungen und Entwurfsentscheidungen müssen zur rechten Zeit am rechten Ort sein. Die Informationsflussanalyse mit FLOW ermöglicht es, unabhängig von der Entwicklungsmethode zu modellieren, wie und auf welchem Wege Informationen und Erfahrungen fließen. Erfahrungen spielen dabei oft die Rolle von Steuergrößen, denn erfahrene Mitarbeiter können Informationen kompetenter bearbeiten und weiterleiten. Auch die Erfahrungen müssen in geeigneter Form zur rechten Zeit am rechten Ort sein. Viele Erfahrungen werden aber nie dokumentiert. Da Informationen und Erfahrungen sowohl in agilen als auch in traditionellen Umgebungen fließen müssen, wird in FLOW ein Modell aufgebaut, das nicht nach agil, traditionell oder anderen Bezeichnungen unterscheidet, sondern einzig danach, wie die Flüsse gestaltet sind.
Game Theoretic Network Coding-aided MAC for Data Dissemination towards Energy Efficiency
Venue: arXiv cs.GT 2012
Year: 2012

In this paper we propose game theoretic Medium Access Control (MAC) strategies for data dissemination scenarios. In particular, we use energy-based utility functions that inherently imply power-awareness, while we consider network coding techniques to eliminate the necessity of exchanging acknowledgement control packets. Simulation results show that our proposed strategies enhance the energy efficiency of the system and reduce the dissemination completion time compared to an optimized standard protocol.
Technique detection software for Sparse Matrices
Venue: arXiv cs.MS 2012
Year: 2012

Sparse storage formats are techniques for storing and processing the sparse matrix data efficiently. The performance of these storage formats depend upon the distribution of non-zeros, within the matrix in different dimensions. In order to have better results we need a technique that suits best the organization of data in a particular matrix. So the decision of selecting a better technique is the main step towards improving the system's results otherwise the efficiency can be decreased. The purpose of this research is to help identify the best storage format in case of reduced storage size and high processing efficiency for a sparse matrix.
Joint Source-Channel Cooperative Transmission over Relay-Broadcast Networks
Venue: arXiv cs.IT 2012
Year: 2012

Reliable transmission of a discrete memoryless source over a multiple-relay relay-broadcast network is considered. Motivated by sensor network applications, it is assumed that the relays and the destinations all have access to side information correlated with the underlying source signal. Joint source-channel cooperative transmission is studied in which the relays help the transmission of the source signal to the destinations by using both their overheard signals, as in the classical channel cooperation scenario, as well as the available correlated side information. Decode-and-forward (DF) based cooperative transmission is considered in a network of multiple relay terminals and two different achievability schemes are proposed: i) a regular encoding and sliding-window decoding scheme without explicit source binning at the encoder, and ii) a semi-regular encoding and backward decoding scheme with binning based on the side information statistics. It is shown that both of these schemes lead to the same source-channel code rate, which is shown to be the "source-channel capacity" in the case of i) a physically degraded relay network in which the side information signals are also degraded in the same order as the channel; and ii) a relay-broadcast network in which all the terminals want to reconstruct the source reliably, while at most one of them can act as a relay.
Multiflow Transmission in Delay Constrained Cooperative Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper considers the problem of energy-efficient transmission in multi-flow multihop cooperative wireless networks. Although the performance gains of cooperative approaches are well known, the combinatorial nature of these schemes makes it difficult to design efficient polynomial-time algorithms for joint routing, scheduling and power control. This becomes more so when there is more than one flow in the network. It has been conjectured by many authors, in the literature, that the multiflow problem in cooperative networks is an NP-hard problem. In this paper, we formulate the problem, as a combinatorial optimization problem, for a general setting of $k$-flows, and formally prove that the problem is not only NP-hard but it is $o(n^{1/7-ε})$ inapproxmiable. To our knowledge*, these results provide the first such inapproxmiablity proof in the context of multiflow cooperative wireless networks. We further prove that for a special case of k = 1 the solution is a simple path, and devise a polynomial time algorithm for jointly optimizing routing, scheduling and power control. We then use this algorithm to establish analytical upper and lower bounds for the optimal performance for the general case of $k$ flows. Furthermore, we propose a polynomial time heuristic for calculating the solution for the general case and evaluate the performance of this heuristic under different channel conditions and against the analytical upper and lower bounds.
On the computational complexity of a game of cops and robbers
Venue: arXiv cs.CC 2012
Year: 2012

We study the computational complexity of a perfect-information two-player game proposed by Aigner and Fromme. The game takes place on an undirected graph where n simultaneously moving cops attempt to capture a single robber, all moving at the same speed. The players are allowed to pick their starting positions at the first move. The question of the computational complexity of deciding this game was raised in the '90s by Goldstein and Reingold. We prove that the game is hard for PSPACE.
Interference Alignment for Partially Connected MIMO Cellular Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose an iterative interference alignment (IA) algorithm for MIMO cellular networks with partial connectivity, which is induced by heterogeneous path losses and spatial correlation. Such systems impose several key technical challenges in the IA algorithm design, namely the overlapping between the direct and interfering links due to the MIMO cellular topology as well as how to exploit the partial connectivity. We shall address these challenges and propose a three stage IA algorithm. As illustration, we analyze the achievable degree of freedom (DoF) of the proposed algorithm for a symmetric partially connected MIMO cellular network. We show that there is significant DoF gain compared with conventional IA algorithms due to partial connectivity. The derived DoF bound is also backward compatible with that achieved on fully connected K-pair MIMO interference channels.
Maximum Inner-Product Search using Tree Data-structures
Venue: arXiv cs.CG 2012
Year: 2012

The problem of {\em efficiently} finding the best match for a query in a given set with respect to the Euclidean distance or the cosine similarity has been extensively studied in literature. However, a closely related problem of efficiently finding the best match with respect to the inner product has never been explored in the general setting to the best of our knowledge. In this paper we consider this general problem and contrast it with the existing best-match algorithms. First, we propose a general branch-and-bound algorithm using a tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Finally we present a new data structure for increasing the efficiency of the dual-tree algorithm. These branch-and-bound algorithms involve novel bounds suited for the purpose of best-matching with inner products. We evaluate our proposed algorithms on a variety of data sets from various applications, and exhibit up to five orders of magnitude improvement in query time over the naive search technique.
Instance Based Methods --- A Brief Overview
Venue: arXiv cs.LO 2012
Year: 2012

Instance-based methods are a specific class of methods for automated proof search in first-order logic. This article provides an overview of the major methods in the area and discusses their properties and relations to the more established resolution methods. It also discusses some recent trends on refinements and applications. This overview is rather brief and informal, but we provide a comprehensive literature list to follow-up on the details.
Reduced-Dimension Linear Transform Coding of Correlated Signals in Networks
Venue: arXiv cs.IT 2012
Year: 2012

A model, called the linear transform network (LTN), is proposed to analyze the compression and estimation of correlated signals transmitted over directed acyclic graphs (DAGs). An LTN is a DAG network with multiple source and receiver nodes. Source nodes transmit subspace projections of random correlated signals by applying reduced-dimension linear transforms. The subspace projections are linearly processed by multiple relays and routed to intended receivers. Each receiver applies a linear estimator to approximate a subset of the sources with minimum mean squared error (MSE) distortion. The model is extended to include noisy networks with power constraints on transmitters. A key task is to compute all local compression matrices and linear estimators in the network to minimize end-to-end distortion. The non-convex problem is solved iteratively within an optimization framework using constrained quadratic programs (QPs). The proposed algorithm recovers as special cases the regular and distributed Karhunen-Loeve transforms (KLTs). Cut-set lower bounds on the distortion region of multi-source, multi-receiver networks are given for linear coding based on convex relaxations. Cut-set lower bounds are also given for any coding strategy based on information theory. The distortion region and compression-estimation tradeoffs are illustrated for different communication demands (e.g. multiple unicast), and graph structures.
A Mean Value Theorem Approach to Robust Control Design for Uncertain Nonlinear Systems
Venue: arXiv cs.SY 2012
Year: 2012

This paper presents a scheme to design a tracking controller for a class of uncertain nonlinear systems using a robust feedback linearization approach. The scheme is composed of two steps. In the first step, a linearized uncertainty model for the corresponding uncertain nonlinear system is developed using a robust feedback linearization approach. In this step, the standard feedback linearization approach is used to linearize the nominal nonlinear dynamics of the uncertain nonlinear system. The remaining nonlinear uncertainties are then linearized at an arbitrary point using the mean value theorem. This approach gives a multi-input multi-output (MIMO) linear uncertain system model with a structured uncertainty representation. In the second step, a minimax linear quadratic regulation (LQR) controller is designed for MIMO linearized uncertain system model. In order to demonstrate the effectiveness of the proposed method, it is applied to a velocity and altitude tracking control problem for an air-breathing hypersonic flight vehicle.
CoLoR: a Coq library on well-founded rewrite relations and its application to the automated verification of termination certificates
Venue: arXiv cs.LO 2012
Year: 2012

Termination is an important property of programs; notably required for programs formulated in proof assistants. It is a very active subject of research in the Turing-complete formalism of term rewriting systems, where many methods and tools have been developed over the years to address this problem. Ensuring reliability of those tools is therefore an important issue. In this paper we present a library formalizing important results of the theory of well-founded (rewrite) relations in the proof assistant Coq. We also present its application to the automated verification of termination certificates, as produced by termination tools.
Simplified, stable parallel merging
Venue: arXiv cs.DC 2012
Year: 2012

This note makes an observation that significantly simplifies a number of previous parallel, two-way merge algorithms based on binary search and sequential merge in parallel. First, it is shown that the additional merge step of distinguished elements as found in previous algorithms is not necessary, thus simplifying the implementation and reducing constant factors. Second, by fixating the requirements to the binary search, the merge algorithm becomes stable, provided that the sequential merge subroutine is stable. The stable, parallel merge algorithm can easily be used to implement a stable, parallel merge sort. For ordered sequences with $n$ and $m$ elements, $m\leq n$, the simplified merge algorithm runs in $O(n/p+\log n)$ operations using $p$ processing elements. It can be implemented on an EREW PRAM, but since it requires only a single synchronization step, it is also a candidate for implementation on other parallel, shared-memory computers.
Verification of Relational Data-Centric Dynamic Systems with External Services
Venue: arXiv cs.DB 2012
Year: 2012

Data-centric dynamic systems are systems where both the process controlling the dynamics and the manipulation of data are equally central. In this paper we study verification of (first-order) mu-calculus variants over relational data-centric dynamic systems, where data are represented by a full-fledged relational database, and the process is described in terms of atomic actions that evolve the database. The execution of such actions may involve calls to external services, providing fresh data inserted into the system. As a result such systems are typically infinite-state. We show that verification is undecidable in general, and we isolate notable cases, where decidability is achieved. Specifically we start by considering service calls that return values deterministically (depending only on passed parameters). We show that in a mu-calculus variant that preserves knowledge of objects appeared along a run we get decidability under the assumption that the fresh data introduced along a run are bounded, though they might not be bounded in the overall system. In fact we tie such a result to a notion related to weak acyclicity studied in data exchange. Then, we move to nondeterministic services where the assumption of data bounded run would result in a bound on the service calls that can be invoked during the execution and hence would be too restrictive. So we investigate decidability under the assumption that knowledge of objects is preserved only if they are continuously present. We show that if infinitely many values occur in a run but do not accumulate in the same state, then we get again decidability. We give syntactic conditions to avoid this accumulation through the novel notion of "generate-recall acyclicity", which takes into consideration that every service call activation generates new values that cannot be accumulated indefinitely.
Design of State-based Schedulers for a Network of Control Loops
Venue: arXiv cs.SY 2012
Year: 2012

For a closed-loop system, which has a contention-based multiple access network on its sensor link, the Medium Access Controller (MAC) may discard some packets when the traffic on the link is high. We use a local state-based scheduler to select a few critical data packets to send to the MAC. In this paper, we analyze the impact of such a scheduler on the closed-loop system in the presence of traffic, and show that there is a dual effect with state-based scheduling. In general, this makes the optimal scheduler and controller hard to find. However, by removing past controls from the scheduling criterion, we find that certainty equivalence holds. This condition is related to the classical result of Bar-Shalom and Tse, and it leads to the design of a scheduler with a certainty equivalent controller. This design, however, does not result in an equivalent system to the original problem, in the sense of Witsenhausen. Computing the estimate is difficult, but can be simplified by introducing a symmetry constraint on the scheduler. Based on these findings, we propose a dual predictor architecture for the closed-loop system, which ensures separation between scheduler, observer and controller. We present an example of this architecture, which illustrates a network-aware event-triggering mechanism.
A Bayesian Approach to Discovering Truth from Conflicting Sources for Data Integration
Venue: arXiv cs.DB 2012
Year: 2012

In practical data integration systems, it is common for the data sources being integrated to provide conflicting information about the same entity. Consequently, a major challenge for data integration is to derive the most complete and accurate integrated records from diverse and sometimes conflicting sources. We term this challenge the truth finding problem. We observe that some sources are generally more reliable than others, and therefore a good model of source quality is the key to solving the truth finding problem. In this work, we propose a probabilistic graphical model that can automatically infer true records and source quality without any supervision. In contrast to previous methods, our principled approach leverages a generative process of two types of errors (false positive and false negative) by modeling two different aspects of source quality. In so doing, ours is also the first approach designed to merge multi-valued attribute types. Our method is scalable, due to an efficient sampling-based inference algorithm that needs very few iterations in practice and enjoys linear time complexity, with an even faster incremental variant. Experiments on two real world datasets show that our new method outperforms existing state-of-the-art approaches to the truth finding problem.
Scaling Datalog for Machine Learning on Big Data
Venue: arXiv cs.DB 2012
Year: 2012

In this paper, we present the case for a declarative foundation for data-intensive machine learning systems. Instead of creating a new system for each specific flavor of machine learning task, or hardcoding new optimizations, we argue for the use of recursive queries to program a variety of machine learning systems. By taking this approach, database query optimization techniques can be utilized to identify effective execution plans, and the resulting runtime plans can be executed on a single unified data-parallel query processing engine. As a proof of concept, we consider two programming models--Pregel and Iterative Map-Reduce-Update---from the machine learning domain, and show how they can be captured in Datalog, tuned for a specific task, and then compiled into an optimized physical plan. Experiments performed on a large computing cluster with real data demonstrate that this declarative approach can provide very good performance while offering both increased generality and programming ease.
Conducting Truthful Surveys, Cheaply
Venue: arXiv cs.GT 2012
Year: 2012

We consider the problem of conducting a survey with the goal of obtaining an unbiased estimator of some population statistic when individuals have unknown costs (drawn from a known prior) for participating in the survey. Individuals must be compensated for their participation and are strategic agents, and so the payment scheme must incentivize truthful behavior. We derive optimal truthful mechanisms for this problem for the two goals of minimizing the variance of the estimator given a fixed budget, and minimizing the expected cost of the survey given a fixed variance goal.