OpenRaiser/Intern-Atlas huggingface dataset:
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
Venue: arXiv cs.CC 2010
Year: 2010

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that protocols for AUGMENTED-INDEX may violate the "rectangle property" due to the inherent input sharing. Second, we use these bounds to resolve an open problem of Magniez, Mathieu and Nayak [STOC, 2010] that asked about the multi-pass complexity of recognizing Dyck languages. This results in a natural separation between the standard multi-pass model and the multi-pass model that permits reverse passes. Third, we present the first passive memory checkers that verify the interaction transcripts of priority queues, stacks, and double-ended queues. We obtain tight upper and lower bounds for these problems, thereby addressing an important sub-class of the memory checking framework of Blum et al. [Algorithmica, 1994].
Generation and Interpretation of Temporal Decision Rules
Venue: arXiv cs.LG 2010
Year: 2010

We present a solution to the problem of understanding a system that produces a sequence of temporally ordered observations. Our solution is based on generating and interpreting a set of temporal decision rules. A temporal decision rule is a decision rule that can be used to predict or retrodict the value of a decision attribute, using condition attributes that are observed at times other than the decision attribute's time of observation. A rule set, consisting of a set of temporal decision rules with the same decision attribute, can be interpreted by our Temporal Investigation Method for Enregistered Record Sequences (TIMERS) to signify an instantaneous, an acausal or a possibly causal relationship between the condition attributes and the decision attribute. We show the effectiveness of our method, by describing a number of experiments with both synthetic and real temporal data.
Improving Update Summarization by Revisiting the MMR Criterion
Venue: arXiv cs.IR 2010
Year: 2010

This paper describes a method for multi-document update summarization that relies on a double maximization criterion. A Maximal Marginal Relevance like criterion, modified and so called Smmr, is used to select sentences that are close to the topic and at the same time, distant from sentences used in already read documents. Summaries are then generated by assembling the high ranked material and applying some ruled-based linguistic post-processing in order to obtain length reduction and maintain coherency. Through a participation to the Text Analysis Conference (TAC) 2008 evaluation campaign, we have shown that our method achieves promising results.
Adaptive Single-Trial Error/Erasure Decoding for Binary Codes
Venue: arXiv cs.IT 2010
Year: 2010

We investigate adaptive single-trial error/erasure decoding of binary codes whose decoder is able to correct e errors and t erasures if le+t<=d-1. Thereby, d is the minimum Hamming distance of the code and 1<l<=2 is the tradeoff parameter between errors and erasures. The error/erasure decoder allows to exploit soft information by treating a set of most unreliable received symbols as erasures. The obvious question here is, how this erasing should be performed, i.e. how the unreliable symbols which must be erased to obtain the smallest possible residual codeword error probability are determined. In a previous paper, we answer this question for the case of fixed erasing, where only the channel state and not the individual symbol reliabilities are taken into consideration. In this paper, we address the adaptive case, where the optimal erasing strategy is determined for every given received vector.
On the precision attainable with various floating-point number systems
Venue: arXiv cs.NA 2010
Year: 2010

For scientific computations on a digital computer the set of real number is usually approximated by a finite set F of "floating-point" numbers. We compare the numerical accuracy possible with difference choices of F having approximately the same range and requiring the same word length. In particular, we compare different choices of base (or radix) in the usual floating-point systems. The emphasis is on the choice of F, not on the details of the number representation or the arithmetic, but both rounded and truncated arithmetic are considered. Theoretical results are given, and some simulations of typical floating-point computations (forming sums, solving systems of linear equations, finding eigenvalues) are described. If the leading fraction bit of a normalized base 2 number is not stored explicitly (saving a bit), and the criterion is to minimize the mean square roundoff error, then base 2 is best. If unnormalized numbers are allowed, so the first bit must be stored explicitly, then base 4 (or sometimes base 8) is the best of the usual systems.
On Factor Universality in Symbolic Spaces
Venue: arXiv cs.DM 2010
Year: 2010

The study of factoring relations between subshifts or cellular automata is central in symbolic dynamics. Besides, a notion of intrinsic universality for cellular automata based on an operation of rescaling is receiving more and more attention in the literature. In this paper, we propose to study the factoring relation up to rescalings, and ask for the existence of universal objects for that simulation relation. In classical simulations of a system S by a system T, the simulation takes place on a specific subset of configurations of T depending on S (this is the case for intrinsic universality). Our setting, however, asks for every configurations of T to have a meaningful interpretation in S. Despite this strong requirement, we show that there exists a cellular automaton able to simulate any other in a large class containing arbitrarily complex ones. We also consider the case of subshifts and, using arguments from recursion theory, we give negative results about the existence of universal objects in some classes.
PCA 4 DCA: The Application Of Principal Component Analysis To The Dendritic Cell Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

