OpenRaiser/Intern-Atlas huggingface dataset:
Multiple Presents: How Search Engines Re-write the Past
Venue: arXiv cs.IR 2009
Year: 2009

Internet search engines function in a present which changes continuously. The search engines update their indices regularly, overwriting Web pages with newer ones, adding new pages to the index, and losing older ones. Some search engines can be used to search for information at the internet for specific periods of time. However, these 'date stamps' are not determined by the first occurrence of the pages in the Web, but by the last date at which a page was updated or a new page was added, and the search engine's crawler updated this change in the database. This has major implications for the use of search engines in scholarly research as well as theoretical implications for the conceptions of time and temporality. We examine the interplay between the different updating frequencies by using AltaVista and Google for searches at different moments of time. Both the retrieval of the results and the structure of the retrieved information erodes over time.
Google matrix and Ulam networks of intermittency maps
Venue: arXiv cs.IR 2009
Year: 2009

We study the properties of the Google matrix of an Ulam network generated by intermittency maps. This network is created by the Ulam method which gives a matrix approximant for the Perron-Frobenius operator of dynamical map. The spectral properties of eigenvalues and eigenvectors of this matrix are analyzed. We show that the PageRank of the system is characterized by a power law decay with the exponent $β$ dependent on map parameters and the Google damping factor $α$. Under certain conditions the PageRank is completely delocalized so that the Google search in such a situation becomes inefficient.
A Semantic Grid Oriented to E-Tourism
Venue: arXiv cs.DC 2009
Year: 2009

With increasing complexity of tourism business models and tasks, there is a clear need of the next generation e-Tourism infrastructure to support flexible automation, integration, computation, storage, and collaboration. Currently several enabling technologies such as semantic Web, Web service, agent and grid computing have been applied in the different e-Tourism applications, however there is no a unified framework to be able to integrate all of them. So this paper presents a promising e-Tourism framework based on emerging semantic grid, in which a number of key design issues are discussed including architecture, ontologies structure, semantic reconciliation, service and resource discovery, role based authorization and intelligent agent. The paper finally provides the implementation of the framework.
A computational definition of the notion of vectorial space
Venue: arXiv cs.LO 2009
Year: 2009

We usually define an algebraic structure by a set, some operations defined on this set and some propositions that the algebraic structure must validate. In some cases, we can replace these propositions by an algorithm on terms constructed upon these operations that the algebraic structure must validate. We show in this note that this is the case for the notions of vectorial space and bilinear operation. KEYWORDS: Rewrite system, vector space, bilinear operation, tensorial product, semantics, quantum programming languages, probabilistic programming languages.
Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
Venue: arXiv cs.IT 2009
Year: 2009

In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \cite{DMM}. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the first of two conference papers describing the derivation of these algorithms, connection with the related literature, extensions of the original framework, and new empirical evidence. In particular, the present paper outlines the derivation of AMP from standard sum-product belief propagation, and its extension in several directions. We also discuss relations with formal calculations based on statistical mechanics methods.
The Importance, Design and Implementation of a Middleware for Networked Control Systems
Venue: arXiv cs.NI 2009
Year: 2009

Due to the advancement of computing and communication technology, networked control systems may soon become prevalent in many control applications. While the capability of employing the communication network in the control loop certainly provides many benefits, it also raises several challenges which need to be overcome to utilize the benefits. In this chapter, we focus on one major challenge: a middleware framework that enables a networked control system to be implemented. Indeed our thesis is that a middleware for networked control sys important for the future of networked control systems. We discuss the fundamental issues which need to be considered in the design and development of an appropriate middleware for networked control systems. We describe \emph{Etherware}, a middleware for networked control system which has been developed at the University of Illinois, as an example of such a middleware framework, to illustrate how these issues can be addressed in the design of a middleware. Using a networked inverted pendulum control system as an example, we demonstrate the powerful capabilities provided by Etherware for a networked control system.
Markovian Network Interdiction and the Four Color Theorem
Venue: arXiv cs.DM 2009
Year: 2009

The Unreactive Markovian Evader Interdiction Problem (UME) asks to optimally place sensors on a network to detect Markovian motion by one or more "evaders". It was previously proved that finding the optimal sensor placement is NP-hard if the number of evaders is unbounded. Here we show that the problem is NP-hard with just 2 evaders using a connection to coloring of planar graphs. The results suggest that approximation algorithms are needed even in applications where the number of evaders is small. It remains an open problem to determine the complexity of the 1-evader case or to devise efficient algorithms.
Structural Consistency: Enabling XML Keyword Search to Eliminate Spurious Results Consistently
Venue: arXiv cs.DB 2009
Year: 2009

