OpenRaiser/Intern-Atlas huggingface dataset:
Towards Multimodal Content Representation
Venue: arXiv cs.CL 2009
Year: 2009

Multimodal interfaces, combining the use of speech, graphics, gestures, and facial expressions in input and output, promise to provide new possibilities to deal with information in more effective and efficient ways, supporting for instance: - the understanding of possibly imprecise, partial or ambiguous multimodal input; - the generation of coordinated, cohesive, and coherent multimodal presentations; - the management of multimodal interaction (e.g., task completion, adapting the interface, error prevention) by representing and exploiting models of the user, the domain, the task, the interactive context, and the media (e.g. text, audio, video). The present document is intended to support the discussion on multimodal content representation, its possible objectives and basic constraints, and how the definition of a generic representation framework for multimodal content representation may be approached. It takes into account the results of the Dagstuhl workshop, in particular those of the informal working group on multimodal meaning representation that was active during the workshop (see http://www.dfki.de/~wahlster/Dagstuhl_Multi_Modality, Working Group 4).
Lightweight Data Indexing and Compression in External Memory
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size $n$, they use only ${n}$ bits of disk working space while all previous approaches use $\Th{n \log n}$ bits of disk working space. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the BWT that uses $\Th{n}$ bits of working space, and a lightweight {\em internal-memory} algorithm for computing the BWT which is the fastest in the literature when the available working space is $\os{n}$ bits. Finally, we prove {\em lower} bounds on the complexity of computing and inverting the BWT via sequential scans in terms of the classic product: internal-memory space $\times$ number of passes over the disk data.
Exploration of Periodically Varying Graphs
Venue: arXiv cs.DS 2009
Year: 2009

We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined by the periodic movements of carriers. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards' tours, etc. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the PV graphs defined by restricted classes of carriers movements: simple routes, and circular routes. We then prove that the limitations on computability and complexity we have established are indeed tight. In fact we prove that all necessary conditions are also sufficient and all lower bounds on costs are tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids. An added benefit is that the algorithms are rather simple.
The Weighted CFG Constraint
Venue: arXiv cs.AI 2009
Year: 2009

We introduce the weighted CFG constraint and propose a propagation algorithm that enforces domain consistency in $O(n^3|G|)$ time. We show that this algorithm can be decomposed into a set of primitive arithmetic constraints without hindering propagation.
The Bibliometric Properties of Article Readership Information
Venue: arXiv cs.DL 2009
Year: 2009

The NASA Astrophysics Data System (ADS), along with astronomy's journals and data centers (a collaboration dubbed URANIA), has developed a distributed on-line digital library which has become the dominant means by which astronomers search, access and read their technical literature. Digital libraries such as the NASA Astrophysics Data System permit the easy accumulation of a new type of bibliometric measure, the number of electronic accesses (``reads'') of individual articles. We explore various aspects of this new measure. We examine the obsolescence function as measured by actual reads, and show that it can be well fit by the sum of four exponentials with very different time constants. We compare the obsolescence function as measured by readership with the obsolescence function as measured by citations. We find that the citation function is proportional to the sum of two of the components of the readership function. This proves that the normative theory of citation is true in the mean. We further examine in detail the similarities and differences between the citation rate, the readership rate and the total citations for individual articles, and discuss some of the causes. Using the number of reads as a bibliometric measure for individuals, we introduce the read-cite diagram to provide a two-dimensional view of an individual's scientific productivity. We develop a simple model to account for an individual's reads and cites and use it to show that the position of a person in the read-cite diagram is a function of age, innate productivity, and work history. We show the age biases of both reads and cites, and develop two new bibliometric measures which have substantially less age bias than citations
Consensus in Correlated Random Topologies: Weights for Finite Time Horizon
Venue: arXiv cs.IT 2009
Year: 2009

We consider the weight design problem for the consensus algorithm under a finite time horizon. We assume that the underlying network is random where the links fail at each iteration with certain probability and the link failures can be spatially correlated. We formulate a family of weight design criteria (objective functions) that minimize n, n = 1,...,N (out of N possible) largest (slowest) eigenvalues of the matrix that describes the mean squared consensus error dynamics. We show that the objective functions are convex; hence, globally optimal weights (with respect to the design criteria) can be efficiently obtained. Numerical examples on large scale, sparse random networks with spatially correlated link failures show that: 1) weights obtained according to our criteria lead to significantly faster convergence than the choices available in the literature; 2) different design criteria that corresponds to different n, exhibits very interesting tradeoffs: faster transient performance leads to slower long time run performance and vice versa. Thus, n is a valuable degree of freedom and can be appropriately selected for the given time horizon.
Approximating Mathematical Semantic Web Services Using Approximation Formulas and Numerical Methods
Venue: arXiv cs.MS 2009
Year: 2009