As one of the newest members in the field of artificial immune systems (AIS), the Dendritic Cell Algorithm (DCA) is based on behavioural models of natural dendritic cells (DCs). Unlike other AIS, the DCA does not rely on training data, instead domain or expert knowledge is required to predetermine the mapping between input signals from a particular instance to the three categories used by the DCA. This data preprocessing phase has received the criticism of having manually over-?tted the data to the algorithm, which is undesirable. Therefore, in this paper we have attempted to ascertain if it is possible to use principal component analysis (PCA) techniques to automatically categorise input data while still generating useful and accurate classication results. The integrated system is tested with a biometrics dataset for the stress recognition of automobile drivers. The experimental results have shown the application of PCA to the DCA for the purpose of automated data preprocessing is successful.
Learning Better Context Characterizations: An Intelligent Information Retrieval Approach
Venue: arXiv cs.IR 2010
Year: 2010

This paper proposes an incremental method that can be used by an intelligent system to learn better descriptions of a thematic context. The method starts with a small number of terms selected from a simple description of the topic under analysis and uses this description as the initial search context. Using these terms, a set of queries are built and submitted to a search engine. New documents and terms are used to refine the learned vocabulary. Evaluations performed on a large number of topics indicate that the learned vocabulary is much more effective than the original one at the time of constructing queries to retrieve relevant material.
Lower bounds for the error decay incurred by coarse quantization schemes
Venue: arXiv cs.IT 2010
Year: 2010

Several analog-to-digital conversion methods for bandlimited signals used in applications, such as Sigma Delta quantization schemes, employ coarse quantization coupled with oversampling. The standard mathematical model for the error accrued from such methods measures the performance of a given scheme by the rate at which the associated reconstruction error decays as a function of the oversampling ratio L > 1. It was recently shown that exponential accuracy of the form O(2(-r L)) can be achieved by appropriate one-bit Sigma Delta modulation schemes. However, the best known achievable rate constants r in this setting differ significantly from the general information theoretic lower bound. In this paper, we provide the first lower bound specific to coarse quantization, thus narrowing the gap between existing upper and lower bounds. In particular, our results imply a quantitative correspondence between the maximal signal amplitude and the best possible error decay rate. Our method draws from the theory of large deviations.
An Optimized Weighted Association Rule Mining On Dynamic Content
Venue: arXiv cs.DB 2010
Year: 2010

Association rule mining aims to explore large transaction databases for association rules. Classical Association Rule Mining (ARM) model assumes that all items have the same significance without taking their weight into account. It also ignores the difference between the transactions and importance of each and every itemsets. But, the Weighted Association Rule Mining (WARM) does not work on databases with only binary attributes. It makes use of the importance of each itemset and transaction. WARM requires each item to be given weight to reflect their importance to the user. The weights may correspond to special promotions on some products, or the profitability of different items. This research work first focused on a weight assignment based on a directed graph where nodes denote items and links represent association rules. A generalized version of HITS is applied to the graph to rank the items, where all nodes and links are allowed to have weights. This research then uses enhanced HITS algorithm by developing an online eigenvector calculation method that can compute the results of mutual reinforcement voting in case of frequent updates. For Example in Share Market Shares price may go down or up. So we need to carefully watch the market and our association rule mining has to produce the items that have undergone frequent changes. These are done by estimating the upper bound of perturbation and postponing of the updates whenever possible. Next we prove that enhanced algorithm is more efficient than the original HITS under the context of dynamic data.
Scopus's Source Normalized Impact per Paper (SNIP) versus a Journal Impact Factor based on Fractional Counting of Citations
Venue: arXiv cs.DL 2010
Year: 2010

Impact factors (and similar measures such as the Scimago Journal Rankings) suffer from two problems: (i) citation behavior varies among fields of science and therefore leads to systematic differences, and (ii) there are no statistics to inform us whether differences are significant. The recently introduced SNIP indicator of Scopus tries to remedy the first of these two problems, but a number of normalization decisions are involved which makes it impossible to test for significance. Using fractional counting of citations-based on the assumption that impact is proportionate to the number of references in the citing documents-citations can be contextualized at the paper level and aggregated impacts of sets can be tested for their significance. It can be shown that the weighted impact of Annals of Mathematics (0.247) is not so much lower than that of Molecular Cell (0.386) despite a five-fold difference between their impact factors (2.793 and 13.156, respectively).
Consensus over a Random Network Generated by i.i.d. Stochastic Matrices
Venue: arXiv cs.NI 2010
Year: 2010

