OpenRaiser/Intern-Atlas huggingface dataset:
Bucketing Coding and Information Theory for the Statistical High Dimensional Nearest Neighbor Problem
Venue: arXiv cs.IT 2008
Year: 2008

Consider the problem of finding high dimensional approximate nearest neighbors, where the data is generated by some known probabilistic model. We will investigate a large natural class of algorithms which we call bucketing codes. We will define bucketing information, prove that it bounds the performance of all bucketing codes, and that the bucketing information bound can be asymptotically attained by randomly constructed bucketing codes. For example suppose we have n Bernoulli(1/2) very long (length d-->infinity) sequences of bits. Let n-2m sequences be completely independent, while the remaining 2m sequences are composed of m independent pairs. The interdependence within each pair is that their bits agree with probability 1/2<p<=1. It is well known how to find most pairs with high probability by performing order of n^{\log_{2}2/p} comparisons. We will see that order of n^{1/p+ε} comparisons suffice, for any ε>0. Moreover if one sequence out of each pair belongs to a a known set of n^{(2p-1)^{2}-ε} sequences, than pairing can be done using order n comparisons!
Bicycle cycles and mobility patterns - Exploring and characterizing data from a community bicycle program
Venue: arXiv cs.CY 2008
Year: 2008

This paper provides an analysis of human mobility data in an urban area using the amount of available bikes in the stations of the community bicycle program Bicing in Barcelona. The data was obtained by periodic mining of a KML-file accessible through the Bicing website. Although in principle very noisy, after some preprocessing and filtering steps the data allows to detect temporal patterns in mobility as well as identify residential, university, business and leisure areas of the city. The results lead to a proposal for an improvement of the bicing website, including a prediction of the number of available bikes in a certain station within the next minutes/hours. Furthermore a model for identifying the most probable routes between stations is briefly sketched.
Randomization Adaptive Self-Stabilization
Venue: arXiv cs.DC 2008
Year: 2008

We present a scheme to convert self-stabilizing algorithms that use randomization during and following convergence to self-stabilizing algorithms that use randomization only during convergence. We thus reduce the number of random bits from an infinite number to a bounded number. The scheme is applicable to the cases in which there exits a local predicate for each node, such that global consistency is implied by the union of the local predicates. We demonstrate our scheme over the token circulation algorithm of Herman and the recent constant time Byzantine self-stabilizing clock synchronization algorithm by Ben-Or, Dolev and Hoch. The application of our scheme results in the first constant time Byzantine self-stabilizing clock synchronization algorithm that uses a bounded number of random bits.
XQuery Join Graph Isolation
Venue: arXiv cs.DB 2008
Year: 2008

A purely relational account of the true XQuery semantics can turn any relational database system into an XQuery processor. Compiling nested expressions of the fully compositional XQuery language, however, yields odd algebraic plan shapes featuring scattered distributions of join operators that currently overwhelm commercial SQL query optimizers. This work rewrites such plans before submission to the relational database back-end. Once cast into the shape of join graphs, we have found off-the-shelf relational query optimizers--the B-tree indexing subsystem and join tree planner, in particular--to cope and even be autonomously capable of "reinventing" advanced processing strategies that have originally been devised specifically for the XQuery domain, e.g., XPath step reordering, axis reversal, and path stitching. Performance assessments provide evidence that relational query engines are among the most versatile and efficient XQuery processors readily available today.
A Novel Clustering Algorithm Based on a Modified Model of Random Walk
Venue: arXiv cs.LG 2008
Year: 2008

We introduce a modified model of random walk, and then develop two novel clustering algorithms based on it. In the algorithms, each data point in a dataset is considered as a particle which can move at random in space according to the preset rules in the modified model. Further, this data point may be also viewed as a local control subsystem, in which the controller adjusts its transition probability vector in terms of the feedbacks of all data points, and then its transition direction is identified by an event-generating function. Finally, the positions of all data points are updated. As they move in space, data points collect gradually and some separating parts emerge among them automatically. As a consequence, data points that belong to the same class are located at a same position, whereas those that belong to different classes are away from one another. Moreover, the experimental results have demonstrated that data points in the test datasets are clustered reasonably and efficiently, and the comparison with other algorithms also provides an indication of the effectiveness of the proposed algorithms.
On the Possibility of Learning in Reactive Environments with Arbitrary Dependence
Venue: arXiv cs.LG 2008
Year: 2008

We address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions, i.e. environments more general than (PO)MDPs. The task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown but belongs to a known countable family of environments. We find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. We analyze how tight these conditions are and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as Markov Decision Processes and mixing conditions.
Non procedural language for parallel programs
Venue: arXiv cs.DC 2008
Year: 2008

