OpenRaiser/Intern-Atlas huggingface dataset:
Stacked OSTBC: Error Performance and Rate Analysis
Venue: arXiv cs.IT 2007
Year: 2007

It is well known, that the Alamouti scheme is the only space-time code from orthogonal design achieving the capacity of a multiple-input multiple-output (MIMO) wireless communication system with n_T=2 transmit antennas and n_R=1 receive antenna. In this work, we propose the n-times stacked Alamouti scheme for n_T=2n transmit antennas and show that this scheme achieves the capacity in the case of n_R=1 receive antenna. This result may regarded as an extension of the Alamouti case. For the more general case of more than one receive antenna, we show that if the number of transmit antennas is higher than the number of receive antennas we achieve a high portion of the capacity with this scheme. Further, we show that the MIMO capacity is at most twice the rate achieved with the proposed scheme for all SNR. We derive lower and upper bounds for the rate achieved with this scheme and compare it with upper and lower bounds for the capacity. In addition to the capacity analysis based on the assumption of a coherent channel, we analyze the error rate performance of the stacked OSTBC with the optimal ML detector and with the suboptimal lattice-reduction (LR) aided zero-forcing detector. We compare the error rate performance of the stacked OSTBC with spatial multiplexing (SM) and full-diversity achieving schemes. Finally, we illustrate the theoretical results by numerical simulations.
RS-232 Led Board
Venue: arXiv cs.OH 2007
Year: 2007

This article demonstrates how to develop a Microchip PIC16F84 based device that supports RS-232 interface with PC. Circuit (LED Board) design and software development will be discussed. PicBasic Pro Compiler from microEngineering Labs, Inc. is used for PIC programming. Development of LED Board Control Console using C/C++ is also briefly discussed. The project requires basic work experience with Microchip PICs, serial communication and programming.
Autonomous tools for Grid management, monitoring and optimization
Venue: arXiv cs.DC 2007
Year: 2007

We outline design and lines of development of autonomous tools for the computing Grid management, monitoring and optimization. The management is proposed to be based on the notion of utility. Grid optimization is considered to be application-oriented. A generic Grid simulator is proposed as an optimization tool for Grid structure and functionality.
International Standard for a Linguistic Annotation Framework
Venue: arXiv cs.CL 2007
Year: 2007

This paper describes the Linguistic Annotation Framework under development within ISO TC37 SC4 WG1. The Linguistic Annotation Framework is intended to serve as a basis for harmonizing existing language resources as well as developing new ones.
Lattices for Distributed Source Coding: Jointly Gaussian Sources and Reconstruction of a Linear Function
Venue: arXiv cs.IT 2007
Year: 2007

Consider a pair of correlated Gaussian sources (X1,X2). Two separate encoders observe the two components and communicate compressed versions of their observations to a common decoder. The decoder is interested in reconstructing a linear combination of X1 and X2 to within a mean-square distortion of D. We obtain an inner bound to the optimal rate-distortion region for this problem. A portion of this inner bound is achieved by a scheme that reconstructs the linear function directly rather than reconstructing the individual components X1 and X2 first. This results in a better rate region for certain parameter values. Our coding scheme relies on lattice coding techniques in contrast to more prevalent random coding arguments used to demonstrate achievable rate regions in information theory. We then consider the case of linear reconstruction of K sources and provide an inner bound to the optimal rate-distortion region. Some parts of the inner bound are achieved using the following coding structure: lattice vector quantization followed by "correlated" lattice-structured binning.
Workspace and Kinematic Analysis of the VERNE machine
Venue: arXiv cs.RO 2007
Year: 2007

This paper describes the workspace and the inverse and direct kinematic analysis of the VERNE machine, a serial/parallel 5-axis machine tool designed by Fatronik for IRCCyN. This machine is composed of a three-degree-of-freedom (DOF) parallel module and a two-DOF serial tilting table. The parallel module consists of a moving platform that is connected to a fixed base by three non-identical legs. This feature involves (i) a simultaneous combination of rotation and translation for the moving platform, which is balanced by the tilting table and (ii) workspace whose shape and volume vary as a function of the tool length. This paper summarizes results obtained in the context of the European projects NEXT ("Next Generation of Productions Systems").
The Kinetostatic Optimization of a Novel Prismatic Drive
Venue: arXiv cs.RO 2007
Year: 2007