Our goal is to find a necessary and sufficient condition on the consensus over a random network, generated by i.i.d. stochastic matrices. We show that the consensus problem in three different convergence modes (almost surely, in probability, and in L1) are equivalent, thus have the same necessary and sufficient condition. We obtain the necessary and sufficient condition through the stability in a projected subspace.
A Gibbs distribution that learns from GA dynamics
Venue: arXiv cs.NE 2010
Year: 2010

A general procedure of average-case performance evaluation for population dynamics such as genetic algorithms (GAs) is proposed and its validity is numerically examined. We introduce a learning algorithm of Gibbs distributions from training sets which are gene configurations (strings) generated by GA in order to figure out the statistical properties of GA from the view point of thermodynamics. The learning algorithm is constructed by means of minimization of the Kullback-Leibler information between a parametric Gibbs distribution and the empirical distribution of gene configurations. The formulation is applied to the solvable probabilistic models having multi-valley energy landscapes, namely, the spin glass chain and the Sherrington-Kirkpatrick model. By using computer simulations, we discuss the asymptotic behaviour of the effective temperature scheduling and the residual energy induced by the GA dynamics.
An Algorithm for Odd Graceful Labeling of the Union of Paths and Cycles
Venue: arXiv cs.IT 2010
Year: 2010

In 1991, Gnanajothi [4] proved that the path graph P_n with n vertex and n-1 edge is odd graceful, and the cycle graph C_m with m vertex and m edges is odd graceful if and only if m even, she proved the cycle graph is not graceful if m odd. In this paper, firstly, we studied the graph C_m $\cup$ P_m when m = 4, 6,8,10 and then we proved that the graph C_ $\cup$ P_n is odd graceful if m is even. Finally, we described an algorithm to label the vertices and the edges of the vertex set V(C_m $\cup$ P_n) and the edge set E(C_m $\cup$ P_n).
Artificial Immune Systems Metaphor for Agent Based Modeling of Crisis Response Operations
Venue: arXiv cs.MA 2010
Year: 2010

Crisis response requires information intensive efforts utilized for reducing uncertainty, calculating and comparing costs and benefits, and managing resources in a fashion beyond those regularly available to handle routine problems. This paper presents an Artificial Immune Systems (AIS) metaphor for agent based modeling of crisis response operations. The presented model proposes integration of hybrid set of aspects (multi-agent systems, built-in defensive model of AIS, situation management, and intensity-based learning) for crisis response operations. In addition, the proposed response model is applied on the spread of pandemic influenza in Egypt as a case study.
A Global Optimisation Toolbox for Massively Parallel Engineering Optimisation
Venue: arXiv cs.DC 2010
Year: 2010

A software platform for global optimisation, called PaGMO, has been developed within the Advanced Concepts Team (ACT) at the European Space Agency, and was recently released as an open-source project. PaGMO is built to tackle high-dimensional global optimisation problems, and it has been successfully used to find solutions to real-life engineering problems among which the preliminary design of interplanetary spacecraft trajectories - both chemical (including multiple flybys and deep-space maneuvers) and low-thrust (limited, at the moment, to single phase trajectories), the inverse design of nano-structured radiators and the design of non-reactive controllers for planetary rovers. Featuring an arsenal of global and local optimisation algorithms (including genetic algorithms, differential evolution, simulated annealing, particle swarm optimisation, compass search, improved harmony search, and various interfaces to libraries for local optimisation such as SNOPT, IPOPT, GSL and NLopt), PaGMO is at its core a C++ library which employs an object-oriented architecture providing a clean and easily-extensible optimisation framework. Adoption of multi-threaded programming ensures the efficient exploitation of modern multi-core architectures and allows for a straightforward implementation of the island model paradigm, in which multiple populations of candidate solutions asynchronously exchange information in order to speed-up and improve the optimisation process. In addition to the C++ interface, PaGMO's capabilities are exposed to the high-level language Python, so that it is possible to easily use PaGMO in an interactive session and take advantage of the numerous scientific Python libraries available.
Motif Detection Inspired by Immune Memory
Venue: arXiv cs.AI 2010
Year: 2010

The search for patterns or motifs in data represents an area of key interest to many researchers. In this paper we present the Motif Tracking Algorithm, a novel immune inspired pattern identification tool that is able to identify variable length unknown motifs which repeat within time series data. The algorithm searches from a completely neutral perspective that is independent of the data being analysed and the underlying motifs. In this paper we test the flexibility of the motif tracking algorithm by applying it to the search for patterns in two industrial data sets. The algorithm is able to identify a population of motifs successfully in both cases, and the value of these motifs is discussed.
Finite Optimal Control for Time-Bounded Reachability in CTMDPs and Continuous-Time Markov Games
Venue: arXiv cs.FL 2010
Year: 2010

