OpenRaiser/Intern-Atlas huggingface dataset:
Connection state overhead in a dynamic linear network
Venue: arXiv cs.IT 2005
Year: 2005

We consider a dynamical linear network where nearest neighbours communicate via links whose states form binary (open/closed) valued independent and identically distributed Markov processes. Our main result is the tight information-theoretic lower bound on the network traffic required by the connection state overhead, or the information required for all nodes to know their connected neighbourhood. These results, and especially their possible generalisations to more realistic network models, could give us valuable understanding of the unavoidable protocol overheads in rapidly changing Ad hoc and sensor networks.
Balanced Allocation on Graphs
Venue: arXiv cs.DS 2005
Year: 2005

In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the graph is almost regular with degree $n^ε$, where $ε$ is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is $\log \log n + O(1/ε) + O(1)$. For general $Δ$-regular graphs, we show that the maximum load is $\log\log n + O(\frac{\log n}{\log (Δ/\log^4 n)}) + O(1)$ and also provide an almost matching lower bound of $\log \log n + \frac{\log n}{\log (Δ\log n)}$. V{ö}cking [Voc99] showed that the maximum bin size with $d$ choice load balancing can be further improved to $O(\log\log n /d)$ by breaking ties to the left. This requires $d$ random bin choices. We show that such bounds can be achieved by making only two random accesses and querying $d/2$ contiguous bins in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of $d/2$ consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is $O(\log\log n/d)$ with high probability.
An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling
Venue: arXiv cs.AI 2005
Year: 2005

Train timetabling is a difficult and very tightly constrained combinatorial problem that deals with the construction of train schedules. We focus on the particular problem of local reconstruction of the schedule following a small perturbation, seeking minimisation of the total accumulated delay by adapting times of departure and arrival for each train and allocation of resources (tracks, routing nodes, etc.). We describe a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic to gradually reconstruct the schedule by inserting trains one after the other following the permutation. This algorithm can be hybridised with ILOG commercial MIP programming tool CPLEX in a coarse-grained manner: the evolutionary part is used to quickly obtain a good but suboptimal solution and this intermediate solution is refined using CPLEX. Experimental results are presented on a large real-world case involving more than one million variables and 2 million constraints. Results are surprisingly good as the evolutionary algorithm, alone or hybridised, produces excellent solutions much faster than CPLEX alone.
Evolutionary Computing
Venue: arXiv cs.AI 2005
Year: 2005

Evolutionary computing (EC) is an exciting development in Computer Science. It amounts to building, applying and studying algorithms based on the Darwinian principles of natural selection. In this paper we briefly introduce the main concepts behind evolutionary computing. We present the main components all evolutionary algorithms (EA), sketch the differences between different types of EAs and survey application areas ranging from optimization, modeling and simulation to entertainment.
Parameters Affecting the Resilience of Scale-Free Networks to Random Failures
Venue: arXiv cs.NI 2005
Year: 2005

It is commonly believed that scale-free networks are robust to massive numbers of random node deletions. For example, Cohen et al. study scale-free networks including some which approximate the measured degree distribution of the Internet. Their results suggest that if each node in this network failed independently with probability 0.99, the remaining network would continue to have a giant component. In this paper, we show that a large and important subclass of scale-free networks are not robust to massive numbers of random node deletions for practical purposes. In particular, we study finite scale-free networks which have minimum node degree of 1 and a power-law degree distribution beginning with nodes of degree 1 (power-law networks). We show that, in a power-law network approximating the Internet's reported distribution, when the probability of deletion of each node is 0.5 only about 25% of the surviving nodes in the network remain connected in a giant component, and the giant component does not persist beyond a critical failure rate of 0.9. The new result is partially due to improved analytical accommodation of the large number of degree-0 nodes that result after node deletions. Our results apply to finite power-law networks with a wide range of power-law exponents, including Internet-like networks. We give both analytical and empirical evidence that such networks are not generally robust to massive random node deletions.
How to make the top ten: Approximating PageRank from in-degree
Venue: arXiv cs.IR 2005
Year: 2005

PageRank has become a key element in the success of search engines, allowing to rank the most important hits in the top screen of results. One key aspect that distinguishes PageRank from other prestige measures such as in-degree is its global nature. From the information provider perspective, this makes it difficult or impossible to predict how their pages will be ranked. Consequently a market has emerged for the optimization of search engine results. Here we study the accuracy with which PageRank can be approximated by in-degree, a local measure made freely available by search engines. Theoretical and empirical analyses lead to conclude that given the weak degree correlations in the Web link graph, the approximation can be relatively accurate, giving service and information providers an effective new marketing tool.
Trellis Pruning for Peak-to-Average Power Ratio Reduction
Venue: arXiv cs.IT 2005
Year: 2005