Probably building non procedural languages is the most prospective way for parallel programming just because non procedural means no fixed way for execution. The article consists of 3 parts. In first part we consider formal systems for definition a named datasets and studying an expression power of different subclasses. In the second part we consider a complexity of algorithms of building sets by the definitions. In third part we consider a fullness and flexibility of the class of program based data set definitions.
Number of wireless sensors needed to detect a wildfire
Venue: arXiv cs.NI 2008
Year: 2008

The lack of extensive research in the application of inexpensive wireless sensor nodes for the early detection of wildfires motivated us to investigate the cost of such a network. As a first step, in this paper we present several results which relate the time to detection and the burned area to the number of sensor nodes in the region which is protected. We prove that the probability distribution of the burned area at the moment of detection is approximately exponential, given that some hypotheses hold: the positions of the sensor nodes are independent random variables uniformly distributed and the number of sensor nodes is large. This conclusion depends neither on the number of ignition points nor on the propagation model of the fire.
Conjectural Equilibrium in Water-filling Games
Venue: arXiv cs.GT 2008
Year: 2008

This paper considers a non-cooperative game in which competing users sharing a frequency-selective interference channel selfishly optimize their power allocation in order to improve their achievable rates. Previously, it was shown that a user having the knowledge of its opponents' channel state information can make foresighted decisions and substantially improve its performance compared with the case in which it deploys the conventional iterative water-filling algorithm, which does not exploit such knowledge. This paper discusses how a foresighted user can acquire this knowledge by modeling its experienced interference as a function of its own power allocation. To characterize the outcome of the multi-user interaction, the conjectural equilibrium is introduced, and the existence of this equilibrium for the investigated water-filling game is proved. Interestingly, both the Nash equilibrium and the Stackelberg equilibrium are shown to be special cases of the generalization of conjectural equilibrium. We develop practical algorithms to form accurate beliefs and search desirable power allocation strategies. Numerical simulations indicate that a foresighted user without any a priori knowledge of its competitors' private information can effectively learn the required information, and induce the entire system to an operating point that improves both its own achievable rate as well as the rates of the other participants in the water-filling game.
A variant of Wiener's attack on RSA
Venue: arXiv cs.CR 2008
Year: 2008

Wiener's attack is a well-known polynomial-time attack on a RSA cryptosystem with small secret decryption exponent d, which works if d<n^{0.25}, where n=pq is the modulus of the cryptosystem. Namely, in that case, d is the denominator of some convergent p_m/q_m of the continued fraction expansion of e/n, and therefore d can be computed efficiently from the public key (n,e). There are several extensions of Wiener's attack that allow the RSA cryptosystem to be broken when d is a few bits longer than n^{0.25}. They all have the run-time complexity (at least) O(D^2), where d=Dn^{0.25}. Here we propose a new variant of Wiener's attack, which uses results on Diophantine approximations of the form |α- p/q| < c/q^2, and "meet-in-the-middle" variant for testing the candidates (of the form rq_{m+1} + sq_m) for the secret exponent. This decreases the run-time complexity of the attack to O(D log(D)) (with the space complexity O(D)).
Approximation of a Fractional Order System by an Integer Order Model Using Particle Swarm Optimization Technique
Venue: arXiv cs.OH 2008
Year: 2008

System identification is a necessity in control theory. Classical control theory usually considers processes with integer order transfer functions. Real processes are usually of fractional order as opposed to the ideal integral order models. A simple and elegant scheme is presented for approximation of such a real world fractional order process by an ideal integral order model. A population of integral order process models is generated and updated by PSO technique, the fitness function being the sum of squared deviations from the set of observations obtained from the actual fractional order process. Results show that the proposed scheme offers a high degree of accuracy.
Balancing Exploration and Exploitation by an Elitist Ant System with Exponential Pheromone Deposition Rule
Venue: arXiv cs.AI 2008
Year: 2008

The paper presents an exponential pheromone deposition rule to modify the basic ant system algorithm which employs constant deposition rule. A stability analysis using differential equation is carried out to find out the values of parameters that make the ant system dynamics stable for both kinds of deposition rule. A roadmap of connected cities is chosen as the problem environment where the shortest route between two given cities is required to be discovered. Simulations performed with both forms of deposition approach using Elitist Ant System model reveal that the exponential deposition approach outperforms the classical one by a large extent. Exhaustive experiments are also carried out to find out the optimum setting of different controlling parameters for exponential deposition approach and an empirical relationship between the major controlling parameters of the algorithm and some features of problem environment.
A Study of the Grunwald-Letnikov Definition for Minimizing the Effects of Random Noise on Fractional Order Differential Equations
Venue: arXiv cs.OH 2008
Year: 2008

