OpenRaiser/Intern-Atlas huggingface dataset:
Mathematical Model for the Optimal Utilization Percentile in M/M/1 Systems: A Contribution about Knees in Performance Curves
Venue: arXiv cs.PF 2011
Year: 2011

Performance curves of queuing systems can be analyzed by separating them into three regions: the flat region, the knee region, and the exponential region. Practical considerations, usually locate the knee region between 70-90% of the theoretical maximum utilization. However, there is not a clear agreement about where the boundaries between regions are, and where exactly the utilization knee is located. An open debate about knees in performance curves was undertaken at least 20 years ago. This historical debate is mainly divided between those who claim that a knee in the curve is not a well-defined term in mathematics, or it is a subjective and not really meaningful concept, and those who define knees mathematically and consider their relevance and application. In this paper, we present a mathematical model and analysis for identifying the three mentioned regions on performance curves for M/M/1 systems; specifically, we found the knees, or optimal utilization percentiles, at the vertices of the hyperbolas that relate response time as a function of utilization. Using these results, we argue that an adaptive and optimal queuing system could be deployed by keeping load and throughput within the knee region.
Network Selection Using TOPSIS in Vertical Handover Decision Schemes for Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

"Handover" is one of the techniques used to achieve the service continuity in Fourth generation wireless networks (FGWNs). Seamless continuity is the main goal in fourth generation Wireless networks (FGWNs), when a mobile terminal (MT) is in overlapping area for service continuity Handover mechanism are mainly used While moving in the heterogeneous wireless networks continual connection is the main challenge. Vertical handover is used as a technique to minimize the processing delay in heterogeneous wireless networks this paper, Vertical handover decision schemes are compared and Technique of order preference by similarity to ideal solution (TOPSIS) in a distributed manner. TOPSIS is used to choose the best network from the available Visitor networks (VTs) for the continuous connection by the mobile terminal. In our work we mainly concentrated to the handover decision Phase and to reduce the processing delay in the period of handover
Inferring Internet AS Relationships Based on BGP Routing Policies
Venue: arXiv cs.NI 2011
Year: 2011

The type of business relationships between the Internet autonomous systems (AS) determines the BGP inter-domain routing. Previous works on inferring AS relationships relied on the connectivity information between ASes. In this paper we infer AS relationships by analysing the routing polices of ASes encoded in the BGP attributes Communities and the Locpref. We accumulate BGP data from RouteViews, RIPE RIS and the public Route Servers in August 2010 and February 2011. Based on the routing policies extracted from data of the two BGP attributes, we obtain AS relationships for 39% links in our data, which include all links among the Tier-1 ASes and most links between Tier-1 and Tier-2 ASes. We also reveal a number of special AS relationships, namely the hybrid relationship, the partial-transit relationship, the indirect peering relationship and the backup links. These special relationships are relevant to a better understanding of the Internet routing. Our work provides a profound methodological progress for inferring the AS relationships.
Degrees of Freedom Region of the Gaussian MIMO Broadcast Channel with Common and Private Messages
Venue: arXiv cs.IT 2011
Year: 2011

We consider the Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and private messages. We obtain the degrees of freedom (DoF) region of this channel. We first show that a parallel Gaussian broadcast channel with unmatched sub-channels can be constructed from any given Gaussian MIMO broadcast channel by using the generalized singular value decomposition (GSVD) and a relaxation on the power constraint for the channel input, in a way that the capacity region of the constructed parallel channel provides an outer bound for the capacity region of the original channel. The capacity region of the parallel Gaussian broadcast channel with unmatched sub-channels is known, using which we obtain an explicit outer bound for the DoF region of the Gaussian MIMO broadcast channel. We finally show that this outer bound for the DoF region can be attained both by the achievable scheme that uses a classical Gaussian coding for the common message and dirty-paper coding (DPC) for the private messages, as well as by a variation of the zero-forcing (ZF) scheme.
Obstructions for linear rankwidth at most 1
Venue: arXiv cs.DM 2011
Year: 2011

We provide a characterization of graphs of linear rankwidth at most 1 by minimal excluded vertex-minors.
SparseAssembler: de novo Assembly with the Sparse de Bruijn Graph
Venue: arXiv cs.DS 2011
Year: 2011

