OpenRaiser/Intern-Atlas huggingface dataset:
Macro and Micro Diversity Behaviors of Practical Dynamic Decode and Forward Relaying schemes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a practical implementation of the Dynamic Decode and Forward (DDF) protocol based on rateless codes and HARQ. We define the macro diversity order of a transmission from several intermittent sources to a single destination. Considering finite symbol alphabet used by the different sources, upper bounds on the achievable macro diversity order are derived. We analyse the diversity behavior of several relaying schemes for the DDF protocol, and we propose the Patching technique to increase both the macro and the micro diversity orders. The coverage gain for the open-loop transmission case and the spectral efficiency gain for the closed loop transmission case are illustrated by simulation results.
Hybrid complex network topologies are preferred for component-subscription in large-scale data-centres
Venue: arXiv cs.DC 2011
Year: 2011

We report on experiments exploring the interplay between the topology of the complex network of dependent components in a large-scale data-centre, and the robustness and scaling properties of that data-centre. In a previous paper [1] we used the SPECI large-scale data-centre simulator [2] to compare the robustness and scaling characteristics of data-centres whose dependent components are connected via Strogatz-Watts small-world (SW) networks [3], versus those organized as Barabasi-Albert scale-free (SF) networks [4], and found significant differences. In this paper, we present results from using the Klemm-Eguiliz (KE) construction method [5] to generate complex network topologies for data-centre component dependencies. The KE model has a control parameter μ\in[0,1]\inR that determines whether the networks generated are SW (0<μ<<1) or SF (μ=1) or a "hybrid" network topology part-way between SW and SF (0<μ<1). We find that the best scores for system-level performance metrics of the simulated data-centres are given by "hybrid" values of μ significantly different from pure-SW or pure-SF.
Labeling 3D scenes for Personal Assistant Robots
Venue: arXiv cs.RO 2011
Year: 2011

Inexpensive RGB-D cameras that give an RGB image together with depth data have become widely available. We use this data to build 3D point clouds of a full scene. In this paper, we address the task of labeling objects in this 3D point cloud of a complete indoor scene such as an office. We propose a graphical model that captures various features and contextual relations, including the local visual appearance and shape cues, object co-occurrence relationships and geometric relationships. With a large number of object classes and relations, the model's parsimony becomes important and we address that by using multiple types of edge potentials. The model admits efficient approximate inference, and we train it using a maximum-margin learning approach. In our experiments over a total of 52 3D scenes of homes and offices (composed from about 550 views, having 2495 segments labeled with 27 object classes), we get a performance of 84.06% in labeling 17 object classes for offices, and 73.38% in labeling 17 object classes for home scenes. Finally, we applied these algorithms successfully on a mobile robot for the task of finding an object in a large cluttered room.
Models and Techniques for Ensuring Reliability, Safety, Availability and Security of Large Scale Distributed Systems
Venue: arXiv cs.DC 2011
Year: 2011

17th International Conference on Control Systems and Computer Science (CSCS 17), Bucharest, Romania, May 26-29, 2009. Vol. 1, pp. 401-406, ISSN: 2066-4451.
Class-based Rough Approximation with Dominance Principle
Venue: arXiv cs.CC 2011
Year: 2011

Dominance-based Rough Set Approach (DRSA), as the extension of Pawlak's Rough Set theory, is effective and fundamentally important in Multiple Criteria Decision Analysis (MCDA). In previous DRSA models, the definitions of the upper and lower approximations are preserving the class unions rather than the singleton class. In this paper, we propose a new Class-based Rough Approximation with respect to a series of previous DRSA models, including Classical DRSA model, VC-DRSA model and VP-DRSA model. In addition, the new class-based reducts are investigated.
Typing a Core Binary Field Arithmetic in a Light Logic
Venue: arXiv cs.LO 2011
Year: 2011

We design a library for binary field arithmetic and we supply a core API which is completely developed in DLAL, extended with a fix point formula. Since DLAL is a restriction of linear logic where only functional programs with polynomial evaluation cost can be typed, we obtain the core of a functional programming setting for binary field arithmetic with built-in polynomial complexity.
Fingerprint: DWT, SVD Based Enhancement and Significant Contrast for Ridges and Valleys Using Fuzzy Measures
Venue: arXiv cs.CV 2011
Year: 2011