This paper introduces a new trellis pruning method which uses nonlinear convolutional coding for peak-to-average power ratio (PAPR) reduction of filtered QPSK and 16-QAM modulations. The Nyquist filter is viewed as a convolutional encoder that controls the analog waveforms of the filter output directly. Pruning some edges of the encoder trellis can effectively reduce the PAPR. The only tradeoff is a slightly lower channel capacity and increased complexity. The paper presents simulation results of the pruning action and the resulting PAPR, and also discusses the decoding algorithm and the capacity of the filtered and pruned QPSK and 16-QAM modulations on the AWGN channel. Simulation results show that the pruning method reduces the PAPR significantly without much damage to capacity.
The Secret Key-Private Key Capacity Region for Three Terminals
Venue: arXiv cs.IT 2005
Year: 2005

We consider a model for secrecy generation, with three terminals, by means of public interterminal communication, and examine the problem of characterizing all the rates at which all three terminals can generate a ``secret key,'' and -- simultaneously -- two designated terminals can generate a ``private key'' which is effectively concealed from the remaining terminal; both keys are also concealed from an eavesdropper that observes the public communication. Inner and outer bounds for the ``secret key--private key capacity region'' are derived. Under a certain special condition, these bounds coincide to yield the (exact) secret key--private key capacity region.
Mining Cellular Automata DataBases throug PCA Models
Venue: arXiv cs.DM 2005
Year: 2005

Cellular Automata are discrete dynamical systems that evolve following simple and local rules. Despite of its local simplicity, knowledge discovery in CA is a NP problem. This is the main motivation for using data mining techniques for CA study. The Principal Component Analysis (PCA) is a useful tool for data mining because it provides a compact and optimal description of data sets. Such feature have been explored to compute the best subspace which maximizes the projection of the I/O patterns of CA onto the principal axis. The stability of the principal components against the input patterns is the main result of this approach. In this paper we perform such analysis but in the presence of noise which randomly reverses the CA output values with probability $p$. As expected, the number of principal components increases when the pattern size is increased. However, it seems to remain stable when the pattern size is unchanged but the noise intensity gets larger. We describe our experiments and point out further works using KL transform theory and parameter sensitivity analysis.
Effects of Initial Stance of Quadruped Trotting on Walking Stability
Venue: arXiv cs.RO 2005
Year: 2005

It is very important for quadruped walking machine to keep its stability in high speed walking. It has been indicated that moment around the supporting diagonal line of quadruped in trotting gait largely influences walking stability. In this paper, moment around the supporting diagonal line of quadruped in trotting gait is modeled and its effects on body attitude are analyzed. The degree of influence varies with different initial stances of quadruped and we get the optimal initial stance of quadruped in trotting gait with maximal walking stability. Simulation results are presented. Keywords: quadruped, trotting, attitude, walking stability.
Stochastic Process Semantics for Dynamical Grammar Syntax: An Overview
Venue: arXiv cs.AI 2005
Year: 2005

We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is mapped to semantics given in terms of a ring of operators, so that grammatical composition corresponds to operator addition or multiplication. The operators are generators for the time-evolution of stochastic processes. Within this modeling framework one can express data clustering models, logic programs, ordinary and stochastic differential equations, graph grammars, and stochastic chemical reaction kinetics. This mathematical formulation connects these apparently distant fields to one another and to mathematical methods from quantum field theory and operator algebra.
The Availability and Persistence of Web References in D-Lib Magazine
Venue: arXiv cs.DL 2005
Year: 2005

We explore the availability and persistence of URLs cited in articles published in D-Lib Magazine. We extracted 4387 unique URLs referenced in 453 articles published from July 1995 to August 2004. The availability was checked three times a week for 25 weeks from September 2004 to February 2005. We found that approximately 28% of those URLs failed to resolve initially, and 30% failed to resolve at the last check. A majority of the unresolved URLs were due to 404 (page not found) and 500 (internal server error) errors. The content pointed to by the URLs was relatively stable; only 16% of the content registered more than a 1 KB change during the testing period. We explore possible factors which may cause a URL to fail by examining its age, path depth, top-level domain and file extension. Based on the data collected, we found the half-life of a URL referenced in a D-Lib Magazine article is approximately 10 years. We also found that URLs were more likely to be unavailable if they pointed to resources in the .net, .edu or country-specific top-level domain, used non-standard ports (i.e., not port 80), or pointed to resources with uncommon or deprecated extensions (e.g., .shtml, .ps, .txt).
The SL synchronous language, revisited
Venue: arXiv cs.PL 2005
Year: 2005

