OpenRaiser/Intern-Atlas huggingface dataset:
The Necessity of Relay Selection
Venue: arXiv cs.IT 2010
Year: 2010

We determine necessary conditions on the structure of symbol error rate (SER) optimal quantizers for limited feedback beamforming in wireless networks with one transmitter-receiver pair and R parallel amplify-and-forward relays. We call a quantizer codebook "small" if its cardinality is less than R, and "large" otherwise. A "d-codebook" depends on the power constraints and can be optimized accordingly, while an "i-codebook" remains fixed. It was previously shown that any i-codebook that contains the single-relay selection (SRS) codebook achieves the full-diversity order, R. We prove the following: Every full-diversity i-codebook contains the SRS codebook, and thus is necessarily large. In general, as the power constraints grow to infinity, the limit of an optimal large d-codebook contains an SRS codebook, provided that it exists. For small codebooks, the maximal diversity is equal to the codebook cardinality. Every diversity-optimal small i-codebook is an orthogonal multiple-relay selection (OMRS) codebook. Moreover, the limit of an optimal small d-codebook is an OMRS codebook. We observe that SRS is nothing but a special case of OMRS for codebooks with cardinality equal to R. As a result, we call OMRS as "the universal necessary condition" for codebook optimality. Finally, we confirm our analytical findings through simulations.
On Beamformer Design for Multiuser MIMO Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers several linear beamformer design paradigms for multiuser time-invariant multiple-input multiple-output interference channels. Notably, interference alignment and sum-rate based algorithms such as the maximum signal-to-interference-plus noise (max-SINR) algorithm are considered. Optimal linear beamforming under interference alignment consists of two layers; an inner precoder and decoder (or receive filter) accomplish interference alignment to eliminate inter-user interference, and an outer precoder and decoder diagonalize the effective single-user channel resulting from the interference alignment by the inner precoder and decoder. The relationship between this two-layer beamforming and the max-SINR algorithm is established at high signal-to-noise ratio. Also, the optimality of the max-SINR algorithm within the class of linear beamforming algorithms, and its local convergence with exponential rate, are established at high signal-to-noise ratio.
A Process Calculus for Expressing Finite Place/Transition Petri Nets
Venue: arXiv cs.LO 2010
Year: 2010

We introduce the process calculus Multi-CCS, which extends conservatively CCS with an operator of strong prefixing able to model atomic sequences of actions as well as multiparty synchronization. Multi-CCS is equipped with a labeled transition system semantics, which makes use of a minimal structural congruence. Multi-CCS is also equipped with an unsafe P/T Petri net semantics by means of a novel technique. This is the first rich process calculus, including CCS as a subcalculus, which receives a semantics in terms of unsafe, labeled P/T nets. The main result of the paper is that a class of Multi-CCS processes, called finite-net processes, is able to represent all finite (reduced) P/T nets.
Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Applications in Cryptanalysis
Venue: arXiv cs.SC 2010
Year: 2010

Efficient characteristic set methods for computing solutions of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of solutions of a proper and monic (or regular) triangular set is given. An improved zero decomposition algorithm which can be used to reduce the zero set of an equation system in general form to the union of zero sets of monic proper triangular sets is proposed. As a consequence, we can give an explicit formula for the number of solutions of an equation system. Bitsize complexity for the algorithm is given in the case of Boolean polynomials. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials are effectively controlled. The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations.
Extending ArXiv.org to Achieve Open Peer Review and Publishing
Venue: arXiv cs.OH 2010
Year: 2010

Today's peer review process for scientific articles is unnecessarily opaque and offers few incentives to referees. Likewise, the publishing process is unnecessarily inefficient and its results are only rarely made freely available to the public. Here we outline a comparatively simple extension of arXiv.org, an online preprint archive widely used in the mathematical and physical sciences, that addresses both of these problems. Under the proposal, editors invite referees to write public and signed reviews to be attached to the posted preprints, and then elevate selected articles to "published" status.
On the Benefit of Virtualization: Strategies for Flexible Server Allocation
Venue: arXiv cs.NI 2010
Year: 2010

