OpenRaiser/Intern-Atlas huggingface dataset:
A Divergence Formula for Randomness and Dimension (Short Version)
Venue: arXiv cs.CC 2009
Year: 2009

If $S$ is an infinite sequence over a finite alphabet $Σ$ and $β$ is a probability measure on $Σ$, then the {\it dimension} of $ S$ with respect to $β$, written $\dim^β(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $β$ is the uniform probability measure. This paper shows that $\dim^β(S)$ and its dual $\Dim^β(S)$, the {\it strong dimension} of $S$ with respect to $β$, can be used in conjunction with randomness to measure the similarity of two probability measures $α$ and $β$ on $Σ$. Specifically, we prove that the {\it divergence formula} $$\dim^β(R) = \Dim^β(R) =\CH(α) / (\CH(α) + \D(α|| β))$$ holds whenever $α$ and $β$ are computable, positive probability measures on $Σ$ and $R \in Σ^\infty$ is random with respect to $α$. In this formula, $\CH(α)$ is the Shannon entropy of $α$, and $\D(α||β)$ is the Kullback-Leibler divergence between $α$ and $β$.
Client-Server Password Recovery (Extended Abstract)
Venue: arXiv cs.CR 2009
Year: 2009

Human memory is not perfect - people constantly memorize new facts and forget old ones. One example is forgetting a password, a common problem raised at IT help desks. We present several protocols that allow a user to automatically recover a password from a server using partial knowledge of the password. These protocols can be easily adapted to the personal entropy setting, where a user can recover a password only if he can answer a large enough subset of personal questions. We introduce client-server password recovery methods, in which the recovery data are stored at the server, and the recovery procedures are integrated into the login procedures. These methods apply to two of the most common types of password based authentication systems. The security of these solutions is significantly better than the security of presently proposed password recovery schemes. Our protocols are based on a variation of threshold encryption that may be of independent interest.
Efficient IRIS Recognition through Improvement of Feature Extraction and subset Selection
Venue: arXiv cs.CV 2009
Year: 2009

The selection of the optimal feature subset and the classification has become an important issue in the field of iris recognition. In this paper we propose several methods for iris feature subset selection and vector creation. The deterministic feature sequence is extracted from the iris image by using the contourlet transform technique. Contourlet transform captures the intrinsic geometrical structures of iris image. It decomposes the iris image into a set of directional sub-bands with texture details captured in different orientations at various scales so for reducing the feature vector dimensions we use the method for extract only significant bit and information from normalized iris images. In this method we ignore fragile bits. And finally we use SVM (Support Vector Machine) classifier for approximating the amount of people identification in our proposed system. Experimental result show that most proposed method reduces processing time and increase the classification accuracy and also the iris feature vector length is much smaller versus the other methods.
Forecasting Model for Crude Oil Price Using Artificial Neural Networks and Commodity Futures Prices
Venue: arXiv cs.NE 2009
Year: 2009

This paper presents a model based on multilayer feedforward neural network to forecast crude oil spot price direction in the short-term, up to three days ahead. A great deal of attention was paid on finding the optimal ANN model structure. In addition, several methods of data pre-processing were tested. Our approach is to create a benchmark based on lagged value of pre-processed spot price, then add pre-processed futures prices for 1, 2, 3,and four months to maturity, one by one and also altogether. The results on the benchmark suggest that a dynamic model of 13 lags is the optimal to forecast spot price direction for the short-term. Further, the forecast accuracy of the direction of the market was 78%, 66%, and 53% for one, two, and three days in future conclusively. For all the experiments, that include futures data as an input, the results show that on the short-term, futures prices do hold new information on the spot price direction. The results obtained will generate comprehensive understanding of the crude oil dynamic which help investors and individuals for risk managements.
Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage
Venue: arXiv cs.IT 2009
Year: 2009

Erasure coding techniques are used to increase the reliability of distributed storage systems while minimizing storage overhead. Also of interest is minimization of the bandwidth required to repair the system following a node failure. In a recent paper, Wu et al. characterize the tradeoff between the repair bandwidth and the amount of data stored per node. They also prove the existence of regenerating codes that achieve this tradeoff. In this paper, we introduce Exact Regenerating Codes, which are regenerating codes possessing the additional property of being able to duplicate the data stored at a failed node. Such codes require low processing and communication overheads, making the system practical and easy to maintain. Explicit construction of exact regenerating codes is provided for the minimum bandwidth point on the storage-repair bandwidth tradeoff, relevant to distributed-mail-server applications. A subspace based approach is provided and shown to yield necessary and sufficient conditions on a linear code to possess the exact regeneration property as well as prove the uniqueness of our construction. Also included in the paper, is an explicit construction of regenerating codes for the minimum storage point for parameters relevant to storage in peer-to-peer systems. This construction supports a variable number of nodes and can handle multiple, simultaneous node failures. All constructions given in the paper are of low complexity, requiring low field size in particular.
Testing cycle-freeness: Finding a certificate
Venue: arXiv cs.DS 2009
Year: 2009

We deal with the problem of designing one-sided error property testers for cycle-freeness in bounded degree graphs. Such a property tester always accepts forests. Furthermore, when it rejects an input, it provides a short cycle as a certificate. The problem of testing cycle-freeness in this model was first considered by Goldreich and Ron \cite{GR97}. They give a constant time tester with two-sided error (it does not provide certificates for rejection) and prove a $Ω(\sqrt{n})$ lower bound for testers with one-sided error. We design a property tester with one-sided error whose running time matches this lower bound (upto polylogarithmic factors). Interestingly, this has connections to a recent conjecture of Benjamini, Schramm, and Shapira \cite{BSS08}. The property of cycle-freeness is closed under the operation of taking minors. This is the first example of such a property that has an almost optimal $\otilde(\sqrt{n})$-time one-sided error tester, but has a constant time two-sided error tester. It was conjectured in \cite{BSS08} that this happens for a vast class of minor-closed properties, and this result can seen as the first indication towards that.
Explicit probabilistic models for databases and networks
Venue: arXiv cs.AI 2009
Year: 2009

Recent work in data mining and related areas has highlighted the importance of the statistical assessment of data mining results. Crucial to this endeavour is the choice of a non-trivial null model for the data, to which the found patterns can be contrasted. The most influential null models proposed so far are defined in terms of invariants of the null distribution. Such null models can be used by computation intensive randomization approaches in estimating the statistical significance of data mining results. Here, we introduce a methodology to construct non-trivial probabilistic models based on the maximum entropy (MaxEnt) principle. We show how MaxEnt models allow for the natural incorporation of prior information. Furthermore, they satisfy a number of desirable properties of previously introduced randomization approaches. Lastly, they also have the benefit that they can be represented explicitly. We argue that our approach can be used for a variety of data types. However, for concreteness, we have chosen to demonstrate it in particular for databases and networks.
Spectrum of Fractal Interpolation Functions
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we compute the Fourier spectrum of the Fractal Interpolation Functions FIFs as introduced by Michael Barnsley. We show that there is an analytical way to compute them. In this paper we attempt to solve the inverse problem of FIF by using the spectrum
Query Significance in Databases via Randomizations
Venue: arXiv cs.DB 2009
Year: 2009

Many sorts of structured data are commonly stored in a multi-relational format of interrelated tables. Under this relational model, exploratory data analysis can be done by using relational queries. As an example, in the Internet Movie Database (IMDb) a query can be used to check whether the average rank of action movies is higher than the average rank of drama movies. We consider the problem of assessing whether the results returned by such a query are statistically significant or just a random artifact of the structure in the data. Our approach is based on randomizing the tables occurring in the queries and repeating the original query on the randomized tables. It turns out that there is no unique way of randomizing in multi-relational data. We propose several randomization techniques, study their properties, and show how to find out which queries or hypotheses about our data result in statistically significant information. We give results on real and generated data and show how the significance of some queries vary between different randomizations.
On Unique Independence Weighted Graphs
Venue: arXiv cs.CC 2009
Year: 2009

An independent set in a graph G is a set of vertices no two of which are joined by an edge. A vertex-weighted graph associates a weight with every vertex in the graph. A vertex-weighted graph G is called a unique independence vertex-weighted graph if it has a unique independent set with maximum sum of weights. Although, in this paper we observe that the problem of recognizing unique independence vertex-weighted graphs is NP-hard in general and therefore no efficient characterization can be expected in general; we give, however, some combinatorial characterizations of unique independence vertex-weighted graphs. This paper introduces a motivating application of this problem in the area of combinatorial auctions, as well.
A Cut-off Phenomenon in Location Based Random Access Games with Imperfect Information
Venue: arXiv cs.IT 2009
Year: 2009

This paper analyzes the behavior of selfish transmitters under imperfect location information. The scenario considered is that of a wireless network consisting of selfish nodes that are randomly distributed over the network domain according to a known probability distribution, and that are interested in communicating with a common sink node using common radio resources. In this scenario, the wireless nodes do not know the exact locations of their competitors but rather have belief distributions about these locations. Firstly, properties of the packet success probability curve as a function of the node-sink separation are obtained for such networks. Secondly, a monotonicity property for the best-response strategies of selfish nodes is identified. That is, for any given strategies of competitors of a node, there exists a critical node-sink separation for this node such that its best-response is to transmit when its distance to the sink node is smaller than this critical threshold, and to back off otherwise. Finally, necessary and sufficient conditions for a given strategy profile to be a Nash equilibrium are provided.
An Iterative Fingerprint Enhancement Algorithm Based on Accurate Determination of Orientation Flow
Venue: arXiv cs.CV 2009
Year: 2009

We describe an algorithm to enhance and binarize a fingerprint image. The algorithm is based on accurate determination of orientation flow of the ridges of the fingerprint image by computing variance of the neighborhood pixels around a pixel in different directions. We show that an iterative algorithm which captures the mutual interdependence of orientation flow computation, enhancement and binarization gives very good results on poor quality images.
Improved approximation guarantees for weighted matching in the semi-streaming model
Venue: arXiv cs.DS 2009
Year: 2009

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. of STACS2008, pages 669-680) by devising a deterministic approach whose performance guarantee is 4.91+epsilon. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching.
Démarche d'évaluation de l'usage et des répercussions psychosociales d'un environnement STIC sur une population de personnes âgées en résidence médicalisée
Venue: arXiv cs.CY 2009
Year: 2009