The design of a mechanical transmission taking into account the transmitted forces is reported in this paper. This transmission is based on Slide-o-Cam, a cam mechanism with multiple rollers mounted on a common translating follower. The design of Slide-o-Cam, a transmission intended to produce a sliding motion from a turning drive, or vice versa, was reported elsewhere. This transmission provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. The pressure angle is a suitable performance index for this transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame. To assess the transmission capability of the mechanism, the Hertz formula is introduced to calculate the stresses on the rollers and on the cams. The final transmission is intended to replace the current ball-screws in the Orthoglide, a three-DOF parallel robot for the production of translational motions, currently under development for machining applications at Ecole Centrale de Nantes.
L'orthoglide : une machine-outil rapide d'architecture parallèle isotrope
Venue: arXiv cs.RO 2007
Year: 2007

This article presents the Orthoglide project. The purpose of this project is the realization of a prototype of machine tool to three degrees of translation. The characteristic of this machine is a parallel kinematic architecture optimized to obtain a compact workspace with homogeneous performance. For that, the principal criterion of design which was used is the isotropy.
Constant-degree graph expansions that preserve the treewidth
Venue: arXiv cs.DM 2007
Year: 2007

Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an _expansion_ of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? Our work answers the above question affirmatively. We prove that any simple undirected graph G=(V, E) admits an expansion G'=(V', E') with the maximum degree <= 3 and treewidth(G') <= treewidth(G)+1. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided.
Understanding the Characteristics of Internet Short Video Sharing: YouTube as a Case Study
Venue: arXiv cs.NI 2007
Year: 2007

Established in 2005, YouTube has become the most successful Internet site providing a new generation of short video sharing service. Today, YouTube alone comprises approximately 20% of all HTTP traffic, or nearly 10% of all traffic on the Internet. Understanding the features of YouTube and similar video sharing sites is thus crucial to their sustainable development and to network traffic engineering. In this paper, using traces crawled in a 3-month period, we present an in-depth and systematic measurement study on the characteristics of YouTube videos. We find that YouTube videos have noticeably different statistics compared to traditional streaming videos, ranging from length and access pattern, to their active life span, ratings, and comments. The series of datasets also allows us to identify the growth trend of this fast evolving Internet site in various aspects, which has seldom been explored before. We also look closely at the social networking aspect of YouTube, as this is a key driving force toward its success. In particular, we find that the links to related videos generated by uploaders' choices form a small-world network. This suggests that the videos have strong correlations with each other, and creates opportunities for developing novel caching or peer-to-peer distribution schemes to efficiently deliver videos to end users.
Queues, stores, and tableaux
Venue: arXiv cs.DM 2007
Year: 2007

Consider the single server queue with an infinite buffer and a FIFO discipline, either of type M/M/1 or Geom/Geom/1. Denote by A the arrival process and by s the services. Assume the stability condition to be satisfied. Denote by D the departure process in equilibrium and by r the time spent by the customers at the very back of the queue. We prove that (D,r) has the same law as (A,s) which is an extension of the classical Burke Theorem. In fact, r can be viewed as the departures from a dual storage model. This duality between the two models also appears when studying the transient behavior of a tandem by means of the RSK algorithm: the first and last row of the resulting semi-standard Young tableau are respectively the last instant of departure in the queue and the total number of departures in the store.
Multiuser Successive Refinement and Multiple Description Coding
Venue: arXiv cs.IT 2007
Year: 2007

We consider the multiuser successive refinement (MSR) problem, where the users are connected to a central server via links with different noiseless capacities, and each user wishes to reconstruct in a successive-refinement fashion. An achievable region is given for the two-user two-layer case and it provides the complete rate-distortion region for the Gaussian source under the MSE distortion measure. The key observation is that this problem includes the multiple description (MD) problem (with two descriptions) as a subsystem, and the techniques useful in the MD problem can be extended to this case. We show that the coding scheme based on the universality of random binning is sub-optimal, because multiple Gaussian side informations only at the decoders do incur performance loss, in contrast to the case of single side information at the decoder. We further show that unlike the single user case, when there are multiple users, the loss of performance by a multistage coding approach can be unbounded for the Gaussian source. The result suggests that in such a setting, the benefit of using successive refinement is not likely to justify the accompanying performance loss. The MSR problem is also related to the source coding problem where each decoder has its individual side information, while the encoder has the complete set of the side informations. The MSR problem further includes several variations of the MD problem, for which the specialization of the general result is investigated and the implication is discussed.
Image Authentication Based on Neural Networks
Venue: arXiv cs.MM 2007
Year: 2007

Neural network has been attracting more and more researchers since the past decades. The properties, such as parameter sensitivity, random similarity, learning ability, etc., make it suitable for information protection, such as data encryption, data authentication, intrusion detection, etc. In this paper, by investigating neural networks' properties, the low-cost authentication method based on neural networks is proposed and used to authenticate images or videos. The authentication method can detect whether the images or videos are modified maliciously. Firstly, this chapter introduces neural networks' properties, such as parameter sensitivity, random similarity, diffusion property, confusion property, one-way property, etc. Secondly, the chapter gives an introduction to neural network based protection methods. Thirdly, an image or video authentication scheme based on neural networks is presented, and its performances, including security, robustness and efficiency, are analyzed. Finally, conclusions are drawn, and some open issues in this field are presented.
Note on edge-colored graphs and digraphs without properly colored cycles
Venue: arXiv cs.DM 2007
Year: 2007