Virtualization technology facilitates a dynamic, demand-driven allocation and migration of servers. This paper studies how the flexibility offered by network virtualization can be used to improve Quality-of-Service parameters such as latency, while taking into account allocation costs. A generic use case is considered where both the overall demand issued for a certain service (for example, an SAP application in the cloud, or a gaming application) as well as the origins of the requests change over time (e.g., due to time zone effects or due to user mobility), and we present online and optimal offline strategies to compute the number and location of the servers implementing this service. These algorithms also allow us to study the fundamental benefits of dynamic resource allocation compared to static systems. Our simulation results confirm our expectations that the gain of flexible server allocation is particularly high in scenarios with moderate dynamics.
n-Channel Asymmetric Entropy-Constrained Multiple-Description Lattice Vector Quantization
Venue: arXiv cs.IT 2010
Year: 2010

This paper is about the design and analysis of an index-assignment (IA) based multiple-description coding scheme for the n-channel asymmetric case. We use entropy constrained lattice vector quantization and restrict attention to simple reconstruction functions, which are given by the inverse IA function when all descriptions are received or otherwise by a weighted average of the received descriptions. We consider smooth sources with finite differential entropy rate and MSE fidelity criterion. As in previous designs, our construction is based on nested lattices which are combined through a single IA function. The results are exact under high-resolution conditions and asymptotically as the nesting ratios of the lattices approach infinity. For any n, the design is asymptotically optimal within the class of IA-based schemes. Moreover, in the case of two descriptions and finite lattice vector dimensions greater than one, the performance is strictly better than that of existing designs. In the case of three descriptions, we show that in the limit of large lattice vector dimensions, points on the inner bound of Pradhan et al. can be achieved. Furthermore, for three descriptions and finite lattice vector dimensions, we show that the IA-based approach yields, in the symmetric case, a smaller rate loss than the recently proposed source-splitting approach.
Hypo-Steiner heuristic for multicast routing in all-optical WDM mesh networks
Venue: arXiv cs.NI 2010
Year: 2010

In sparse light splitting all-optical WDM networks, the more destinations a light-tree can accommodate, the fewer light-trees andwavelengths amulticast session will require. In this article, a Hypo-Steiner light-tree algorithm (HSLT) is proposed to construct a HSLT light-tree to include as many destinations as possible. The upper bound cost of the light-trees built by HSLT is given as N(N -1)/2, where N is the number of nodes in the network. The analytical model proves that, under the same condition, more destinations could be held in a HSLT than a Member-Only (Zhang et al., J. Lightware Technol, 18(12), 1917-1927 2000.) light-tree. Extensive simulations not only validate the proof but also show that the proposed heuristic outperforms the existing multicast routing algorithms by a large margin in terms of link stress, throughput, and efficiency ofwavelength usage.
Testing by C++ template metaprograms
Venue: arXiv cs.SE 2010
Year: 2010

Testing is one of the most indispensable tasks in software engineering. The role of testing in software development has grown significantly because testing is able to reveal defects in the code in an early stage of development. Many unit test frameworks compatible with C/C++ code exist, but a standard one is missing. Unfortunately, many unsolved problems can be mentioned with the existing methods, for example usually external tools are necessary for testing C++ programs. In this paper we present a new approach for testing C++ programs. Our solution is based on C++ template metaprogramming facilities, so it can work with the standard-compliant compilers. The metaprogramming approach ensures that the overhead of testing is minimal at runtime. This approach also supports that the specification language can be customized among other advantages. Nevertheless, the only necessary tool is the compiler itself.
Survey on Various Gesture Recognition Techniques for Interfacing Machines Based on Ambient Intelligence
Venue: arXiv cs.AI 2010
Year: 2010