The MNESIS Project aims to see whether the use of computerized environment by elderly people in medicalized residences stimulates their cognitive capacities and contributes to a better integration, recognition or acceptance within their social environment (friends, family, medical staff). In this paper we present the protocol of evaluation that is defined to check this assumption. This protocol is between users' centred traditional protocols (built on investigations and indirect observation) and studies of Web Usage Mining (where knowledge databases about the uses are built from traces of use). It allows collecting direct and indirect information on a large scale and over long periods.
Network Topology and Time Criticality Effects in the Modularised Fleet Mix Problem
Venue: arXiv cs.NE 2009
Year: 2009

In this paper, we explore the interplay between network topology and time criticality in a military logistics system. A general goal of this work (and previous work) is to evaluate land transportation requirements or, more specifically, how to design appropriate fleets of military general service vehicles that are tasked with the supply and re-supply of military units dispersed in an area of operation. The particular focus of this paper is to gain a better understanding of how the logistics environment changes when current Army vehicles with fixed transport characteristics are replaced by a new generation of modularised vehicles that can be configured task-specifically. The experimental work is conducted within a well developed strategic planning simulation environment which includes a scenario generation engine for automatically sampling supply and re-supply missions and a multi-objective meta-heuristic search algorithm (i.e. Evolutionary Algorithm) for solving the particular scheduling and routing problems. The results presented in this paper allow for a better understanding of how (and under what conditions) a modularised vehicle fleet can provide advantages over the currently implemented system.
Multidimensional Generalized Automatic Sequences and Shape-symmetric Morphic Words
Venue: arXiv cs.FL 2009
Year: 2009