XML keyword search is a user-friendly way to query XML data using only keywords. In XML keyword search, to achieve high precision without sacrificing recall, it is important to remove spurious results not intended by the user. Efforts to eliminate spurious results have enjoyed some success by using the concepts of LCA or its variants, SLCA and MLCA. However, existing methods still could find many spurious results. The fundamental cause for the occurrence of spurious results is that the existing methods try to eliminate spurious results locally without global examination of all the query results and, accordingly, some spurious results are not consistently eliminated. In this paper, we propose a novel keyword search method that removes spurious results consistently by exploiting the new concept of structural consistency.
Bio-inspired speed detection and discrimination
Venue: arXiv cs.CV 2009
Year: 2009

In the field of computer vision, a crucial task is the detection of motion (also called optical flow extraction). This operation allows analysis such as 3D reconstruction, feature tracking, time-to-collision and novelty detection among others. Most of the optical flow extraction techniques work within a finite range of speeds. Usually, the range of detection is extended towards higher speeds by combining some multiscale information in a serial architecture. This serial multi-scale approach suffers from the problem of error propagation related to the number of scales used in the algorithm. On the other hand, biological experiments show that human motion perception seems to follow a parallel multiscale scheme. In this work we present a bio-inspired parallel architecture to perform detection of motion, providing a wide range of operation and avoiding error propagation associated with the serial architecture. To test our algorithm, we perform relative error comparisons between both classical and proposed techniques, showing that the parallel architecture is able to achieve motion detection with results similar to the serial approach.
Introduction to Distributed Systems
Venue: arXiv cs.DC 2009
Year: 2009

Computing has passed through many transformations since the birth of the first computing machines. Developments in technology have resulted in the availability of fast and inexpensive processors, and progresses in communication technology have resulted in the availability of lucrative and highly proficient computer networks. Among these, the centralized networks have one component that is shared by users all the time. All resources are accessible, but there is a single point of control as well as a single point of failure. The integration of computer and networking technologies gave birth to new paradigm of computing called distributed computing in the late 1970s. Distributed computing has changed the face of computing and offered quick and precise solutions for a variety of complex problems for different fields. Nowadays, we are fully engrossed by the information age, and expending more time communicating and gathering information through the Internet. The Internet keeps on progressing along more than a few magnitudes, abiding end systems increasingly to communicate in more and more different ways. Over the years, several methods have evolved to enable these developments, ranging from simplistic data sharing to advanced systems supporting a multitude of services. This article provides an overview of distributed computing systems. The definition, architecture, characteristics of distributed systems and the various distributed computing fallacies are discussed in the beginning. Finally, discusses client/server computing, World Wide Web and types of distributed systems.
On Feasibility of Interference Alignment in MIMO Interference Networks
Venue: arXiv cs.IT 2009
Year: 2009

We explore the feasibility of interference alignment in signal vector space -- based only on beamforming -- for K-user MIMO interference channels. Our main contribution is to relate the feasibility issue to the problem of determining the solvability of a multivariate polynomial system, considered extensively in algebraic geometry. It is well known, e.g. from Bezout's theorem, that generic polynomial systems are solvable if and only if the number of equations does not exceed the number of variables. Following this intuition, we classify signal space interference alignment problems as either proper or improper based on the number of equations and variables. Rigorous connections between feasible and proper systems are made through Bernshtein's theorem for the case where each transmitter uses only one beamforming vector. The multi-beam case introduces dependencies among the coefficients of a polynomial system so that the system is no longer generic in the sense required by both theorems. In this case, we show that the connection between feasible and proper systems can be further strengthened (since the equivalency between feasible and proper systems does not always hold) by including standard information theoretic outer bounds in the feasibility analysis.
A tight upper bound on the (2,1)-total labeling number of outerplanar graphs
Venue: arXiv cs.DM 2009
Year: 2009