The performance of the Fingerprint recognition system will be more accurate with respect of enhancement for the fingerprint images. In this paper we develop a novel method for Fingerprint image contrast enhancement technique based on the discrete wavelet transform (DWT) and singular value decomposition (SVD) has been proposed. This technique is compared with conventional image equalization techniques such as standard general histogram equalization and local histogram equalization. An automatic histogram threshold approach based on a fuzziness measure is presented. Then, using an index of fuzziness, a similarity process is started to find the threshold point. A significant contrast between ridges and valleys of the best, medium and poor finger image features to extract from finger images and get maximum recognition rate using fuzzy measures. The experimental results show the recognition of superiority of the proposed method to get maximum performance up gradation to the implementation of this approach.
Entropy of Telugu
Venue: arXiv cs.CL 2011
Year: 2011

This paper presents an investigation of the entropy of the Telugu script. Since this script is syllabic, and not alphabetic, the computation of entropy is somewhat complicated.
Black Hole Search with Finite Automata Scattered in a Synchronous Torus
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of locating a black hole in synchronous anonymous networks using finite state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no finite team of finite state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on the number of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens.
IBSEAD: - A Self-Evolving Self-Obsessed Learning Algorithm for Machine Learning
Venue: arXiv cs.LG 2011
Year: 2011

We present IBSEAD or distributed autonomous entity systems based Interaction - a learning algorithm for the computer to self-evolve in a self-obsessed manner. This learning algorithm will present the computer to look at the internal and external environment in series of independent entities, which will interact with each other, with and/or without knowledge of the computer's brain. When a learning algorithm interacts, it does so by detecting and understanding the entities in the human algorithm. However, the problem with this approach is that the algorithm does not consider the interaction of the third party or unknown entities, which may be interacting with each other. These unknown entities in their interaction with the non-computer entities make an effect in the environment that influences the information and the behaviour of the computer brain. Such details and the ability to process the dynamic and unsettling nature of these interactions are absent in the current learning algorithm such as the decision tree learning algorithm. IBSEAD is able to evaluate and consider such algorithms and thus give us a better accuracy in simulation of the highly evolved nature of the human brain. Processes such as dreams, imagination and novelty, that exist in humans are not fully simulated by the existing learning algorithms. Also, Hidden Markov models (HMM) are useful in finding "hidden" entities, which may be known or unknown. However, this model fails to consider the case of unknown entities which maybe unclear or unknown. IBSEAD is better because it considers three types of entities- known, unknown and invisible. We present our case with a comparison of existing algorithms in known environments and cases and present the results of the experiments using dry run of the simulated runs of the existing machine learning algorithms versus IBSEAD.
External Memory Orthogonal Range Reporting with Fast Updates
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we describe data structures for orthogonal range reporting in external memory that support fast update operations. The query costs either match the query costs of the best previously known data structures or differ by a small multiplicative factor.
Low-Complexity Adaptive Channel Estimation over Multipath Rayleigh Fading Non-Stationary Channels Under CFO
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose novel low-complexity adaptive channel estimation techniques for mob ile wireless chan- n els in presence of Rayleigh fading, carrier frequency offsets (CFO) and random channel variations. We show that the selective p artial update of the estimated channel tap-weight vector offers a better trade-off between the performance and computational complexity, compared to the full update of the estimated channel tap-weight vector. We evaluate the mean-square weight error of th e proposed methods and demonstrate the usefulness of its via simulation studies.
SIP APIs for Voice and Video Communications on the Web
Venue: arXiv cs.NI 2011
Year: 2011