An infinite word is S-automatic if, for all n>=0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d>=2, we state that a multidimensional infinite word x : N^d \to Σover a finite alphabet Σis S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word.
Function Interface Models for Hardware Compilation: Types, Signatures, Protocols
Venue: arXiv cs.PL 2009
Year: 2009

The problem of synthesis of gate-level descriptions of digital circuits from behavioural specifications written in higher-level programming languages (hardware compilation) has been studied for a long time yet a definitive solution has not been forthcoming. The argument of this essay is mainly methodological, bringing a perspective that is informed by recent developments in programming-language theory. We argue that one of the major obstacles in the way of hardware compilation becoming a useful and mature technology is the lack of a well defined function interface model, i.e. a canonical way in which functions communicate with arguments. We discuss the consequences of this problem and propose a solution based on new developments in programming language theory. We conclude by presenting a prototype implementation and some examples illustrating our principles.
Deterministic Polynomial Time Algorithms for Matrix Completion Problems
Venue: arXiv cs.DS 2009
Year: 2009

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e. the problem of assigning values to the variables in a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to the fundamental problems in computational complexity with numerous important algorithmic applications, among others, in computing dynamic transitive closures or multicast network codings (Harvey et al SODA 2005, Harvey et al SODA 2006). We design efficient deterministic algorithms for common generalizations of the results of Lovasz and Geelen on this problem by allowing linear functions in the entries of the input matrix such that the submatrices corresponding to each variable have rank one. We present also a deterministic polynomial time algorithm for finding the minimal number of generators of a given module structure given by matrices. We establish further several hardness results related to matrix algebras and modules. As a result we connect the classical problem of polynomial identity testing with checking surjectivity (or injectivity) between two given modules. One of the elements of our algorithm is a construction of a greedy algorithm for finding a maximum rank element in the more general setting of the problem. The proof methods used in this paper could be also of independent interest.
Bayesian Multitask Learning with Latent Hierarchies
Venue: arXiv cs.LG 2009
Year: 2009