Of the many definitions for fractional order differintegral, the Grunwald-Letnikov definition is arguably the most important one. The necessity of this definition for the description and analysis of fractional order systems cannot be overstated. Unfortunately, the Fractional Order Differential Equation (FODE) describing such a systems, in its original form, highly sensitive to the effects of random noise components inevitable in a natural environment. Thus direct application of the definition in a real-life problem can yield erroneous results. In this article, we perform an in-depth mathematical analysis the Grunwald-Letnikov definition in depth and, as far as we know, we are the first to do so. Based on our analysis, we present a transformation scheme which will allow us to accurately analyze generalized fractional order systems in presence of significant quantities of random errors. Finally, by a simple experiment, we demonstrate the high degree of robustness to noise offered by the said transformation and thus validate our scheme.
A Novel Parser Design Algorithm Based on Artificial Ants
Venue: arXiv cs.AI 2008
Year: 2008

This article presents a unique design for a parser using the Ant Colony Optimization algorithm. The paper implements the intuitive thought process of human mind through the activities of artificial ants. The scheme presented here uses a bottom-up approach and the parsing program can directly use ambiguous or redundant grammars. We allocate a node corresponding to each production rule present in the given grammar. Each node is connected to all other nodes (representing other production rules), thereby establishing a completely connected graph susceptible to the movement of artificial ants. Each ant tries to modify this sentential form by the production rule present in the node and upgrades its position until the sentential form reduces to the start symbol S. Successful ants deposit pheromone on the links that they have traversed through. Eventually, the optimum path is discovered by the links carrying maximum amount of pheromone concentration. The design is simple, versatile, robust and effective and obviates the calculation of the above mentioned sets and precedence relation tables. Further advantages of our scheme lie in i) ascertaining whether a given string belongs to the language represented by the grammar, and ii) finding out the shortest possible path from the given string to the start symbol S in case multiple routes exist.
Extension of Max-Min Ant System with Exponential Pheromone Deposition Rule
Venue: arXiv cs.AI 2008
Year: 2008

The paper presents an exponential pheromone deposition approach to improve the performance of classical Ant System algorithm which employs uniform deposition rule. A simplified analysis using differential equations is carried out to study the stability of basic ant system dynamics with both exponential and constant deposition rules. A roadmap of connected cities, where the shortest path between two specified cities are to be found out, is taken as a platform to compare Max-Min Ant System model (an improved and popular model of Ant System algorithm) with exponential and constant deposition rules. Extensive simulations are performed to find the best parameter settings for non-uniform deposition approach and experiments with these parameter settings revealed that the above approach outstripped the traditional one by a large extent in terms of both solution quality and convergence time.
Entropy, Perception, and Relativity
Venue: arXiv cs.LG 2008
Year: 2008

In this paper, I expand Shannon's definition of entropy into a new form of entropy that allows integration of information from different random events. Shannon's notion of entropy is a special case of my more general definition of entropy. I define probability using a so-called performance function, which is de facto an exponential distribution. Assuming that my general notion of entropy reflects the true uncertainty about a probabilistic event, I understand that our perceived uncertainty differs. I claim that our perception is the result of two opposing forces similar to the two famous antagonists in Chinese philosophy: Yin and Yang. Based on this idea, I show that our perceived uncertainty matches the true uncertainty in points determined by the golden ratio. I demonstrate that the well-known sigmoid function, which we typically employ in artificial neural networks as a non-linear threshold function, describes the actual performance. Furthermore, I provide a motivation for the time dilation in Einstein's Special Relativity, basically claiming that although time dilation conforms with our perception, it does not correspond to reality. At the end of the paper, I show how to apply this theoretical framework to practical applications. I present recognition rates for a pattern recognition problem, and also propose a network architecture that can take advantage of general entropy to solve complex decision problems.
Joint Transmitter-Receiver Design for the Downlink Multiuser Spatial Multiplexing MIMO System
Venue: arXiv cs.IT 2008
Year: 2008

This paper proposes a joint transmitter-receiver design to minimize the weighted sum power under the post-processing signal-to-interference-and-noise ratio (post-SINR) constraints for all subchannels. Simulation results demonstrate that the algorithm can not only satisfy the post-SINR constraints but also easily adjust the power distribution among the users by changing the weights accordingly. Hence the algorithm can be used to alleviates the adjacent cell interference by reducing the transmitting power to the edge users without performance penalty.
Robust Linear Processing for Downlink Multiuser MIMO System With Imperfectly Known Channel
Venue: arXiv cs.IT 2008
Year: 2008