We study the following two functions: d(n,c) and $\vec{d}(n,c)$; d(n,c) ($\vec{d}(n,c)$) is the minimum number k such that every c-edge-colored undirected (directed) graph of order n and minimum monochromatic degree (out-degree) at least k has a properly colored cycle. Abouelaoualim et al. (2007) stated a conjecture which implies that d(n,c)=1. Using a recursive construction of c-edge-colored graphs with minimum monochromatic degree p and without properly colored cycles, we show that $d(n,c)\ge {1 \over c}(\log_cn -\log_c\log_cn)$ and, thus, the conjecture does not hold. In particular, this inequality significantly improves a lower bound on $\vec{d}(n,2)$ obtained by Gutin, Sudakov and Yeo in 1998.
Side-information Scalable Source Coding
Venue: arXiv cs.IT 2007
Year: 2007

The problem of side-information scalable (SI-scalable) source coding is considered in this work, where the encoder constructs a progressive description, such that the receiver with high quality side information will be able to truncate the bitstream and reconstruct in the rate distortion sense, while the receiver with low quality side information will have to receive further data in order to decode. We provide inner and outer bounds for general discrete memoryless sources. The achievable region is shown to be tight for the case that either of the decoders requires a lossless reconstruction, as well as the case with degraded deterministic distortion measures. Furthermore we show that the gap between the achievable region and the outer bounds can be bounded by a constant when square error distortion measure is used. The notion of perfectly scalable coding is introduced as both the stages operate on the Wyner-Ziv bound, and necessary and sufficient conditions are given for sources satisfying a mild support condition. Using SI-scalable coding and successive refinement Wyner-Ziv coding as basic building blocks, a complete characterization is provided for the important quadratic Gaussian source with multiple jointly Gaussian side-informations, where the side information quality does not have to be monotonic along the scalable coding order. Partial result is provided for the doubly symmetric binary source with Hamming distortion when the worse side information is a constant, for which one of the outer bound is strictly tighter than the other one.
Comments on the Reliability of Lawson and Hanson's Linear Distance Programming Algorithm: Subroutine LDP
Venue: arXiv cs.MS 2007
Year: 2007

This brief paper: (1) Discusses strategies to generate random test cases that can be used to extensively test any Linear Distance Program (LDP) software. (2) Gives three numerical examples of input cases generated by this strategy that cause problems in the Lawson and Hanson LDP module. (3) Proposes, as a standard matter of acceptable implementation procedures, that (unless it is done internally in the software itself, but, in general, this seems to be much rarer than one would expect) all users should test the returned output from any LDP module for self-consistency since it incurs only a small amount of added computational overhead and it is not hard to do.
Why the relational data model can be considered as a formal basis for group operations in object-oriented systems
Venue: arXiv cs.DB 2007
Year: 2007

Relational data model defines a specification of a type "relation". However, its simplicity does not mean that the system implementing this model must operate with structures having the same simplicity. We consider two principles allowing create a system which combines object-oriented paradigm (OOP) and relational data model (RDM) in one framework. The first principle -- "complex data in encapsulated domains" -- is well known from The Third Manifesto by Date and Darwen. The second principle --"data complexity in names"-- is the basis for a system where data are described as complex objects and uniquely represented as a set of relations. Names of these relations and names of their attributes are combinations of names entered in specifications of the complex objects. Below, we consider the main properties of such a system.
Quasi-stationary distributions as centrality measures of reducible graphs
Venue: arXiv cs.NI 2007
Year: 2007

Random walk can be used as a centrality measure of a directed graph. However, if the graph is reducible the random walk will be absorbed in some subset of nodes and will never visit the rest of the graph. In Google PageRank the problem was solved by introduction of uniform random jumps with some probability. Up to the present, there is no clear criterion for the choice this parameter. We propose to use parameter-free centrality measure which is based on the notion of quasi-stationary distribution. Specifically we suggest four quasi-stationary based centrality measures, analyze them and conclude that they produce approximately the same ranking. The new centrality measures can be applied in spam detection to detect ``link farms'' and in image search to find photo albums.
ADS-Directory Services for Mobile Ad-Hoc Networks Based on an Information Market Model
Venue: arXiv cs.NI 2007
Year: 2007