Gesture recognition is mainly apprehensive on analyzing the functionality of human wits. The main goal of gesture recognition is to create a system which can recognize specific human gestures and use them to convey information or for device control. Hand gestures provide a separate complementary modality to speech for expressing ones ideas. Information associated with hand gestures in a conversation is degree,discourse structure, spatial and temporal structure. The approaches present can be mainly divided into Data-Glove Based and Vision Based approaches. An important face feature point is the nose tip. Since nose is the highest protruding point from the face. Besides that, it is not affected by facial expressions.Another important function of the nose is that it is able to indicate the head pose. Knowledge of the nose location will enable us to align an unknown 3D face with those in a face database. Eye detection is divided into eye position detection and eye contour detection. Existing works in eye detection can be classified into two major categories: traditional image-based passive approaches and the active IR based approaches. The former uses intensity and shape of eyes for detection and the latter works on the assumption that eyes have a reflection under near IR illumination and produce bright/dark pupil effect. The traditional methods can be broadly classified into three categories: template based methods,appearance based methods and feature based methods. The purpose of this paper is to compare various human Gesture recognition systems for interfacing machines directly to human wits without any corporeal media in an ambient environment.
Modeling and Analysis of Time-Varying Graphs
Venue: arXiv cs.NI 2010
Year: 2010