This paper proposes a roust downlink multiuser MIMO scheme that exploits the channel mean and antenna correlations to alleviate the performance penalty due to the mismatch between the true and estimated CSI.
A Web-Based Resource Model for eScience: Object Reuse & Exchange
Venue: arXiv cs.DL 2008
Year: 2008

Work in the Open Archives Initiative - Object Reuse and Exchange (OAI-ORE) focuses on an important aspect of infrastructure for eScience: the specification of the data model and a suite of implementation standards to identify and describe compound objects. These are objects that aggregate multiple sources of content including text, images, data, visualization tools, and the like. These aggregations are an essential product of eScience, and will become increasingly common in the age of data-driven scholarship. The OAI-ORE specifications conform to the core concepts of the Web architecture and the semantic Web, ensuring that applications that use them will integrate well into the general Web environment.
Cognitive OFDM network sensing: a free probability approach
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a practical power detection scheme for OFDM terminals, based on recent free probability tools, is proposed. The objective is for the receiving terminal to determine the transmission power and the number of the surrounding base stations in the network. However, thesystem dimensions of the network model turn energy detection into an under-determined problem. The focus of this paper is then twofold: (i) discuss the maximum amount of information that an OFDM terminal can gather from the surrounding base stations in the network, (ii) propose a practical solution for blind cell detection using the free deconvolution tool. The efficiency of this solution is measured through simulations, which show better performance than the classical power detection methods.
Two Forms of One Useful Logic: Existential Fixed Point Logic and Liberal Datalog
Venue: arXiv cs.LO 2008
Year: 2008

A natural liberalization of Datalog is used in the Distributed Knowledge Authorization Language (DKAL). We show that the expressive power of this liberal Datalog is that of existential fixed-point logic. The exposition is self-contained.
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
Venue: arXiv cs.LO 2008
Year: 2008

Resolution refinements called w-resolution trees with lemmas (WRTL) and with input lemmas (WRTI) are introduced. Dag-like resolution is equivalent to both WRTL and WRTI when there is no regularity condition. For regular proofs, an exponential separation between regular dag-like resolution and both regular WRTL and regular WRTI is given. It is proved that DLL proof search algorithms that use clause learning based on unit propagation can be polynomially simulated by regular WRTI. More generally, non-greedy DLL algorithms with learning by unit propagation are equivalent to regular WRTI. A general form of clause learning, called DLL-Learn, is defined that is equivalent to regular WRTL. A variable extension method is used to give simulations of resolution by regular WRTI, using a simplified form of proof trace extensions. DLL-Learn and non-greedy DLL algorithms with learning by unit propagation can use variable extensions to simulate general resolution without doing restarts. Finally, an exponential lower bound for WRTL where the lemmas are restricted to short clauses is shown.
A Model for Probabilistic Reasoning on Assume/Guarantee Contracts
Venue: arXiv cs.PF 2008
Year: 2008

In this paper, we present a probabilistic adaptation of an Assume/Guarantee contract formalism. For the sake of generality, we assume that the extended state machines used in the contracts and implementations define sets of runs on a given set of variables, that compose by intersection over the common variables. In order to enable probabilistic reasoning, we consider that the contracts dictate how certain input variables will behave, being either non-deterministic, or probabilistic; the introduction of probabilistic variables leading us to tune the notions of implementation, refinement and composition. As shown in the report, this probabilistic adaptation of the Assume/Guarantee contract theory preserves compositionality and therefore allows modular reliability analysis, either with a top-down or a bottom-up approach.
NB-FEB: An Easy-to-Use and Scalable Universal Synchronization Primitive for Parallel Programming
Venue: arXiv cs.DC 2008
Year: 2008

This paper addresses the problem of universal synchronization primitives that can support scalable thread synchronization for large-scale many-core architectures. The universal synchronization primitives that have been deployed widely in conventional architectures like CAS and LL/SC are expected to reach their scalability limits in the evolution to many-core architectures with thousands of cores. We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable, feasible and convenient to use. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility). The original full/empty bit is well-known as a special-purpose primitive for fast producer-consumer synchronization and has been used extensively in the specific domain of applications. In this paper, we show that NB-FEB can be deployed easily as a general-purpose primitive. Using NB-FEB, we construct a non-blocking software transactional memory system called NBFEB-STM, which can be used to handle concurrent threads conveniently. NBFEB-STM is space efficient: the space complexity of each object updated by $N$ concurrent threads/transactions is $Θ(N)$, the optimal.