OpenRaiser/Intern-Atlas huggingface dataset:
A Meshless Method for Variational Nonrigid 2-D Shape Registration
Venue: arXiv cs.CV 2011
Year: 2011

We present a method for nonrigid registration of 2-D geometric shapes. Our contribution is twofold. First, we extend the classic chamfer-matching energy to a variational functional. Secondly, we introduce a meshless deformation model that can handle significant high-curvature deformations. We represent 2-D shapes implicitly using distance transforms, and registration error is defined based on the shape contours' mutual distances. In addition, we model global shape deformation as an approximation blended from local deformation fields using partition-of-unity. The global deformation field is regularized by penalizing inconsistencies between local fields. The representation can be made adaptive to shape's contour, leading to registration that is both flexible and efficient. Finally, registration is achieved by minimizing a variational chamfer-energy functional combined with the consistency regularizer. We demonstrate the effectiveness of our method on a number of experiments.
Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
Venue: arXiv cs.DS 2011
Year: 2011

Countless variants of the Lempel-Ziv compression are widely used in many real-life applications. This paper is concerned with a natural modification of the classical pattern matching problem inspired by the popularity of such compression methods: given an uncompressed pattern s[1..m] and a Lempel-Ziv representation of a string t[1..N], does s occur in t? Farach and Thorup gave a randomized O(nlog^2(N/n)+m) time solution for this problem, where n is the size of the compressed representation of t. We improve their result by developing a faster and fully deterministic O(nlog(N/n)+m) time algorithm with the same space complexity. Note that for highly compressible texts, log(N/n) might be of order n, so for such inputs the improvement is very significant. A (tiny) fragment of our method can be used to give an asymptotically optimal solution for the substring hashing problem considered by Farach and Muthukrishnan.
A Short Course on Frame Theory
Venue: arXiv cs.IT 2011
Year: 2011

A Short Course on Frame Theory.
Platforms for Building and Deploying Applications for Cloud Computing
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing is rapidly emerging as a new paradigm for delivering IT services as utlity-oriented services on subscription-basis. The rapid development of applications and their deployment in Cloud computing environments in efficient manner is a complex task. In this article, we give a brief introduction to Cloud computing technology and Platform as a Service, we examine the offerings in this category, and provide the basis for helping readers to understand basic application platform opportunities in Cloud by technologies such as Microsoft Azure, Sales Force, Google App, and Aneka for Cloud computing. We demonstrate that Manjrasoft Aneka is a Cloud Application Platform (CAP) leveraging these concepts and allowing an easy development of Cloud ready applications on a Private/Public/Hybrid Cloud. Aneka CAP offers facilities for quickly developing Cloud applications and a modular platform where additional services can be easily integrated to extend the system capabilities, thus being at pace with the rapidly evolution of Cloud computing.
Internal links and pairs as a new tool for the analysis of bipartite complex networks
Venue: arXiv cs.SI 2011
Year: 2011

Many real-world complex networks are best modeled as bipartite (or 2-mode) graphs, where nodes are divided into two sets with links connecting one side to the other. However, there is currently a lack of methods to analyze properly such graphs as most existing measures and methods are suited to classical graphs. A usual but limited approach consists in deriving 1-mode graphs (called projections) from the underlying bipartite structure, though it causes important loss of information and data storage issues. We introduce here internal links and pairs as a new notion useful for such analysis: it gives insights on the information lost by projecting the bipartite graph. We illustrate the relevance of theses concepts on several real-world instances illustrating how it enables to discriminate behaviors among various cases when we compare them to a benchmark of random networks. Then, we show that we can draw benefit from this concept for both modeling complex networks and storing them in a compact format.
On scattered subword complexity
Venue: arXiv cs.DM 2011
Year: 2011

Special scattered subwords, in which the gaps are of length from a given set, are defined. The scattered subword complexity, which is the number of such scattered subwords, is computed for rainbow words.
Primitive words and roots of words
Venue: arXiv cs.FL 2011
Year: 2011

In the algebraic theory of codes and formal languages, the set $Q$ of all primitive words over some alphabet $\zi $ has received special interest. With this survey article we give an overview about relevant research to this topic during the last twenty years including own investigations and some new results. In Section 1 after recalling the most important notions from formal language theory we illustrate the connection between coding theory and primitive words by some facts. We define primitive words as words having only a trivial representation as the power of another word. Nonprimitive words (without the empty word) are exactly the periodic words. Every nonempty word is a power of an uniquely determined primitive word which is called the root of the former one. The set of all roots of nonempty words of a language is called the root of the language. The primitive words have interesting combinatorial properties which we consider in Section 2. In Section 3 we investigate the relationship between the set $Q$ of all primitive words over some fixed alphabet and the language classes of the Chomsky Hierarchy and the contextual languages over the same alphabet. The computational complexity of the set $Q$ and of the roots of languages are considered in Section 4. The set of all powers of the same degree of all words from a language is the power of this language. We examine the powers of languages for different sets of exponents, and especially their regularity and context-freeness, in Section 5, and the decidability of appropriate questions in Section 6. Section 7 is dedicated to several generalizations of the notions of periodicity and primitivity of words.
Tiled QR factorization algorithms
Venue: arXiv cs.DC 2011
Year: 2011