Existing standard protocols for the web and Internet telephony fail to deliver real-time interactive communication from within a web browser. In particular, the client-server web protocol over reliable TCP is not always suitable for end-to-end low latency media path needed for interactive voice and video communication. To solve this, we compare the available platform options using the existing technologies such as modifying the web programming language and protocol, using an existing web browser plugin, and a separate host resident application that the web browser can talk to. We argue that using a separate application as an adaptor is a promising short term as well as long-term strategy for voice and video communications on the web. Our project aims at developing the open technology and sample implementations for web-based real-time voice and video communication applications. We describe the architecture of our project including (1) a RESTful web communication API over HTTP inspired by SIP message flows, (2) a web-friendly set of metadata for session description, and (3) an UDP-based end-to-end media path. All other telephony functions reside in the web application itself and/or in web feature servers. The adaptor approach allows us to easily add new voice and video codecs and NAT traversal technologies such as Host Identity Protocol. We want to make web-based communication accessible to millions of web developers, maximize the end user experience and security, and preserve the huge global investment in and experience from SIP systems while adhering to web standards and development tools as much as possible. We have created an open source prototype that allows you to freely use the conference application by directing a browser to the conference URL.
Quadratic-time Algorithm for the String Constrained LCS Problem
Venue: arXiv cs.DS 2011
Year: 2011

The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.
Competitive Coevolution through Evolutionary Complexification
Venue: arXiv cs.AI 2011
Year: 2011

Two major goals in machine learning are the discovery and improvement of solutions to complex problems. In this paper, we argue that complexification, i.e. the incremental elaboration of solutions through adding new structure, achieves both these goals. We demonstrate the power of complexification through the NeuroEvolution of Augmenting Topologies (NEAT) method, which evolves increasingly complex neural network architectures. NEAT is applied to an open-ended coevolutionary robot duel domain where robot controllers compete head to head. Because the robot duel domain supports a wide range of strategies, and because coevolution benefits from an escalating arms race, it serves as a suitable testbed for studying complexification. When compared to the evolution of networks with fixed structure, complexifying evolution discovers significantly more sophisticated strategies. The results suggest that in order to discover and improve complex solutions, evolution, and search in general, should be allowed to complexify as well as optimize.
Restricted Value Iteration: Theory and Algorithms
Venue: arXiv cs.AI 2011
Year: 2011

Value iteration is a popular algorithm for finding near optimal policies for POMDPs. It is inefficient due to the need to account for the entire belief space, which necessitates the solution of large numbers of linear programs. In this paper, we study value iteration restricted to belief subsets. We show that, together with properly chosen belief subsets, restricted value iteration yields near-optimal policies and we give a condition for determining whether a given belief subset would bring about savings in space and time. We also apply restricted value iteration to two interesting classes of POMDPs, namely informative POMDPs and near-discernible POMDPs.
Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms
Venue: arXiv cs.AI 2011
Year: 2011

Inductive learning is based on inferring a general rule from a finite data set and using it to label new data. In transduction one attempts to solve the problem of using a labeled training set to label a set of unlabeled points, which are given to the learner prior to learning. Although transduction seems at the outset to be an easier task than induction, there have not been many provably useful algorithms for transduction. Moreover, the precise relation between induction and transduction has not yet been determined. The main theoretical developments related to transduction were presented by Vapnik more than twenty years ago. One of Vapnik's basic results is a rather tight error bound for transductive classification based on an exact computation of the hypergeometric tail. While tight, this bound is given implicitly via a computational routine. Our first contribution is a somewhat looser but explicit characterization of a slightly extended PAC-Bayesian version of Vapnik's transductive bound. This characterization is obtained using concentration inequalities for the tail of sums of random variables obtained by sampling without replacement. We then derive error bounds for compression schemes such as (transductive) support vector machines and for transduction algorithms based on clustering. The main observation used for deriving these new error bounds and algorithms is that the unlabeled test points, which in the transductive setting are known in advance, can be used in order to construct useful data dependent prior distributions over the hypothesis space.
Fixed parameter algorithms for restricted coloring problems
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$-tidy graphs and $(q,q-4)$-graphs, for every fixed $q$. These classes include cographs, $P_4$-sparse and $P_4$-lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$, which is the minimum $q$ such that $G$ is a $(q,q-4)$-graph. We also prove that every connected $(q,q-4)$-graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.
Formal Visual Modeling of Real-Time Systems in e-Motions: Two Case Studies
Venue: arXiv cs.SE 2011
Year: 2011