Mathematical semantic web services are very useful in practice, but only a small number of research results are reported in this area. In this paper we present a method of obtaining an approximation of a mathematical semantic web service, from its semantic description, using existing mathematical semantic web services, approximation formulas, and numerical methods techniques. We also give a method for automatic comparison of two complexity functions. In addition, we present a method for classifying the numerical methods mathematical semantic web services from a library.
Hybrid Intrusion Detection and Prediction multiAgent System HIDPAS
Venue: arXiv cs.CR 2009
Year: 2009

This paper proposes an intrusion detection and prediction system based on uncertain and imprecise inference networks and its implementation. Giving a historic of sessions, it is about proposing a method of supervised learning doubled of a classifier permitting to extract the necessary knowledge in order to identify the presence or not of an intrusion in a session and in the positive case to recognize its type and to predict the possible intrusions that will follow it. The proposed system takes into account the uncertainty and imprecision that can affect the statistical data of the historic. The systematic utilization of an unique probability distribution to represent this type of knowledge supposes a too rich subjective information and risk to be in part arbitrary. One of the first objectives of this work was therefore to permit the consistency between the manner of which we represent information and information which we really dispose.
Local Shape of Generalized Offsets to Algebraic Curves
Venue: arXiv cs.SC 2009
Year: 2009

In this paper we study the local behavior of an algebraic curve under a geometric construction which is a variation of the usual offsetting construction, namely the {\it generalized} offsetting process (\cite {SS99}). More precisely, here we discuss when and how this geometric construction may cause local changes in the shape of an algebraic curve, and we compare our results with those obtained for the case of classical offsets (\cite{JGS07}). For these purposes, we use well-known notions of Differential Geometry, and also the notion of {\it local shape} introduced in \cite{JGS07}.
MACH: Fast Randomized Tensor Decompositions
Venue: arXiv cs.DS 2009
Year: 2009

Tensors naturally model many real world processes which generate multi-aspect data. Such processes appear in many different research disciplines, e.g, chemometrics, computer vision, psychometrics and neuroimaging analysis. Tensor decompositions such as the Tucker decomposition are used to analyze multi-aspect data and extract latent factors, which capture the multilinear data structure. Such decompositions are powerful mining tools, for extracting patterns from large data volumes. However, most frequently used algorithms for such decompositions involve the computationally expensive Singular Value Decomposition. In this paper we propose MACH, a new sampling algorithm to compute such decompositions. Our method is of significant practical value for tensor streams, such as environmental monitoring systems, IP traffic matrices over time, where large amounts of data are accumulated and the analysis is computationally intensive but also in "post-mortem" data analysis cases where the tensor does not fit in the available memory. We provide the theoretical analysis of our proposed method, and verify its efficacy in monitoring system applications.
Cartesian product of hypergraphs: properties and algorithms
Venue: arXiv cs.DM 2009
Year: 2009

Cartesian products of graphs have been studied extensively since the 1960s. They make it possible to decrease the algorithmic complexity of problems by using the factorization of the product. Hypergraphs were introduced as a generalization of graphs and the definition of Cartesian products extends naturally to them. In this paper, we give new properties and algorithms concerning coloring aspects of Cartesian products of hypergraphs. We also extend a classical prime factorization algorithm initially designed for graphs to connected conformal hypergraphs using 2-sections of hypergraphs.
Quasi-Proportional Mechanisms: Prior-free Revenue Maximization
Venue: arXiv cs.GT 2009
Year: 2009

Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of prior-free auction and focus on designing a simple mechanism that always allocates the item. Rather than designing sophisticated pricing methods like prior literature, we design better allocation methods. In particular, we propose quasi-proportional allocation methods in which the probability that an item is allocated to a bidder depends (quasi-proportionally) on the bids. We prove that corresponding games for both all-pay and winners-pay quasi-proportional mechanisms admit pure Nash equilibria and this equilibrium is unique. We also give an algorithm to compute this equilibrium in polynomial time. Further, we show that the revenue of the auctioneer is promisingly high compared to the ultimate, i.e., the highest value of any of the bidders, and show bounds on the revenue of equilibria both analytically, as well as using experiments for specific quasi-proportional functions. This is the first known revenue analysis for these natural mechanisms (including the special case of proportional mechanism which is common in network resource allocation problems).
Robust Distributed Estimation over Multiple Access Channels with Constant Modulus Signaling
Venue: arXiv cs.IT 2009
Year: 2009