We live in a world increasingly dominated by networks -- communications, social, information, biological etc. A central attribute of many of these networks is that they are dynamic, that is, they exhibit structural changes over time. While the practice of dynamic networks has proliferated, we lag behind in the fundamental, mathematical understanding of network dynamism. Existing research on time-varying graphs ranges from preliminary algorithmic studies (e.g., Ferreira's work on evolving graphs) to analysis of specific properties such as flooding time in dynamic random graphs. A popular model for studying dynamic graphs is a sequence of graphs arranged by increasing snapshots of time. In this paper, we study the fundamental property of reachability in a time-varying graph over time and characterize the latency with respect to two metrics, namely store-or-advance latency and cut-through latency. Instead of expected value analysis, we concentrate on characterizing the exact probability distribution of routing latency along a randomly intermittent path in two popular dynamic random graph models. Using this analysis, we characterize the loss of accuracy (in a probabilistic setting) between multiple temporal graph models, ranging from one that preserves all the temporal ordering information for the purpose of computing temporal graph properties to one that collapses various snapshots into one graph (an operation called smashing), with multiple intermediate variants. We also show how some other traditional graph theoretic properties can be extended to the temporal domain. Finally, we propose algorithms for controlling the progress of a packet in single-copy adaptive routing schemes in various dynamic random graphs.
Dynamic Resource Coordination and Interference Management for Femtocell Networks
Venue: arXiv cs.IT 2010
Year: 2010

Femtocell is emerging as a key technology to secure the coverage and capacity in indoor environments. However the deployment of a new femtocell layer may originate undesired interference to the whole system. This paper investigates spectrum resource coordination and interference management for the femtocell networks. A resource coordination scheme based on broadcasting resource coordination request messages by the femto mobile is proposed to reduce the system interference.
Estimating Probabilities in Recommendation Systems
Venue: arXiv cs.LG 2010
Year: 2010

Recommendation systems are emerging as an important business application with significant economic impact. Currently popular systems include Amazon's book recommendations, Netflix's movie recommendations, and Pandora's music recommendations. In this paper we address the problem of estimating probabilities associated with recommendation system data using non-parametric kernel smoothing. In our estimation we interpret missing items as randomly censored observations and obtain efficient computation schemes using combinatorial properties of generating functions. We demonstrate our approach with several case studies involving real world movie recommendation data. The results are comparable with state-of-the-art techniques while also providing probabilistic preference estimates outside the scope of traditional recommender systems.
A Note on Nonuniform versus Uniform ACC^k Circuits for NE
Venue: arXiv cs.CC 2010
Year: 2010

We note that for each k \in {0,1,2, ...} the following holds: NE has (nonuniform) ACC^k circuits if and only if NE has P^{NE}-uniform ACC^k circuits. And we mention how to get analogous results for other circuit and complexity classes.
Faster Black-Box Algorithms Through Higher Arity Operators
Venue: arXiv cs.NE 2010
Year: 2010

We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary operators the black-box complexity of \leadingones drops from $Θ(n^2)$ for unary operators to $O(n \log n)$. For \onemax, the $Ω(n \log n)$ unary black-box complexity drops to O(n) in the binary case. For $k$-ary operators, $k \leq n$, the \onemax-complexity further decreases to $O(n/\log k)$.
Yet another aperiodic tile set
Venue: arXiv cs.DM 2010
Year: 2010

We present here an elementary construction of an aperiodic tile set. Although there already exist dozens of examples of aperiodic tile sets we believe this construction introduces an approach that is different enough to be interesting and that the whole construction and the proof of aperiodicity are hopefully simpler than most existing techniques.
Robust Distributed Online Prediction
Venue: arXiv cs.LG 2010
Year: 2010

The standard model of online prediction deals with serial processing of inputs by a single processor. However, in large-scale online prediction problems, where inputs arrive at a high rate, an increasingly common necessity is to distribute the computation across several processors. A non-trivial challenge is to design distributed algorithms for online prediction, which maintain good regret guarantees. In \cite{DMB}, we presented the DMB algorithm, which is a generic framework to convert any serial gradient-based online prediction algorithm into a distributed algorithm. Moreover, its regret guarantee is asymptotically optimal for smooth convex loss functions and stochastic inputs. On the flip side, it is fragile to many types of failures that are common in distributed environments. In this companion paper, we present variants of the DMB algorithm, which are resilient to many types of network failures, and tolerant to varying performance of the computing nodes.
Are SNOMED CT Browsers Ready for Institutions? Introducing MySNOM
Venue: arXiv cs.AI 2010
Year: 2010

SNOMED Clinical Terms (SNOMED CT) is one of the most widespread ontologies in the life sciences, with more than 300,000 concepts and relationships, but is distributed with no associated software tools. In this paper we present MySNOM, a web-based SNOMED CT browser. MySNOM allows organizations to browse their own distribution of SNOMED CT under a controlled environment, focuses on navigating using the structure of SNOMED CT, and has diagramming capabilities.
Benchmarking triple stores with biological data
Venue: arXiv cs.DB 2010
Year: 2010

We have compared the performance of five non-commercial triple stores, Virtuoso-open source, Jena SDB, Jena TDB, SWIFT-OWLIM and 4Store. We examined three performance aspects: the query execution time, scalability and run-to-run reproducibility. The queries we chose addressed different ontological or biological topics, and we obtained evidence that individual store performance was quite query specific. We identified three groups of queries displaying similar behavior across the different stores: 1) relatively short response time, 2) moderate response time and 3) relatively long response time. OWLIM proved to be a winner in the first group, 4Store in the second and Virtuoso in the third. Our benchmarking showed Virtuoso to be a very balanced performer - its response time was better than average for all the 24 queries; it showed a very good scalability and a reasonable run-to-run reproducibility.
Process Makna - A Semantic Wiki for Scientific Workflows
Venue: arXiv cs.AI 2010
Year: 2010

Virtual e-Science infrastructures supporting Web-based scientific workflows are an example for knowledge-intensive collaborative and weakly-structured processes where the interaction with the human scientists during process execution plays a central role. In this paper we propose the lightweight dynamic user-friendly interaction with humans during execution of scientific workflows via the low-barrier approach of Semantic Wikis as an intuitive interface for non-technical scientists. Our Process Makna Semantic Wiki system is a novel combination of an business process management system adapted for scientific workflows with a Corporate Semantic Web Wiki user interface supporting knowledge intensive human interaction tasks during scientific workflow execution.
Analysis Of Cancer Omics Data In A Semantic Web Framework
Venue: arXiv cs.AI 2010
Year: 2010