A $(2,1)$-total labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ and the edge set $E(G)$ to the set $\{0,1,...,k\}$ of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ is a vertex and $y$ is an edge incident to $x$, and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are a pair of adjacent vertices or a pair of adjacent edges, for all $x$ and $y$ in $V(G)\cup E(G)$. The $(2,1)$-total labeling number $λ^T_2(G)$ of a graph $G$ is defined as the minimum $k$ among all possible assignments. In [D. Chen and W. Wang. (2,1)-Total labelling of outerplanar graphs. Discr. Appl. Math. 155, 2585--2593 (2007)], Chen and Wang conjectured that all outerplanar graphs $G$ satisfy $λ^T_2(G) \leq Δ(G)+2$, where $Δ(G)$ is the maximum degree of $G$, while they also showed that it is true for $G$ with $Δ(G)\geq 5$. In this paper, we solve their conjecture completely, by proving that $λ^T_2(G) \leq Δ(G)+2$ even in the case of $Δ(G)\leq 4 $.
A characterization of Konig-Egervary graphs using a common property of all maximum matchings
Venue: arXiv cs.DM 2009
Year: 2009

The independence number of a graph G, denoted by alpha(G), is the cardinality of an independent set of maximum size in G, while mu(G) is the size of a maximum matching in G, i.e., its matching number. G is a Konig-Egervary graph if its order equals alpha(G)+mu(G). In this paper we give a new characterization of Konig-Egervary graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a Konig-Egervary graph.
An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting
Venue: arXiv cs.IT 2009
Year: 2009

Compressed sensing deals with the reconstruction of sparse signals using a small number of linear measurements. One of the main challenges in compressed sensing is to find the support of a sparse signal. In the literature, several bounds on the scaling law of the number of measurements for successful support recovery have been derived where the main focus is on random Gaussian measurement matrices. In this paper, we investigate the noisy support recovery problem from an estimation theoretic point of view, where no specific assumption is made on the underlying measurement matrix. The linear measurements are perturbed by additive white Gaussian noise. We define the output of a support estimator to be a set of position values in increasing order. We set the error between the true and estimated supports as the $\ell_2$-norm of their difference. On the one hand, this choice allows us to use the machinery behind the $\ell_2$-norm error metric and on the other hand, converts the support recovery into a more intuitive and geometrical problem. First, by using the Hammersley-Chapman-Robbins (HCR) bound, we derive a fundamental lower bound on the performance of any \emph{unbiased} estimator of the support set. This lower bound provides us with necessary conditions on the number of measurements for reliable $\ell_2$-norm support recovery, which we specifically evaluate for uniform Gaussian measurement matrices. Then, we analyze the maximum likelihood estimator and derive conditions under which the HCR bound is achievable. This leads us to the number of measurements for the optimum decoder which is sufficient for reliable $\ell_2$-norm support recovery. Using this framework, we specifically evaluate sufficient conditions for uniform Gaussian measurement matrices.
Asynchronous CDMA Systems with Random Spreading-Part II: Design Criteria
Venue: arXiv cs.IT 2009
Year: 2009

Totally asynchronous code-division multiple-access (CDMA) systems are addressed. In Part I, the fundamental limits of asynchronous CDMA systems are analyzed in terms of spectral efficiency and SINR at the output of the optimum linear detector. The focus of Part II is the design of low-complexity implementations of linear multiuser detectors in systems with many users that admit a multistage representation, e.g. reduced rank multistage Wiener filters, polynomial expansion detectors, weighted linear parallel interference cancellers. The effects of excess bandwidth, chip-pulse shaping, and time delay distribution on CDMA with suboptimum linear receiver structures are investigated. Recursive expressions for universal weight design are given. The performance in terms of SINR is derived in the large-system limit and the performance improvement over synchronous systems is quantified. The considerations distinguish between two ways of forming discrete-time statistics: chip-matched filtering and oversampling.
A Bayesian Rule for Adaptive Control based on Causal Interventions
Venue: arXiv cs.AI 2009
Year: 2009