e-Motions is an Eclipse-based visual timed model transformation framework with a Real-Time Maude semantics that supports the usual Maude formal analysis methods, including simulation, reachability analysis, and LTL model checking. e-Motions is characterized by a novel and powerful set of constructs for expressing timed behaviors. In this paper we illustrate the use of these constructs --- and thereby implicitly investigate their suitability to define real-time systems in an intuitive way --- to define and formally analyze two prototypical and very different real-time systems: (i) a simple round trip time protocol for computing the time it takes a message to travel from one node to another, and back; and (ii) the EDF scheduling algorithm.
Towards a Reliable Framework of Uncertainty-Based Group Decision Support System
Venue: arXiv cs.SY 2011
Year: 2011

This study proposes a framework of Uncertainty-based Group Decision Support System (UGDSS). It provides a platform for multiple criteria decision analysis in six aspects including (1) decision environment, (2) decision problem, (3) decision group, (4) decision conflict, (5) decision schemes and (6) group negotiation. Based on multiple artificial intelligent technologies, this framework provides reliable support for the comprehensive manipulation of applications and advanced decision approaches through the design of an integrated multi-agents architecture.
Optimal Folding of Data Flow Graphs based on Finite Projective Geometry using Lattice Embedding
Venue: arXiv cs.DM 2011
Year: 2011

A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry(PG) based balanced bipartite graphs. Many of these applications are actively being researched upon. Almost all these applications need bipartite graphs of the order of tens of thousands in practice, whose nodes represent parallel computations. To reduce its implementation cost, reducing amount of system/hardware resources during design is an important engineering objective. In this context, we present a scheme to reduce resource utilization when performing computations derived from PG-based graphs. In a fully parallel design based on PG concepts, the number of processing units is equal to the number of vertices, each performing an atomic computation. To reduce the number of processing units used for implementation, we present an easy way of partitioning the vertex set. Each block of partition is then assigned to a processing unit. A processing unit performs the computations corresponding to the vertices in the block assigned to it in a sequential fashion, thus creating the effect of folding the overall computation. These blocks have certain symmetric properties that enable us to develop a conflict-free schedule. The scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. This paper reports two folding schemes, which are based on same lattice embedding approach, based on partitioning. We first provide a scheme for a projective space of dimension five, and the corresponding schedules. Both the folding schemes that we present have been verified by both simulation and hardware prototyping for different applications. We later generalize this scheme to arbitrary projective spaces.
Unbounded Contention Resolution in Multiple-Access Channels
Venue: arXiv cs.DC 2011
Year: 2011

A frequent problem in settings where a unique resource must be shared among users is how to resolve the contention that arises when all of them must use it, but the resource allows only for one user each time. The application of efficient solutions for this problem spans a myriad of settings such as radio communication networks or databases. For the case where the number of users is unknown, recent work has yielded fruitful results for local area networks and radio networks, although either a (possibly loose) upper bound on the number of users needs to be known, or the solution is suboptimal, or it is only implicit or embedded in other problems, with bounds proved only asymptotically. In this paper, under the assumption that collision detection or information on the number of contenders is not available, we present a novel protocol for contention resolution in radio networks, and we recreate a protocol previously used for other problems, tailoring the constants for our needs. In contrast with previous work, both protocols are proved to be optimal up to a small constant factor and with high probability for big enough number of contenders. Additionally, the protocols are evaluated and contrasted with the previous work by extensive simulations. The evaluation shows that the complexity bounds obtained by the analysis are rather tight, and that both protocols proposed have small and predictable complexity for many system sizes (unlike previous proposals).
Completeness of Epistemic Coalition Logic with Group Knowledge
Venue: arXiv cs.LO 2011
Year: 2011

Coalition logic is one of the most popular logics for multi-agent systems. While epistemic extensions of coalition logic have received much attention, existence of their complete axiomatisations has so far been an open problem. In this paper we settle several of those problems. We prove completeness for epistemic coalition logic with common knowledge, with distributed knowledge, and with both common and distributed knowledge, respectively.