This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, Greedy, and those found within PLASMA. Although neither Modi and Clarke nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q^2 f(q), where f is any function such that \lim_{+\infty} f= 0. This novel and important complexity result applies to all matrices where p and q are proportional, p = λq, with λ>= 1, thereby encompassing many important situations in practice (least squares). We provide an extensive set of experiments that show the superiority of the new algorithms for tall matrices.
Playing against the fittest: A simple strategy that promotes the emergence of cooperation
Venue: arXiv cs.GT 2011
Year: 2011

Understanding the emergence and sustainability of cooperation is a fundamental problem in evolutionary biology and is frequently studied by the framework of evolutionary game theory. A very powerful mechanism to promote cooperation is network reciprocity, where the interaction patterns and opportunities for strategy spread of agents are constrained to limited sets of permanent interactions partners. Cooperation survives because it is possible for close-knit communities of cooperation to be shielded from invasion by defectors. Here we show that parameter ranges in which cooperation can survive are strongly expanded if game play on networks is skewed towards more frequent interactions with more successful neighbours. In particular, if agents exclusively select neighbors for game play that are more successful than themselves, cooperation can even dominate in situations in which it would die out if interaction neighbours were chosen without a bias or with a preference for less successful opponents. We demonstrate that the "selecting fitter neighbours" strategy is evolutionarily stable. Moreover, it will emerge as the dominant strategy out of an initially random population of agents.
Temporal Second Difference Traces
Venue: arXiv cs.LG 2011
Year: 2011

Q-learning is a reliable but inefficient off-policy temporal-difference method, backing up reward only one step at a time. Replacing traces, using a recency heuristic, are more efficient but less reliable. In this work, we introduce model-free, off-policy temporal difference methods that make better use of experience than Watkins' Q(λ). We introduce both Optimistic Q(λ) and the temporal second difference trace (TSDT). TSDT is particularly powerful in deterministic domains. TSDT uses neither recency nor frequency heuristics, storing (s,a,r,s',δ) so that off-policy updates can be performed after apparently suboptimal actions have been taken. There are additional advantages when using state abstraction, as in MAXQ. We demonstrate that TSDT does significantly better than both Q-learning and Watkins' Q(λ) in a deterministic cliff-walking domain. Results in a noisy cliff-walking domain are less advantageous for TSDT, but demonstrate the efficacy of Optimistic Q(λ), a replacing trace with some of the advantages of TSDT.
Performance Evaluation of Statistical Approaches for Text Independent Speaker Recognition Using Source Feature
Venue: arXiv cs.CL 2011
Year: 2011

This paper introduces the performance evaluation of statistical approaches for TextIndependent speaker recognition system using source feature. Linear prediction LP residual is used as a representation of excitation information in speech. The speaker-specific information in the excitation of voiced speech is captured using statistical approaches such as Gaussian Mixture Models GMMs and Hidden Markov Models HMMs. The decrease in the error during training and recognizing speakers during testing phase close to 100 percent accuracy demonstrates that the excitation component of speech contains speaker-specific information and is indeed being effectively captured by continuous Ergodic HMM than GMM. The performance of the speaker recognition system is evaluated on GMM and 2 state ergodic HMM with different mixture components and test speech duration. We demonstrate the speaker recognition studies on TIMIT database for both GMM and Ergodic HMM.
An inflationary differential evolution algorithm for space trajectory optimization
Venue: arXiv cs.CE 2011
Year: 2011

In this paper we define a discrete dynamical system that governs the evolution of a population of agents. From the dynamical system, a variant of Differential Evolution is derived. It is then demonstrated that, under some assumptions on the differential mutation strategy and on the local structure of the objective function, the proposed dynamical system has fixed points towards which it converges with probability one for an infinite number of generations. This property is used to derive an algorithm that performs better than standard Differential Evolution on some space trajectory optimization problems. The novel algorithm is then extended with a guided restart procedure that further increases the performance, reducing the probability of stagnation in deceptive local minima.
Maximum Rate of 3- and 4-Real-Symbol ML Decodable Unitary Weight STBCs
Venue: arXiv cs.IT 2011
Year: 2011