A distributed estimation scheme where the sensors transmit with constant modulus signals over a multiple access channel is considered. The proposed estimator is shown to be strongly consistent for any sensing noise distribution in the i.i.d. case both for a per-sensor power constraint, and a total power constraint. When the distributions of the sensing noise are not identical, a bound on the variances is shown to establish strong consistency. The estimator is shown to be asymptotically normal with a variance (AsV) that depends on the characteristic function of the sensing noise. Optimization of the AsV is considered with respect to a transmission phase parameter for a variety of noise distributions exhibiting differing levels of impulsive behavior. The robustness of the estimator to impulsive sensing noise distributions such as those with positive excess kurtosis, or those that do not have finite moments is shown. The proposed estimator is favorably compared with the amplify and forward scheme under an impulsive noise scenario. The effect of fading is shown to not affect the consistency of the estimator, but to scale the asymptotic variance by a constant fading penalty depending on the fading statistics. Simulations corroborate our analytical results.
Guaranteed Rank Minimization via Singular Value Projection
Venue: arXiv cs.LG 2009
Year: 2009

Minimizing the rank of a matrix subject to affine constraints is a fundamental problem with many important applications in machine learning and statistics. In this paper we propose a simple and fast algorithm SVP (Singular Value Projection) for rank minimization with affine constraints (ARMP) and show that SVP recovers the minimum rank solution for affine constraints that satisfy the "restricted isometry property" and show robustness of our method to noise. Our results improve upon a recent breakthrough by Recht, Fazel and Parillo (RFP07) and Lee and Bresler (LB09) in three significant ways: 1) our method (SVP) is significantly simpler to analyze and easier to implement, 2) we give recovery guarantees under strictly weaker isometry assumptions 3) we give geometric convergence guarantees for SVP even in presense of noise and, as demonstrated empirically, SVP is significantly faster on real-world and synthetic problems. In addition, we address the practically important problem of low-rank matrix completion (MCP), which can be seen as a special case of ARMP. We empirically demonstrate that our algorithm recovers low-rank incoherent matrices from an almost optimal number of uniformly sampled entries. We make partial progress towards proving exact recovery and provide some intuition for the strong performance of SVP applied to matrix completion by showing a more restricted isometry property. Our algorithm outperforms existing methods, such as those of \cite{RFP07,CR08,CT09,CCS08,KOM09,LB09}, for ARMP and the matrix-completion problem by an order of magnitude and is also significantly more robust to noise.
Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions
Venue: arXiv cs.GT 2009
Year: 2009

We study the design of mechanisms in combinatorial auction domains. We focus on settings where the auction is repeated, motivated by auctions for licenses or advertising space. We consider models of agent behaviour in which they either apply common learning techniques to minimize the regret of their bidding strategies, or apply short-sighted best-response strategies. We ask: when can a black-box approximation algorithm for the base auction problem be converted into a mechanism that approximately preserves the original algorithm's approximation factor on average over many iterations? We present a general reduction for a broad class of algorithms when agents minimize external regret. We also present a new mechanism for the combinatorial auction problem that attains an $O(\sqrt{m})$ approximation on average when agents apply best-response dynamics.
Hierarchical Approach for Key Management in Mobile Ad hoc Networks
Venue: arXiv cs.CR 2009
Year: 2009

Mobile Ad-hoc Network (MANET) is a collection of autonomous nodes or terminals which communicate with each other by forming a multi-hop radio network and maintaining connectivity in a decentralized manner. The conventional security solutions to provide key management through accessing trusted authorities or centralized servers are infeasible for this new environment since mobile ad hoc networks are characterized by the absence of any infrastructure, frequent mobility, and wireless links. We propose a hierarchical group key management scheme that is hierarchical and fully distributed with no central authority and uses a simple rekeying procedure which is suitable for large and high mobility mobile ad hoc networks. The rekeying procedure requires only one round in our scheme and Chinese Remainder Theorem Diffie Hellman Group Diffie Hellmann and Burmester and Desmedt it is a constant 3 whereas in other schemes such as Distributed Logical Key Hierarchy and Distributed One Way Function Trees, it depends on the number of members. We reduce the energy consumption during communication of the keying materials by reducing the number of bits in the rekeying message. We show through analysis and simulations that our scheme has less computation, communication and energy consumption compared to the existing schemes.
From Requirements to code: an Architecture-centric Approach for producing Quality Systems
Venue: arXiv cs.SE 2009
Year: 2009