Ubiquitous computing based on small mobile devices using wireless communication links is becoming very attractive. The computational power and storage capacities provided allow the execution of sophisticated applications. Due to the fact that sharing of information is a central problem for distributed applications, the development of self organizing middleware services providing high level interfaces for information managing is essential. ADS is a directory service for mobile ad-hoc networks dealing with local and nearby information as well as providing access to distant information. The approach discussed throughout this paper is based upon the concept of information markets.
Reconstruction of Protein-Protein Interaction Pathways by Mining Subject-Verb-Objects Intermediates
Venue: arXiv cs.IR 2007
Year: 2007

The exponential increase in publication rate of new articles is limiting access of researchers to relevant literature. This has prompted the use of text mining tools to extract key biological information. Previous studies have reported extensive modification of existing generic text processors to process biological text. However, this requirement for modification had not been examined. In this study, we have constructed Muscorian, using MontyLingua, a generic text processor. It uses a two-layered generalization-specialization paradigm previously proposed where text was generically processed to a suitable intermediate format before domain-specific data extraction techniques are applied at the specialization layer. Evaluation using a corpus and experts indicated 86-90% precision and approximately 30% recall in extracting protein-protein interactions, which was comparable to previous studies using either specialized biological text processing tools or modified existing tools. Our study had also demonstrated the flexibility of the two-layered generalization-specialization paradigm by using the same generalization layer for two specialized information extraction tasks.
Nodally 3-connected planar graphs and convex combination mappings
Venue: arXiv cs.CG 2007
Year: 2007

A convex combination mapping of a planar graph is a plane mapping in which the external vertices are mapped to the corners of a convex polygon and every internal vertex is a proper weighted average of its neighbours. If a planar graph is nodally 3-connected or triangulated then every such mapping is an embedding (Tutte, Floater). We give a simple characterisation of nodally 3-connected planar graphs, and generalise the above result to any planar graph which admits any convex embedding.
A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods
Venue: arXiv cs.DM 2007
Year: 2007

We study the problem of estimating the best B term Fourier representation for a given frequency-sparse signal (i.e., vector) $\textbf{A}$ of length $N \gg B$. More explicitly, we investigate how to deterministically identify B of the largest magnitude frequencies of $\hat{\textbf{A}}$, and estimate their coefficients, in polynomial$(B,\log N)$ time. Randomized sub-linear time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem. However, for failure intolerant applications such as those involving mission-critical hardware designed to process many signals over a long lifetime, deterministic algorithms with no probability of failure are highly desirable. In this paper we build on the deterministic Compressed Sensing results of Cormode and Muthukrishnan (CM) \cite{CMDetCS3,CMDetCS1,CMDetCS2} in order to develop the first known deterministic sub-linear time sparse Fourier Transform algorithm suitable for failure intolerant applications. Furthermore, in the process of developing our new Fourier algorithm, we present a simplified deterministic Compressed Sensing algorithm which improves on CM's algebraic compressibility results while simultaneously maintaining their results concerning exponential decay.
On Optimal Turbo Decoding of Wideband MIMO-OFDM Systems Under Imperfect Channel State Information
Venue: arXiv cs.NI 2007
Year: 2007

We consider the decoding of bit interleaved coded modulation (BICM) applied to both multiband and MIMO OFDM systems for typical scenarios where only a noisy (possibly very bad) estimate of the channel is provided by sending a limited number of pilot symbols. First, by using a Bayesian framework involving the channel a posteriori density, we adopt a practical decoding metric that is robust to the presence of channel estimation errors. Then this metric is used in the demapping part of BICM multiband and MIMO OFDM receivers. We also compare our results with the performance of a mismatched decoder that replaces the channel by its estimate in the decoding metric. Numerical results over both realistic UWB and theoretical Rayleigh fading channels show that the proposed method provides significant gain in terms of bit error rate compared to the classical mismatched detector, without introducing any additional complexity.
Learning Phonotactics Using ILP
Venue: arXiv cs.CL 2007
Year: 2007

This paper describes experiments on learning Dutch phonotactic rules using Inductive Logic Programming, a machine learning discipline based on inductive logical operators. Two different ways of approaching the problem are experimented with, and compared against each other as well as with related work on the task. The results show a direct correspondence between the quality and informedness of the background knowledge and the constructed theory, demonstrating the ability of ILP to take good advantage of the prior domain knowledge available. Further research is outlined.
Empirical entropy in context
Venue: arXiv cs.IT 2007
Year: 2007

We trace the history of empirical entropy, touching briefly on its relation to Markov processes, normal numbers, Shannon entropy, the Chomsky hierarchy, Kolmogorov complexity, Ziv-Lempel compression, de Bruijn sequences and stochastic complexity.