We revisit the SL synchronous programming model introduced by Boussinot and De Simone (IEEE, Trans. on Soft. Eng., 1996). We discuss an alternative design of the model including thread spawning and recursive definitions and we explore some basic properties of the revised model: determinism, reactivity, CPS translation to a tail recursive form, computational expressivity, and a compositional notion of program equivalence.
The Signed Distance Function: A New Tool for Binary Classification
Venue: arXiv cs.LG 2005
Year: 2005

From a geometric perspective most nonlinear binary classification algorithms, including state of the art versions of Support Vector Machine (SVM) and Radial Basis Function Network (RBFN) classifiers, and are based on the idea of reconstructing indicator functions. We propose instead to use reconstruction of the signed distance function (SDF) as a basis for binary classification. We discuss properties of the signed distance function that can be exploited in classification algorithms. We develop simple versions of such classifiers and test them on several linear and nonlinear problems. On linear tests accuracy of the new algorithm exceeds that of standard SVM methods, with an average of 50% fewer misclassifications. Performance of the new methods also matches or exceeds that of standard methods on several nonlinear problems including classification of benchmark diagnostic micro-array data sets.
Which n-Venn diagrams can be drawn with convex k-gons?
Venue: arXiv cs.CG 2005
Year: 2005

We establish a new lower bound for the number of sides required for the component curves of simple Venn diagrams made from polygons. Specifically, for any n-Venn diagram of convex k-gons, we prove that k >= (2^n - 2 - n) / (n (n-2)). In the process we prove that Venn diagrams of seven curves, simple or not, cannot be formed from triangles. We then give an example achieving the new lower bound of a (simple, symmetric) Venn diagram of seven quadrilaterals. Previously Grunbaum had constructed a 7-Venn diagram of non-convex 5-gons [``Venn Diagrams II'', Geombinatorics 2:25-31, 1992].
Self-Regulated Artificial Ant Colonies on Digital Image Habitats
Venue: arXiv cs.MA 2005
Year: 2005

Artificial life models, swarm intelligent and evolutionary computation algorithms are usually built on fixed size populations. Some studies indicate however that varying the population size can increase the adaptability of these systems and their capability to react to changing environments. In this paper we present an extended model of an artificial ant colony system designed to evolve on digital image habitats. We will show that the present swarm can adapt the size of the population according to the type of image on which it is evolving and reacting faster to changing images, thus converging more rapidly to the new desired regions, regulating the number of his image foraging agents. Finally, we will show evidences that the model can be associated with the Mathematical Morphology Watershed algorithm to improve the segmentation of digital grey-scale images. KEYWORDS: Swarm Intelligence, Perception and Image Processing, Pattern Recognition, Mathematical Morphology, Social Cognitive Maps, Social Foraging, Self-Organization, Distributed Search.
The Physical Foundation of Human Mind and a New Theory of Investment
Venue: arXiv cs.IT 2005
Year: 2005

This paper consists of two parts. In the first part, we develop a new information theory, in which it is not a coincidence that information and physical entropy share the same mathematical formula. It is an adaptation of mind to help search for resources. We then show that psychological patterns either reflect the constraints of physical laws or are evolutionary adaptations to efficiently process information and to increase the chance of survival in the environment of our evolutionary past. In the second part, we demonstrate that the new information theory provides the foundation to understand market behavior. One fundamental result from the information theory is that information is costly. In general, information with higher value is more costly. Another fundamental result from the information theory is that the amount of information one can receive is the amount of information generated minus equivocation. The level of equivocation, which is the measure of information asymmetry, is determined by the correlation between the source of information and the receiver of information. In general, how much information one can receive depends on the background knowledge of the receiver. The difference in cost different investors are willing to pay for information and the difference in background knowledge about a particular information causes the heterogeneity in information processing by the investment public, which is the main reason of the price and volume patterns observed in the market. Many assumptions in some of the recent models on behavioral finance can be derived naturally from this theory.
Termination Analysis of General Logic Programs for Moded Queries: A Dynamic Approach
Venue: arXiv cs.LO 2005
Year: 2005