Explaining adaptive behavior is a central problem in artificial intelligence research. Here we formalize adaptive agents as mixture distributions over sequences of inputs and outputs (I/O). Each distribution of the mixture constitutes a `possible world', but the agent does not know which of the possible worlds it is actually facing. The problem is to adapt the I/O stream in a way that is compatible with the true world. A natural measure of adaptation can be obtained by the Kullback-Leibler (KL) divergence between the I/O distribution of the true world and the I/O distribution expected by the agent that is uncertain about possible worlds. In the case of pure input streams, the Bayesian mixture provides a well-known solution for this problem. We show, however, that in the case of I/O streams this solution breaks down, because outputs are issued by the agent itself and require a different probabilistic syntax as provided by intervention calculus. Based on this calculus, we obtain a Bayesian control rule that allows modeling adaptive behavior with mixture distributions over I/O streams. This rule might allow for a novel approach to adaptive control based on a minimum KL-principle.
A conversion between utility and information
Venue: arXiv cs.AI 2009
Year: 2009

Rewards typically express desirabilities or preferences over a set of alternatives. Here we propose that rewards can be defined for any probability distribution based on three desiderata, namely that rewards should be real-valued, additive and order-preserving, where the latter implies that more probable events should also be more desirable. Our main result states that rewards are then uniquely determined by the negative information content. To analyze stochastic processes, we define the utility of a realization as its reward rate. Under this interpretation, we show that the expected utility of a stochastic process is its negative entropy rate. Furthermore, we apply our results to analyze agent-environment interactions. We show that the expected utility that will actually be achieved by the agent is given by the negative cross-entropy from the input-output (I/O) distribution of the coupled interaction system and the agent's I/O distribution. Thus, our results allow for an information-theoretic interpretation of the notion of utility and the characterization of agent-environment interactions in terms of entropy dynamics.
Untangling Phase and Time in Monophonic Sounds
Venue: arXiv cs.SD 2009
Year: 2009

We are looking for a mathematical model of monophonic sounds with independent time and phase dimensions. With such a model we can resynthesise a sound with arbitrarily modulated frequency and progress of the timbre. We propose such a model and show that it exactly fulfils some natural properties, like a kind of time-invariance, robustness against non-harmonic frequencies, envelope preservation, and inclusion of plain resampling as a special case. The resulting algorithm is efficient and allows to process data in a streaming manner with phase and shape modulation at sample rate, what we demonstrate with an implementation in the functional language Haskell. It allows a wide range of applications, namely pitch shifting and time scaling, creative FM synthesis effects, compression of monophonic sounds, generating loops for sampled sounds, synthesise sounds similar to wavetable synthesis, or making ultrasound audible.
Towards an embedding of Graph Transformation in Intuitionistic Linear Logic
Venue: arXiv cs.LO 2009
Year: 2009

Linear logics have been shown to be able to embed both rewriting-based approaches and process calculi in a single, declarative framework. In this paper we are exploring the embedding of double-pushout graph transformations into quantified linear logic, leading to a Curry-Howard style isomorphism between graphs and transformations on one hand, formulas and proof terms on the other. With linear implication representing rules and reachability of graphs, and the tensor modelling parallel composition of graphs and transformations, we obtain a language able to encode graph transformation systems and their computations as well as reason about their properties.
Lattice QCD Thermodynamics on the Grid
Venue: arXiv cs.DC 2009
Year: 2009

We describe how we have used simultaneously ${\cal O}(10^3)$ nodes of the EGEE Grid, accumulating ca. 300 CPU-years in 2-3 months, to determine an important property of Quantum Chromodynamics. We explain how Grid resources were exploited efficiently and with ease, using user-level overlay based on Ganga and DIANE tools above standard Grid software stack. Application-specific scheduling and resource selection based on simple but powerful heuristics allowed to improve efficiency of the processing to obtain desired scientific results by a specified deadline. This is also a demonstration of combined use of supercomputers, to calculate the initial state of the QCD system, and Grids, to perform the subsequent massively distributed simulations. The QCD simulation was performed on a $16^3\times 4$ lattice. Keeping the strange quark mass at its physical value, we reduced the masses of the up and down quarks until, under an increase of temperature, the system underwent a second-order phase transition to a quark-gluon plasma. Then we measured the response of this system to an increase in the quark density. We find that the transition is smoothened rather than sharpened. If confirmed on a finer lattice, this finding makes it unlikely for ongoing experimental searches to find a QCD critical point at small chemical potential.
Hierarchies in Dictionary Definition Space
Venue: arXiv cs.CL 2009
Year: 2009

A dictionary defines words in terms of other words. Definitions can tell you the meanings of words you don't know, but only if you know the meanings of the defining words. How many words do you need to know (and which ones) in order to be able to learn all the rest from definitions? We reduced dictionaries to their "grounding kernels" (GKs), about 10% of the dictionary, from which all the other words could be defined. The GK words turned out to have psycholinguistic correlates: they were learned at an earlier age and more concrete than the rest of the dictionary. But one can compress still more: the GK turns out to have internal structure, with a strongly connected "kernel core" (KC) and a surrounding layer, from which a hierarchy of definitional distances can be derived, all the way out to the periphery of the full dictionary. These definitional distances, too, are correlated with psycholinguistic variables (age of acquisition, concreteness, imageability, oral and written frequency) and hence perhaps with the "mental lexicon" in each of our heads.