It has been shown recently that the maximum rate of a 2-real-symbol (single-complex-symbol) maximum likelihood (ML) decodable, square space-time block codes (STBCs) with unitary weight matrices is $\frac{2a}{2^a}$ complex symbols per channel use (cspcu) for $2^a$ number of transmit antennas \cite{KSR}. These STBCs are obtained from Unitary Weight Designs (UWDs). In this paper, we show that the maximum rates for 3- and 4-real-symbol (2-complex-symbol) ML decodable square STBCs from UWDs, for $2^{a}$ transmit antennas, are $\frac{3(a-1)}{2^{a}}$ and $\frac{4(a-1)}{2^{a}}$ cspcu, respectively. STBCs achieving this maximum rate are constructed. A set of sufficient conditions on the signal set, required for these codes to achieve full-diversity are derived along with expressions for their coding gain.
File Transfer Application For Sharing Femto Access
Venue: arXiv cs.NI 2011
Year: 2011

In wireless access network optimization, today's main challenges reside in traffic offload and in the improvement of both capacity and coverage networks. The operators are interested in solving their localized coverage and capacity problems in areas where the macro network signal is not able to serve the demand for mobile data. Thus, the major issue for operators is to find the best solution at reasonable expanses. The femto cell seems to be the answer to this problematic. In this work (This work is supported by the COMET project AWARE. http://www.ftw.at/news/project-start-for-aware-ftw), we focus on the problem of sharing femto access between a same mobile operator's customers. This problem can be modeled as a game where service requesters customers (SRCs) and service providers customers (SPCs) are the players. This work addresses the sharing femto access problem considering only one SPC using game theory tools. We consider that SRCs are static and have some similar and regular connection behavior. We also note that the SPC and each SRC have a software embedded respectively on its femto access, user equipment (UE). After each connection requested by a SRC, its software will learn the strategy increasing its gain knowing that no information about the other SRCs strategies is given. The following article presents a distributed learning algorithm with incomplete information running in SRCs software. We will then answer the following questions for a game with $N$ SRCs and one SPC: how many connections are necessary for each SRC in order to learn the strategy maximizing its gain? Does this algorithm converge to a stable state? If yes, does this state a Nash Equilibrium and is there any way to optimize the learning process duration time triggered by SRCs software?
Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines
Venue: arXiv cs.FL 2011
Year: 2011

A weighted finite-state machine with n tapes (n-WFSM) defines a rational relation on n strings. It is a generalization of weighted acceptors (one tape) and transducers (two tapes). After recalling some basic definitions about n-ary weighted rational relations and n-WFSMs, we summarize some central operations on these relations and machines, such as join and auto-intersection. Unfortunately, due to Post's Correspondence Problem, a fully general join or auto-intersection algorithm cannot exist. We recall a restricted algorithm for a class of n-WFSMs. Through a series of practical applications, we finally investigate the augmented descriptive power of n-WFSMs and their join, compared to classical transducers and their composition. Some applications are not feasible with the latter. The series includes: the morphological analysis of Semitic languages, the preservation of intermediate results in transducer cascades, the induction of morphological rules from corpora, the alignment of lexicon entries, the automatic extraction of acronyms and their meaning from corpora, and the search for cognates in a bilingual lexicon. All described operations and applications have been implemented with Xerox's WFSC tool.
A Framework for QoS-aware Execution of Workflows over the Cloud
Venue: arXiv cs.DC 2011
Year: 2011

The Cloud Computing paradigm is providing system architects with a new powerful tool for building scalable applications. Clouds allow allocation of resources on a "pay-as-you-go" model, so that additional resources can be requested during peak loads and released after that. However, this flexibility asks for appropriate dynamic reconfiguration strategies. In this paper we describe SAVER (qoS-Aware workflows oVER the Cloud), a QoS-aware algorithm for executing workflows involving Web Services hosted in a Cloud environment. SAVER allows execution of arbitrary workflows subject to response time constraints. SAVER uses a passive monitor to identify workload fluctuations based on the observed system response time. The information collected by the monitor is used by a planner component to identify the minimum number of instances of each Web Service which should be allocated in order to satisfy the response time constraint. SAVER uses a simple Queueing Network (QN) model to identify the optimal resource allocation. Specifically, the QN model is used to identify bottlenecks, and predict the system performance as Cloud resources are allocated or released. The parameters used to evaluate the model are those collected by the monitor, which means that SAVER does not require any particular knowledge of the Web Services and workflows being executed. Our approach has been validated through numerical simulations, whose results are reported in this paper.
A cuckoo hashing variant with improved memory utilization and insertion time
Venue: arXiv cs.DS 2011
Year: 2011