We establish the existence of optimal scheduling strategies for time-bounded reachability in continuous-time Markov decision processes, and of co-optimal strategies for continuous-time Markov games. Furthermore, we show that optimal control does not only exist, but has a surprisingly simple structure: The optimal schedulers from our proofs are deterministic and timed-positional, and the bounded time can be divided into a finite number of intervals, in which the optimal strategies are positional. That is, we demonstrate the existence of finite optimal control. Finally, we show that these pleasant properties of Markov decision processes extend to the more general class of continuous-time Markov games, and that both early and late schedulers show this behaviour.
Database Security: A Historical Perspective
Venue: arXiv cs.DB 2010
Year: 2010

The importance of security in database research has greatly increased over the years as most of critical functionality of the business and military enterprises became digitized. Database is an integral part of any information system and they often hold sensitive data. The security of the data depends on physical security, OS security and DBMS security. Database security can be compromised by obtaining sensitive data, changing data or degrading availability of the database. Over the last 30 years the information technology environment have gone through many changes of evolution and the database research community have tried to stay a step ahead of the upcoming threats to the database security. The database research community has thoughts about these issues long before they were address by the implementations. This paper will examine the different topics pertaining to database security and see the adaption of the research to the changing environment. Some short term database research trends will be ascertained at the conclusion.
Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions
Venue: arXiv cs.IT 2010
Year: 2010

In this two-part paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. We show that the constructions of certain types of optical queues, including linear compressors, linear decompressors, and 2-to-1 FIFO multiplexers, under a simple packet routing scheme and under the constraint of a limited number of recirculations can be transformed into equivalent integer representation problems under a corresponding constraint. Given $M$ and $k$, the problem of finding an \emph{optimal} construction, in the sense of maximizing the maximum delay (resp., buffer size), among our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers) is equivalent to the problem of finding an optimal sequence ${\dbf^*}_1^M$ in $\Acal_M$ (resp., $\Bcal_M$) such that $B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in \Acal_M}B(\dbf_1^M;k)$ (resp., $B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in \Bcal_M}B(\dbf_1^M;k)$), where $\Acal_M$ (resp., $\Bcal_M$) is the set of all sequences of fiber delays allowed in our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers). In Part I, we propose a class of \emph{greedy} constructions of linear compressors/decompressors and 2-to-1 FIFO multiplexers by specifying a class $\Gcal_{M,k}$ of sequences such that $\Gcal_{M,k}\subseteq \Bcal_M\subseteq \Acal_M$ and each sequence in $\Gcal_{M,k}$ is obtained recursively in a greedy manner. We then show that every optimal construction must be a greedy construction. In Part II, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s).
A General Framework for Graph Sparsification
Venue: arXiv cs.DS 2010
Year: 2010

Given a weighted graph $G$ and an error parameter $ε> 0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_ε$ (containing O(n\log n) edges in expectation) with the following property: the weight of every cut in $G_ε$ is within a factor of $(1\pm ε)$ of the weight of the corresponding cut in $G$. We provide a generic framework that sets out sufficient conditions for any particular sampling scheme to result in good sparsifiers, and obtain a set of results by simple instantiations of this framework. The results we obtain include the following: (1) We improve the time complexity of graph sparsification from O(m\log^3 n) to O(m + n\log^4 n) for graphs with polynomial edge weights. (2) We improve the time complexity of graph sparsification from O(m\log^3 n) to O(m\log^2 n) for graphs with arbitrary edge weights. (3) If the size of the sparsifier is allowed to be O(n\log^2 n/ε^2) instead of O(n\log n/ε^2), we improve the time complexity of sparsification to O(m) for graphs with polynomial edge weights. (4) We show that sampling using standard connectivities results in good sparsifiers, thus resolving an open question of Benczur and Karger. As a corollary, we give a simple proof of (a slightly weaker version of) a result due to Spielman and Srivastava showing that sampling using effective resistances produces good sparsifiers. (5) We give a simple proof showing that sampling using strong connectivities results in good sparsifiers, a result obtained previously using a more involved proof by Benczur and Karger. A key ingredient of our proofs is a generalization of bounds on the number of small cuts in an undirected graph due to Karger; this generalization might be of independent interest.
Operator-oriented programming: a new paradigm for implementing window interfaces and parallel algorithms
Venue: arXiv cs.PL 2010
Year: 2010

We present a new programming paradigm which can be useful, in particular, for implementing window interfaces and parallel algorithms. This paradigm allows a user to define operators which can contain nested operators. The new paradigm is called operator-oriented. One of the goals of this paradigm is to escape the complexity of objects definitions inherent in many object-oriented languages and to move to transparent algorithms definitions.