We learn multiple hypotheses for related tasks under a latent hierarchical relationship between tasks. We exploit the intuition that for domain adaptation, we wish to share classifier structure, but for multitask learning, we wish to share covariance structure. Our hierarchical model is seen to subsume several previously proposed multitask learning models and performs well on three distinct real-world data sets.
Cross-Task Knowledge-Constrained Self Training
Venue: arXiv cs.LG 2009
Year: 2009

We present an algorithmic framework for learning multiple related tasks. Our framework exploits a form of prior knowledge that relates the output spaces of these tasks. We present PAC learning results that analyze the conditions under which such learning is possible. We present results on learning a shallow parser and named-entity recognition system that exploits our framework, showing consistent improvements over baseline methods.
A Bayesian Model for Discovering Typological Implications
Venue: arXiv cs.CL 2009
Year: 2009

A standard form of analysis for linguistic typology is the universal implication. These implications state facts about the range of extant languages, such as ``if objects come after verbs, then adjectives come after nouns.'' Such implications are typically discovered by painstaking hand analysis over a small sample of languages. We propose a computational model for assisting at this process. Our model is able to discover both well-known implications as well as some novel implications that deserve further study. Moreover, through a careful application of hierarchical analysis, we are able to cope with the well-known sampling problem: languages are not independent.
Randomized Incremental Construction of Compressed Quadtrees
Venue: arXiv cs.CG 2009
Year: 2009

We present a simple randomized incremental algorithm for building compressed quadtrees. The resulting algorithm seems to be simpler than previously known algorithms for this task.
The Soft Cumulative Constraint
Venue: arXiv cs.AI 2009
Year: 2009

This research report presents an extension of Cumulative of Choco constraint solver, which is useful to encode over-constrained cumulative problems. This new global constraint uses sweep and task interval violation-based algorithms.
Apply Local Clustering Method to Improve the Running Speed of Ant Colony Optimization
Venue: arXiv cs.NE 2009
Year: 2009

Ant Colony Optimization (ACO) has time complexity O(t*m*N*N), and its typical application is to solve Traveling Salesman Problem (TSP), where t, m, and N denotes the iteration number, number of ants, number of cities respectively. Cutting down running time is one of study focuses, and one way is to decrease parameter t and N, especially N. For this focus, the following method is presented in this paper. Firstly, design a novel clustering algorithm named Special Local Clustering algorithm (SLC), then apply it to classify all cities into compact classes, where compact class is the class that all cities in this class cluster tightly in a small region. Secondly, let ACO act on every class to get a local TSP route. Thirdly, all local TSP routes are jointed to form solution. Fourthly, the inaccuracy of solution caused by clustering is eliminated. Simulation shows that the presented method improves the running speed of ACO by 200 factors at least. And this high speed is benefit from two factors. One is that class has small size and parameter N is cut down. The route length at every iteration step is convergent when ACO acts on compact class. The other factor is that, using the convergence of route length as termination criterion of ACO and parameter t is cut down.
Multi-User Diversity vs. Accurate Channel State Information in MIMO Downlink Channels
Venue: arXiv cs.IT 2009
Year: 2009

In a multiple transmit antenna, single antenna per receiver downlink channel with limited channel state feedback, we consider the following question: given a constraint on the total system-wide feedback load, is it preferable to get low-rate/coarse channel feedback from a large number of receivers or high-rate/high-quality feedback from a smaller number of receivers? Acquiring feedback from many receivers allows multi-user diversity to be exploited, while high-rate feedback allows for very precise selection of beamforming directions. We show that there is a strong preference for obtaining high-quality feedback, and that obtaining near-perfect channel information from as many receivers as possible provides a significantly larger sum rate than collecting a few feedback bits from a large number of users.