Cuckoo hashing [4] is a multiple choice hashing scheme in which each item can be placed in multiple locations, and collisions are resolved by moving items to their alternative locations. In the classical implementation of two-way cuckoo hashing, the memory is partitioned into contiguous disjoint fixed-size buckets. Each item is hashed to two buckets, and may be stored in any of the positions within those buckets. Ref. [2] analyzed a variation in which the buckets are contiguous and overlap. However, many systems retrieve data from secondary storage in same-size blocks called pages. Fetching a page is a relatively expensive process; but once a page is fetched, its contents can be accessed orders of magnitude faster. We utilize this property of memory retrieval, presenting a variant of cuckoo hashing incorporating the following constraint: each bucket must be fully contained in a single page, but buckets are not necessarily contiguous. Empirical results show that this modification increases memory utilization and decreases the number of iterations required to insert an item. If each item is hashed to two buckets of capacity two, the page size is 8, and each bucket is fully contained in a single page, the memory utilization equals 89.71% in the classical contiguous disjoint bucket variant, 93.78% in the contiguous overlapping bucket variant, and increases to 97.46% in our new non-contiguous bucket variant. When the memory utilization is 92% and we use breadth first search to look for a vacant position, the number of iterations required to insert a new item is dramatically reduced from 545 in the contiguous overlapping buckets variant to 52 in our new non-contiguous bucket variant. In addition to the empirical results, we present a theoretical lower bound on the memory utilization of our variation as a function of the page size.
Interference Alignment at Finite SNR for Time-Invariant Channels
Venue: arXiv cs.IT 2011
Year: 2011

An achievable rate region, based on lattice interference alignment, is derived for a class of time-invariant Gaussian interference channels with more than two users. The result is established via a new coding theorem for the two-user Gaussian multiple-access channel where both users use a single linear code. The class of interference channels treated is such that all interference channel gains are rational. For this class of interference channels, beyond recovering the known results on the degrees of freedom, an explicit rate region is derived for finite signal-to-noise ratios, shedding light on the nature of previously established asymptotic results.
Notes on a New Philosophy of Empirical Science
Venue: arXiv cs.LG 2011
Year: 2011

This book presents a methodology and philosophy of empirical science based on large scale lossless data compression. In this view a theory is scientific if it can be used to build a data compression program, and it is valuable if it can compress a standard benchmark database to a small size, taking into account the length of the compressor itself. This methodology therefore includes an Occam principle as well as a solution to the problem of demarcation. Because of the fundamental difficulty of lossless compression, this type of research must be empirical in nature: compression can only be achieved by discovering and characterizing empirical regularities in the data. Because of this, the philosophy provides a way to reformulate fields such as computer vision and computational linguistics as empirical sciences: the former by attempting to compress databases of natural images, the latter by attempting to compress large text databases. The book argues that the rigor and objectivity of the compression principle should set the stage for systematic progress in these fields. The argument is especially strong in the context of computer vision, which is plagued by chronic problems of evaluation. The book also considers the field of machine learning. Here the traditional approach requires that the models proposed to solve learning problems be extremely simple, in order to avoid overfitting. However, the world may contain intrinsically complex phenomena, which would require complex models to understand. The compression philosophy can justify complex models because of the large quantity of data being modeled (if the target database is 100 Gb, it is easy to justify a 10 Mb model). The complex models and abstractions learned on the basis of the raw data (images, language, etc) can then be reused to solve any specific learning problem, such as face recognition or machine translation.
A Sequence of Inequalities among Difference of Symmetric Divergence Measures
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we have considered two one parametric generalizations. These two generalizations have in articular the well known measures such as: J-divergence, Jensen-Shannon divergence and Arithmetic-Geometric mean divergence. These three measures are with logarithmic expressions. Also, we have particular cases the measures such as: Hellinger discrimination, symmetric chi-square divergence, and triangular discrimination. These three measures are also well-known in the literature of statistics, and are without logarithmic expressions. Still, we have one more non logarithmic measure as particular case calling it d-divergence. These seven measures bear an interesting inequality. Based on this inequality, we have considered different difference of divergence measures and established a sequence of inequalities among themselves.
A Multi-Hop Weighted Clustering of Homogenous MANETs Using Combined Closeness Index
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, a new multi-hop weighted clustering procedure is proposed for homogeneous Mobile Ad hoc networks. The algorithm generates double star embedded non-overlapping cluster structures, where each cluster is managed by a leader node and a substitute for the leader node (in case of failure of leader node). The weight of a node is a linear combination of six different graph theoretic parameters which deal with the communication capability of a node both in terms of quality and quantity, the relative closeness relationship between network nodes and the maximum and average distance traversed by a node for effective communication. This paper deals with the design and analysis of the algorithm and some of the graph theoretic/structural properties of the clusters obtained are also discussed.