When engineering complex and distributed software and hardware systems (increasingly used in many sectors, such as manufacturing, aerospace, transportation, communication, energy, and health-care), quality has become a big issue, since failures can have economics consequences and can also endanger human life. Model-based specifications of a component-based system permit to explicitly model the structure and behaviour of components and their integration. In particular Software Architectures (SA) has been advocated as an effective means to produce quality systems. In this chapter by combining different technologies and tools for analysis and development, we propose an architecture-centric model-driven approach to validate required properties and to generate the system code. Functional requirements are elicited and used for identifying expected properties the architecture shall express. The architectural compliance to the properties is formally demonstrated, and the produced architectural model is used to automatically generate the Java code. Suitable transformations assure that the code is conforming to both structural and behavioural SA constraints. This chapter describes the process and discusses how some existing tools and languages can be exploited to support the approach.
Ranking via Arrow-Debreu Equilibrium
Venue: arXiv cs.GT 2009
Year: 2009

In this paper, we establish a connection between ranking theory and general equilibrium theory. First of all, we show that the ranking vector of PageRank or Invariant method is precisely the equilibrium of a special Cobb-Douglas market. This gives a natural economic interpretation for the PageRank or Invariant method. Furthermore, we propose a new ranking method, the CES ranking, which is minimally fair, strictly monotone and invariant to reference intensity, but not uniform or weakly additive.
The Gelfand-Pinsker Channel: Strong Converse and Upper Bound for the Reliability Function
Venue: arXiv cs.IT 2009
Year: 2009

We consider a Gelfand-Pinsker discrete memoryless channel (DMC) model and provide a strong converse for its capacity. The strong converse is then used to obtain an upper bound on the reliability function. Instrumental in our proofs is a new technical lemma which provides an upper bound for the rate of codes with codewords that are conditionally typical over large message dependent subsets of a typical set of state sequences. This technical result is a nonstraightforward analog of a known result for a DMC without states that provides an upper bound on the rate of a good code with codewords of a fixed type (to be found in, for instance, the Csiszar-Korner book).
Co-Channel Interference Cancellation in OFDM Networks using Coordinated Symbol Repetition and Soft Decision MLE CCI Canceler
Venue: arXiv cs.OH 2009
Year: 2009

In this paper, a new scheme of downlink co-channel interference (CCI) cancellation in OFDM cellular networks is introduced for users at the cell-edge. Coordinated symbol transmission between base stations (BS) is operated where the same symbol is transmitted from different BS on different sub-carriers. At the mobile station (MS) receiver, we introduce a soft decision maximum likelihood CCI canceler and a modified maximum ratio combining (M-MRC) to obtain an estimate of the transmitted symbols. Weights used in the combining method are derived from the channels coefficients between the cooperated BS and the MS. Simulations show that the proposed scheme works well under frequency-selective channels and frequency non-selective channels. A gain of 9 dB and 6 dB in SIR is obtained under multipath fading and flat-fading channels, respectively.
Design of asynchronous supervisors
Venue: arXiv cs.LO 2009
Year: 2009

One of the main drawbacks while implementing the interaction between a plant and a supervisor, synthesised by the supervisory control theory of \citeauthor{RW:1987}, is the inexact synchronisation. \citeauthor{balemiphdt} was the first to consider this problem, and the solutions given in his PhD thesis were in the domain of automata theory. Our goal is to address the issue of inexact synchronisation in a process algebra setting, because we get concepts like modularity and abstraction for free, which are useful to further analyze the synthesised system. In this paper, we propose four methods to check a closed loop system in an asynchronous setting such that it is branching bisimilar to the modified (asynchronous) closed loop system. We modify a given closed loop system by introducing buffers either in the plant models, the supervisor models, or the output channels of both supervisor and plant models, or in the input channels of both supervisor and plant models. A notion of desynchronisable closed loop system is introduced, which is a class of synchronous closed loop systems such that they are branching bisimilar to their corresponding asynchronous versions. Finally we study different case studies in an asynchronous setting and then try to summarise the observations (or conditions) which will be helpful in order to formulate a theory of desynchronisable closed loop systems.