Our work concerns the elucidation of the cancer (epi)genome, transcriptome and proteome to better understand the complex interplay between a cancer cell's molecular state and its response to anti-cancer therapy. To study the problem, we have previously focused on data warehousing technologies and statistical data integration. In this paper, we present recent work on extending our analytical capabilities using Semantic Web technology. A key new component presented here is a SPARQL endpoint to our existing data warehouse. This endpoint allows the merging of observed quantitative data with existing data from semantic knowledge sources such as Gene Ontology (GO). We show how such variegated quantitative and functional data can be integrated and accessed in a universal manner using Semantic Web tools. We also demonstrate how Description Logic (DL) reasoning can be used to infer previously unstated conclusions from existing knowledge bases. As proof of concept, we illustrate the ability of our setup to answer complex queries on resistance of cancer cells to Decitabine, a demethylating agent.
semanticSBML 2.0 - A Collection of Online Services for SBML Models
Venue: arXiv cs.OH 2010
Year: 2010

semanticSBML 2.0 is an online collection of services for the work with biochemical network models in SBML format.
A semantic approach for the requirement-driven discovery of web services in the Life Sciences
Venue: arXiv cs.AI 2010
Year: 2010

Research in the Life Sciences depends on the integration of large, distributed and heterogeneous data sources and web services. The discovery of which of these resources are the most appropriate to solve a given task is a complex research question, since there is a large amount of plausible candidates and there is little, mostly unstructured, metadata to be able to decide among them.We contribute a semi-automatic approach,based on semantic techniques, to assist researchers in the discovery of the most appropriate web services to full a set of given requirements.
Evaluating Modelling Approaches for Medical Image Annotations
Venue: arXiv cs.MM 2010
Year: 2010

Information system designers face many challenges w.r.t. selecting appropriate semantic technologies and deciding on a modelling approach for their system. However, there is no clear methodology yet to evaluate "semantically enriched" information systems. In this paper we present a case study on different modelling approaches for annotating medical images and introduce a conceptual framework that can be used to analyse the fitness of information systems and help designers to spot the strengths and weaknesses of various modelling approaches as well as managing trade-offs between modelling effort and their potential benefits.
Congestion Games with Variable Demands
Venue: arXiv cs.GT 2010
Year: 2010

We initiate the study of congestion games with variable demands where the (variable) demand has to be assigned to exactly one subset of resources. The players' incentives to use higher demands are stimulated by non-decreasing and concave utility functions. The payoff for a player is defined as the difference between the utility of the demand and the associated cost on the used resources. Although this class of non-cooperative games captures many elements of real-world applications, it has not been studied in this generality, to our knowledge, in the past. We study the fundamental problem of the existence of pure Nash equilibria (PNE for short) in congestion games with variable demands. We call a set of cost functions C consistent if every congestion game with variable demands and cost functions in C possesses a PNE. We say that C is FIP consistent if every such game possesses the alpha-Finite Improvement Property for every alpha>0. Our main results are structural characterizations of consistency and FIP consistency for twice continuously differentiable cost functions. Specifically, we show 1. C is consistent if and only if C contains either only affine functions or only homogeneously exponential functions (c(x) = a exp(p x)). 2. C is FIP consistent if and only if C contains only affine functions. Our results provide a complete characterization of consistency of cost functions revealing structural differences to congestion games with fixed demands (weighted congestion games), where in the latter even inhomogeneously exponential functions are FIP consistent. Finally, we study consistency and FIP consistency of cost functions in a slightly different class of games, where every player experiences the same cost on a resource (uniform cost model). We give a characterization of consistency and FIP consistency showing that only homogeneously exponential functions are consistent.