The termination problem of a logic program can be addressed in either a static or a dynamic way. A static approach performs termination analysis at compile time, while a dynamic approach characterizes and tests termination of a logic program by applying a loop checking technique. In this paper, we present a novel dynamic approach to termination analysis for general logic programs with moded queries. We address several interesting questions, including how to formulate an SLDNF-derivation for a moded query, how to characterize an infinite SLDNF-derivation with a moded query, and how to apply a loop checking mechanism to cut infinite SLDNF-derivations for the purpose of termination analysis. The proposed approach is very powerful and useful. It can be used (1) to test if a logic program terminates for a given concrete or moded query, (2) to test if a logic program terminates for all concrete or moded queries, and (3) to find all (most general) concrete/moded queries that are most likely terminating (or non-terminating).
Solving Partial Order Constraints for LPO Termination
Venue: arXiv cs.PL 2005
Year: 2005

This paper introduces a new kind of propositional encoding for reasoning about partial orders. The symbols in an unspecified partial order are viewed as variables which take integer values and are interpreted as indices in the order. For a partial order statement on n symbols each index is represented in log2 n propositional variables and partial order constraints between symbols are modeled on the bit representations. We illustrate the application of our approach to determine LPO termination for term rewrite systems. Experimental results are unequivocal, indicating orders of magnitude speedups in comparison with current implementations for LPO termination. The proposed encoding is general and relevant to other applications which involve propositional reasoning about partial orders.
The Fibonacci Sequence Mod m
Venue: arXiv cs.OH 2005
Year: 2005

This paper proposes a computational method for obtaining the length of the cycle that arises from the Fibonacci series taken mod m (some number) and mod p (some prime number).
Meaningful Information
Venue: arXiv cs.CC 2006
Year: 2006

The information in an individual finite object (like a binary string) is commonly measured by its Kolmogorov complexity. One can divide that information into two parts: the information accounting for the useful regularity present in the object and the information accounting for the remaining accidental information. There can be several ways (model classes) in which the regularity is expressed. Kolmogorov has proposed the model class of finite sets, generalized later to computable probability mass functions. The resulting theory, known as Algorithmic Statistics, analyzes the algorithmic sufficient statistic when the statistic is restricted to the given model class. However, the most general way to proceed is perhaps to express the useful information as a recursive function. The resulting measure has been called the ``sophistication'' of the object. We develop the theory of recursive functions statistic, the maximum and minimum value, the existence of absolutely nonstochastic objects (that have maximal sophistication--all the information in them is meaningful and there is no residual randomness), determine its relation with the more restricted model classes of finite sets, and computable probability distributions, in particular with respect to the algorithmic (Kolmogorov) minimal sufficient statistic, the relation to the halting problem and further algorithmic properties.
Architecture of an Open-Sourced, Extensible Data Warehouse Builder: InterBase 6 Data Warehouse Builder (IB-DWB)
Venue: arXiv cs.DB 2006
Year: 2006

We report the development of an open-sourced data warehouse builder, InterBase Data Warehouse Builder (IB-DWB), based on Borland InterBase 6 Open Edition Database Server. InterBase 6 is used for its low maintenance and small footprint. IB-DWB is designed modularly and consists of 5 main components, Data Plug Platform, Discoverer Platform, Multi-Dimensional Cube Builder, and Query Supporter, bounded together by a Kernel. It is also an extensible system, made possible by the Data Plug Platform and the Discoverer Platform. Currently, extensions are only possible via dynamic linked-libraries (DLLs). Multi-Dimensional Cube Builder represents a basal mean of data aggregation. The architectural philosophy of IB-DWB centers around providing a base platform that is extensible, which is functionally supported by expansion modules. IB-DWB is currently being hosted by sourceforge.net (Project Unix Name: ib-dwb), licensed under GNU General Public License, Version 2.
Uniform test of algorithmic randomness over a general space
Venue: arXiv cs.CC 2006
Year: 2006

The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Loef), and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. - We allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). - The uniform test (deficiency of randomness) d_P(x) (depending both on the outcome x and the measure P should be defined in a general and natural way. - We see which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as "deficiency of independence. - The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).
NLOMJ--Natural Language Object Model in Java
Venue: arXiv cs.CL 2006
Year: 2006

In this paper we present NLOMJ--a natural language object model in Java with English as the experiment language. This modal describes the grammar elements of any permissible expression in a natural language and their complicated relations with each other with the concept "Object" in OOP(Object Oriented Programming). Directly mapped to the syntax and semantics of the natural language, it can be used in information retrieval as a linguistic method. Around the UML diagram of the NLOMJ the important classes(Sentence, Clause and Phrase) and their sub classes are introduced and their syntactic and semantic meanings are explained.