de Bruijn graph-based algorithms are one of the two most widely used approaches for de novo genome assembly. A major limitation of this approach is the large computational memory space requirement to construct the de Bruijn graph, which scales with k-mer length and total diversity (N) of unique k-mers in the genome expressed in base pairs or roughly (2k+8)N bits. This limitation is particularly important with large-scale genome analysis and for sequencing centers that simultaneously process multiple genomes. We present a sparse de Bruijn graph structure, based on which we developed SparseAssembler that greatly reduces memory space requirements. The structure also allows us to introduce a novel method for the removal of substitution errors introduced during sequencing. The sparse de Bruijn graph structure skips g intermediate k-mers, therefore reducing the theoretical memory space requirement to ~(2k/g+8)N. We have found that a practical value of g=16 consumes approximately 10% of the memory required by standard de Bruijn graph-based algorithms but yields comparable results. A high error rate could potentially derail the SparseAssembler. Therefore, we developed a sparse de Bruijn graph-based denoising algorithm that can remove more than 99% of substitution errors from datasets with a \leq 2% error rate. Given that substitution error rates for the current generation of sequencers is lower than 1%, our denoising procedure is sufficiently effective to safeguard the performance of our algorithm. Finally, we also introduce a novel Dijkstra-like breadth-first search algorithm for the sparse de Bruijn graph structure to circumvent residual errors and resolve polymorphisms.
Learning Equilibria with Partial Information in Decentralized Wireless Networks
Venue: arXiv cs.LG 2011
Year: 2011

In this article, a survey of several important equilibrium concepts for decentralized networks is presented. The term decentralized is used here to refer to scenarios where decisions (e.g., choosing a power allocation policy) are taken autonomously by devices interacting with each other (e.g., through mutual interference). The iterative long-term interaction is characterized by stable points of the wireless network called equilibria. The interest in these equilibria stems from the relevance of network stability and the fact that they can be achieved by letting radio devices to repeatedly interact over time. To achieve these equilibria, several learning techniques, namely, the best response dynamics, fictitious play, smoothed fictitious play, reinforcement learning algorithms, and regret matching, are discussed in terms of information requirements and convergence properties. Most of the notions introduced here, for both equilibria and learning schemes, are illustrated by a simple case study, namely, an interference channel with two transmitter-receiver pairs.
Program Equivalence in Linear Contexts
Venue: arXiv cs.PL 2011
Year: 2011

Program equivalence in linear contexts, where programs are used or executed exactly once, is an important issue in programming languages. However, existing techniques like those based on bisimulations and logical relations only target at contextual equivalence in the usual (non-linear) functional languages, and fail in capturing non-trivial equivalent programs in linear contexts, particularly when non-determinism is present. We propose the notion of linear contextual equivalence to formally characterize such program equivalence, as well as a novel and general approach to studying it in higher-order languages, based on labeled transition systems specifically designed for functional languages. We show that linear contextual equivalence indeed coincides with trace equivalence - it is sound and complete. We illustrate our technique in both deterministic (a linear version of PCF) and non-deterministic (linear PCF in Moggi's framework) functional languages.
The rates of convergence for generalized entropy of the normalized sums of IID random variables
Venue: arXiv cs.IT 2011
Year: 2011

We consider the generalized differential entropy of normalized sums of independent and identically distributed (IID) continuous random variables. We prove that the Rényi entropy and Tsallis entropy of order $α (α>0)$ of the normalized sum of IID continuous random variables with bounded moments are convergent to the corresponding Rényi entropy and Tsallis entropy of the Gaussian limit, and obtain sharp rates of convergence.
Large margin filtering for signal sequence labeling
Venue: arXiv cs.LG 2011
Year: 2011

Signal Sequence Labeling consists in predicting a sequence of labels given an observed sequence of samples. A naive way is to filter the signal in order to reduce the noise and to apply a classification algorithm on the filtered samples. We propose in this paper to jointly learn the filter with the classifier leading to a large margin filtering for classification. This method allows to learn the optimal cutoff frequency and phase of the filter that may be different from zero. Two methods are proposed and tested on a toy dataset and on a real life BCI dataset from BCI Competition III.
Handling uncertainties in SVM classification
Venue: arXiv cs.LG 2011
Year: 2011

This paper addresses the pattern classification problem arising when available target data include some uncertainty information. Target data considered here is either qualitative (a class label) or quantitative (an estimation of the posterior probability). Our main contribution is a SVM inspired formulation of this problem allowing to take into account class label through a hinge loss as well as probability estimates using epsilon-insensitive cost function together with a minimum norm (maximum margin) objective. This formulation shows a dual form leading to a quadratic problem and allows the use of a representer theorem and associated kernel. The solution provided can be used for both decision and posterior probability estimation. Based on empirical evidence our method outperforms regular SVM in terms of probability predictions and classification performances.
Constraint solving in non-permutative nominal abstract syntax
Venue: arXiv cs.PL 2011
Year: 2011

Nominal abstract syntax is a popular first-order technique for encoding, and reasoning about, abstract syntax involving binders. Many of its applications involve constraint solving. The most commonly used constraint solving algorithm over nominal abstract syntax is the Urban-Pitts-Gabbay nominal unification algorithm, which is well-behaved, has a well-developed theory and is applicable in many cases. However, certain problems require a constraint solver which respects the equivariance property of nominal logic, such as Cheney's equivariant unification algorithm. This is more powerful but is more complicated and computationally hard. In this paper we present a novel algorithm for solving constraints over a simple variant of nominal abstract syntax which we call non-permutative. This constraint problem has similar complexity to equivariant unification but without many of the additional complications of the equivariant unification term language. We prove our algorithm correct, paying particular attention to issues of termination, and present an explicit translation of name-name equivariant unification problems into non-permutative constraints.
Conditional and Unique Coloring of Graphs
Venue: arXiv cs.DM 2011
Year: 2011

For integers $k, r > 0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to at least $\min\{r, d(v)\}$ differently colored vertices. Given $r$, the smallest integer $k$ for which $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number $χ_r(G)$ of $G$. We give results (exact values or bounds for $χ_r(G)$, depending on $r$) related to the conditional coloring of some graphs. We introduce \emph{unique conditional colorability} and give some related results. (Keywords. cartesian product of graphs; conditional chromatic number; gear graph; join of graphs.)
On the Locality of Codeword Symbols
Venue: arXiv cs.IT 2011
Year: 2011

Consider a linear [n,k,d]_q code C. We say that that i-th coordinate of C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst-case distance and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality for parity checks and the ability to correct erasures beyond the minimum distance.
Analog Network Coding in the Generalized High-SNR Regime
Venue: arXiv cs.IT 2011
Year: 2011

In a recent paper [4], Marić et al. analyzed the performance of the analog network coding (ANC) in a layered relay network for the high-SNR regime. They have proved that under the ANC scheme, if each relay transmits the received signals at the upper bound of the power constraint, the transmission rate will approach the network capacity. In this paper, we consider a more general scenario defined as the generalized high-SNR regime, where the relays at layer $l$ in a layered relay network with $L$ layers do not satisfy the high-SNR conditions, and then determine an ANC relay scheme in such network. By relating the received SNR at the nodes with the propagated noise, we derive the rate achievable by the ANC scheme proposed in this paper. The result shows that the achievable ANC rate approaches the upper bound of the ANC capacity as the received powers at relays in high SNR increase. A comparison of the two ANC schemes implies that the scheme proposed in [4] may not always be the optimal one in the generalized high-SNR regime. The result also demonstrates that the upper and lower bounds of the ANC rate coincide in the limit as the number of relays at layer L-1 dissatisfying the high-SNR conditions tends to infinity, yielding an asymptotic capacity result.
Total Variation Minimization Based Compressive Wideband Spectrum Sensing for Cognitive Radios
Venue: arXiv cs.IT 2011
Year: 2011

Wideband spectrum sensing is a critical component of a functioning cognitive radio system. Its major challenge is the too high sampling rate requirement. Compressive sensing (CS) promises to be able to deal with it. Nearly all the current CS based compressive wideband spectrum sensing methods exploit only the frequency sparsity to perform. Motivated by the achievement of a fast and robust detection of the wideband spectrum change, total variation mnimization is incorporated to exploit the temporal and frequency structure information to enhance the sparse level. As a sparser vector is obtained, the spectrum sensing period would be shorten and sensing accuracy would be enhanced. Both theoretical evaluation and numerical experiments can demonstrate the performance improvement.
Embedding and Automating Conditional Logics in Classical Higher-Order Logic
Venue: arXiv cs.AI 2011
Year: 2011

A sound and complete embedding of conditional logics into classical higher-order logic is presented. This embedding enables the application of off-the-shelf higher-order automated theorem provers and model finders for reasoning within and about conditional logics.
Composition with Target Constraints
Venue: arXiv cs.DB 2011
Year: 2011

It is known that the composition of schema mappings, each specified by source-to-target tgds (st-tgds), can be specified by a second-order tgd (SO tgd). We consider the question of what happens when target constraints are allowed. Specifically, we consider the question of specifying the composition of standard schema mappings (those specified by st-tgds, target egds, and a weakly acyclic set of target tgds). We show that SO tgds, even with the assistance of arbitrary source constraints and target constraints, cannot specify in general the composition of two standard schema mappings. Therefore, we introduce source-to-target second-order dependencies (st-SO dependencies), which are similar to SO tgds, but allow equations in the conclusion. We show that st-SO dependencies (along with target egds and target tgds) are sufficient to express the composition of every finite sequence of standard schema mappings, and further, every st-SO dependency specifies such a composition. In addition to this expressive power, we show that st-SO dependencies enjoy other desirable properties. In particular, they have a polynomial-time chase that generates a universal solution. This universal solution can be used to find the certain answers to unions of conjunctive queries in polynomial time. It is easy to show that the composition of an arbitrary number of standard schema mappings is equivalent to the composition of only two standard schema mappings. We show that surprisingly, the analogous result holds also for schema mappings specified by just st-tgds (no target constraints). This is proven by showing that every SO tgd is equivalent to an unnested SO tgd (one where there is no nesting of function symbols). Similarly, we prove unnesting results for st-SO dependencies, with the same types of consequences.
Rewriting Ontological Queries into Small Nonrecursive Datalog Programs
Venue: arXiv cs.AI 2011
Year: 2011

We consider the setting of ontological database access, where an Abox is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a Tbox T formulated in DL-Lite or Linear Datalog+/-. It is well-known that (T,q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog? or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of T and q. This gives rise to the interesting question of whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate (T,q) into a polynomially sized equivalent nonrecursive Datalog program P.
A Packet Dropping Mechanism for Efficient Operation of M/M/1 Queues with Selfish Users
Venue: arXiv cs.GT 2011
Year: 2011

We consider a fundamental game theoretic problem concerning selfish users contributing packets to an M/M/1 queue. In this game, each user controls its own input rate so as to optimize a desired tradeoff between throughput and delay. We first show that the original game has an inefficient Nash Equilibrium (NE), with a Price of Anarchy (PoA) that scales linearly or worse in the number of users. In order to improve the outcome efficiency, we propose an easily implementable mechanism design whereby the server randomly drops packets with a probability that is a function of the total arrival rate. We show that this results in a modified M/M/1 queueing game that is an ordinal potential game with at least one NE. In particular, for a linear packet dropping function, which is similar to the Random Early Detection (RED) algorithm used in Internet Congestion Control, we prove that there is a unique NE. We also show that the simple best response dynamic converges to this unique equilibrium. Finally, for this scheme, we prove that the social welfare (expressed either as the summation of utilities of all players, or as the summation of the logarithm of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point, i.e. the PoA can be made arbitrarily close to 1. We also study the impact of arrival rate estimation error on the PoA through simulations.
Coincidences and the encounter problem: A formal account
Venue: arXiv cs.AI 2011
Year: 2011

Individuals have an intuitive perception of what makes a good coincidence. Though the sensitivity to coincidences has often been presented as resulting from an erroneous assessment of probability, it appears to be a genuine competence, based on non-trivial computations. The model presented here suggests that coincidences occur when subjects perceive complexity drops. Co-occurring events are, together, simpler than if considered separately. This model leads to a possible redefinition of subjective probability.
Building a refinement checker for Z
Venue: arXiv cs.SE 2011
Year: 2011

In previous work we have described how refinements can be checked using a temporal logic based model-checker, and how we have built a model-checker for Z by providing a translation of Z into the SAL input language. In this paper we draw these two strands of work together and discuss how we have implemented refinement checking in our Z2SAL toolset. The net effect of this work is that the SAL toolset can be used to check refinements between Z specifications supplied as input files written in the LaTeX mark-up. Two examples are used to illustrate the approach and compare it with a manual translation and refinement check.