OpenRaiser/Intern-Atlas huggingface dataset:
Relay Selection and Power Allocation in Cooperative Cellular Networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider a system with a single base station communicating with multiple users over orthogonal channels while being assisted by multiple relays. Several recent works have suggested that, in such a scenario, selection, i.e., a single relay helping the source, is the best relaying option in terms of the resulting complexity and overhead. However, in a multiuser setting, optimal relay assignment is a combinatorial problem. In this paper, we formulate a related convex optimization problem that provides an extremely tight upper bound on performance and show that selection is, almost always, inherent in the solution. We also provide a heuristic to find a close-to-optimal relay assignment and power allocation across users supported by a single relay. Simulation results using realistic channel models demonstrate the efficacy of the proposed schemes, but also raise the question as to whether the gains from relaying are worth the additional costs.
To Click or not to Click? The Role of Contextualized and User-Centric Web Snippets
Venue: arXiv cs.IR 2009
Year: 2009

When searching the web, it is often possible that there are too many results available for ambiguous queries. Text snippets, extracted from the retrieved pages, are an indicator of the pages' usefulness to the query intention and can be used to focus the scope of search results. In this paper, we propose a novel method for automatically extracting web page snippets that are highly relevant to the query intention and expressive of the pages' entire content. We show that the usage of semantics, as a basis for focused retrieval, produces high quality text snippet suggestions. The snippets delivered by our method are significantly better in terms of retrieval performance compared to those derived using the pages' statistical content. Furthermore, our study suggests that semantically-driven snippet generation can also be used to augment traditional passage retrieval algorithms based on word overlap or statistical weights, since they typically differ in coverage and produce different results. User clicks on the query relevant snippets can be used to refine the query results and promote the most comprehensive among the relevant documents.
Generating Hierarchically Modular Networks via Link Switching
Venue: arXiv cs.OH 2009
Year: 2009

This paper introduces a method to generate hierarchically modular networks with prescribed node degree list by link switching. Unlike many existing network generating models, our method does not use link probabilities to achieve modularity. Instead, it utilizes a user-specified topology to determine relatedness between pairs of nodes in terms of edge distances and links are switched to increase edge distances. To measure the modular-ness of a network as a whole, a new metric called Q2 is proposed. Comparisons are made between the Q [15] and Q2 measures. We also comment on the effect of our modularization method on other network characteristics such as clustering, hierarchy, average path length, small-worldness, degree correlation and centrality. An application of this method is reported elsewhere [12]. Briefly, the generated networks are used as test problems to explore the effect of modularity and degree distribution on evolutionary search algorithms.
On Hadwiger's Number of a graph with partial information
Venue: arXiv cs.DM 2009
Year: 2009

We investigate the possibility of proving upper bounds on Hadwiger's number of a graph with partial information, mirroring several known upper bounds for the chromatic number. For each such bound we determine whether the corresponding bound for Hadwiger's number holds. Our results suggest that the ``locality'' of an inequality accounts for the existence of such an extension.
Optimistic Simulated Exploration as an Incentive for Real Exploration
Venue: arXiv cs.LG 2009
Year: 2009

Many reinforcement learning exploration techniques are overly optimistic and try to explore every state. Such exploration is impossible in environments with the unlimited number of states. I propose to use simulated exploration with an optimistic model to discover promising paths for real exploration. This reduces the needs for the real exploration.
A Robust Ranging Scheme for OFDMA-Based Networks
Venue: arXiv cs.IT 2009
Year: 2009

Uplink synchronization in orthogonal frequency-division multiple-access (OFDMA) systems is a challenging task. In IEEE 802.16-based networks, users that intend to establish a communication link with the base station must go through a synchronization procedure called Initial Ranging (IR). Existing IR schemes aim at estimating the timing offsets and power levels of ranging subscriber stations (RSSs) without considering possible frequency misalignments between the received uplink signals and the base station local reference. In this work, we present a novel IR scheme for OFDMA systems where carrier frequency offsets, timing errors and power levels are estimated for all RSSs in a decoupled fashion. The proposed frequency estimator is based on a subspace decomposition approach, while timing recovery is accomplished by measuring the phase shift between the users'channel responses over adjacent subcarriers. Computer simulations are employed to assess the effectiveness of the proposed solution and to make comparisons with existing alternatives.
Matrix Completion With Noise
Venue: arXiv cs.IT 2009
Year: 2009

On the heels of compressed sensing, a remarkable new field has very recently emerged. This field addresses a broad range of problems of significant practical interest, namely, the recovery of a data matrix from what appears to be incomplete, and perhaps even corrupted, information. In its simplest form, the problem is to recover a matrix from a small sample of its entries, and comes up in many areas of science and engineering including collaborative filtering, machine learning, control, remote sensing, and computer vision to name a few. This paper surveys the novel literature on matrix completion, which shows that under some suitable conditions, one can recover an unknown low-rank matrix from a nearly minimal set of entries by solving a simple convex optimization problem, namely, nuclear-norm minimization subject to data constraints. Further, this paper introduces novel results showing that matrix completion is provably accurate even when the few observed entries are corrupted with a small amount of noise. A typical result is that one can recover an unknown n x n matrix of low rank r from just about nr log^2 n noisy samples with an error which is proportional to the noise level. We present numerical results which complement our quantitative analysis and show that, in practice, nuclear norm minimization accurately fills in the many missing entries of large low-rank matrices from just a few noisy samples. Some analogies between matrix completion and compressed sensing are discussed throughout.
Smart Antenna Based Broadband communication in Intelligent Transportation system
Venue: arXiv cs.NI 2009
Year: 2009

This paper presents a review for the development of Intelligent Transportation System (ITS) world wide and the use of Smart Antennas in ITS. This review work also discusses the usual problems in ITS and proposes the solution of such problems using smart antennas.
Nation-State Routing: Censorship, Wiretapping, and BGP
Venue: arXiv cs.NI 2009
Year: 2009

The treatment of Internet traffic is increasingly affected by national policies that require the ISPs in a country to adopt common protocols or practices. Examples include government enforced censorship, wiretapping, and protocol deployment mandates for IPv6 and DNSSEC. If an entire nation's worth of ISPs apply common policies to Internet traffic, the global implications could be significant. For instance, how many countries rely on China or Great Britain (known traffic censors) to transit their traffic? These kinds of questions are surprisingly difficult to answer, as they require combining information collected at the prefix, Autonomous System, and country level, and grappling with incomplete knowledge about the AS-level topology and routing policies. In this paper we develop the first framework for country-level routing analysis, which allows us to answer questions about the influence of each country on the flow of international traffic. Our results show that some countries known for their national policies, such as Iran and China, have relatively little effect on interdomain routing, while three countries (the United States, Great Britain, and Germany) are central to international reachability, and their policies thus have huge potential impact.
De-anonymizing Social Networks
Venue: arXiv cs.CR 2009
Year: 2009

Operators of online social networks are increasingly sharing potentially sensitive information about users and their relationships with advertisers, application developers, and data-mining researchers. Privacy is typically protected by anonymization, i.e., removing names, addresses, etc. We present a framework for analyzing privacy and anonymity in social networks and develop a new re-identification algorithm targeting anonymized social-network graphs. To demonstrate its effectiveness on real-world networks, we show that a third of the users who can be verified to have accounts on both Twitter, a popular microblogging service, and Flickr, an online photo-sharing site, can be re-identified in the anonymous Twitter graph with only a 12% error rate. Our de-anonymization algorithm is based purely on the network topology, does not require creation of a large number of dummy "sybil" nodes, is robust to noise and all existing defenses, and works even when the overlap between the target network and the adversary's auxiliary information is small.
Cartesian effect categories are Freyd-categories
Venue: arXiv cs.LO 2009
Year: 2009

Most often, in a categorical semantics for a programming language, the substitution of terms is expressed by composition and finite products. However this does not deal with the order of evaluation of arguments, which may have major consequences when there are side-effects. In this paper Cartesian effect categories are introduced for solving this issue, and they are compared with strong monads, Freyd-categories and Haskell's Arrows. It is proved that a Cartesian effect category is a Freyd-category where the premonoidal structure is provided by a kind of binary product, called the sequential product. The universal property of the sequential product provides Cartesian effect categories with a powerful tool for constructions and proofs. To our knowledge, both effect categories and sequential products are new notions.
A Nice Labelling for Tree-Like Event Structures of Degree 3 (Extended Version)
Venue: arXiv cs.DC 2009
Year: 2009

We address the problem of finding nice labellings for event structures of degree 3. We develop a minimum theory by which we prove that the labelling number of an event structure of degree 3 is bounded by a linear function of the height. The main theorem we present in this paper states that event structures of degree 3 whose causality order is a tree have a nice labelling with 3 colors. Finally, we exemplify how to use this theorem to construct upper bounds for the labelling number of other event structures of degree 3.
Worst case attacks against binary probabilistic traitor tracing codes
Venue: arXiv cs.IT 2009
Year: 2009

An insightful view into the design of traitor tracing codes should necessarily consider the worst case attacks that the colluders can lead. This paper takes an information-theoretic point of view where the worst case attack is defined as the collusion strategy minimizing the achievable rate of the traitor tracing code. Two different decoders are envisaged, the joint decoder and the simple decoder, as recently defined by P. Moulin \cite{Moulin08universal}. Several classes of colluders are defined with increasing power. The worst case attack is derived for each class and each decoder when applied to Tardos' codes and a probabilistic version of the Boneh-Shaw construction. This contextual study gives the real rates achievable by the binary probabilistic traitor tracing codes. Attacks usually considered in literature, such as majority or minority votes, are indeed largely suboptimal. This article also shows the utmost importance of the time-sharing concept in a probabilistic codes.
Fuzzy Chemical Abstract Machines
Venue: arXiv cs.FL 2009
Year: 2009

Fuzzy set theory opens new vistas in computability theory and here I show this by defining a new computational metaphor--the fuzzy chemical metaphor. This metaphor is an extension of the chemical metaphor. In particular, I introduce the idea of a state of a system as a solution of fuzzy molecules, that is molecules that are not just different but rather similar, that react according to a set of fuzzy reaction rules. These notions become precise by introducing fuzzy labeled transition systems. Solutions of fuzzy molecules and fuzzy reaction rules are used to define the general notion of a fuzzy chemical abstract machine, which is a {\em realization} of the fuzzy chemical metaphor. Based on the idea that these machines can be used to describe the operational semantics of process calculi and algebras that include fuzziness as a fundamental property, I present a toy calculus that is a fuzzy equivalent of the $π$-calculus.
Ambient Isotopic Meshing of Implicit Algebraic Surface with Singularities
Venue: arXiv cs.CG 2009
Year: 2009

A complete method is proposed to compute a certified, or ambient isotopic, meshing for an implicit algebraic surface with singularities. By certified, we mean a meshing with correct topology and any given geometric precision. We propose a symbolic-numeric method to compute a certified meshing for the surface inside a box containing singularities and use a modified Plantinga-Vegter marching cube method to compute a certified meshing for the surface inside a box without singularities. Nontrivial examples are given to show the effectiveness of the algorithm. To our knowledge, this is the first method to compute a certified meshing for surfaces with singularities.
String comparison by transposition networks
Venue: arXiv cs.DS 2009
Year: 2009

Computing string or sequence alignments is a classical method of comparing strings and has applications in many areas of computing, such as signal processing and bioinformatics. Semi-local string alignment is a recent generalisation of this method, in which the alignment of a given string and all substrings of another string are computed simultaneously at no additional asymptotic cost. In this paper, we show that there is a close connection between semi-local string alignment and a certain class of traditional comparison networks known as transposition networks. The transposition network approach can be used to represent different string comparison algorithms in a unified form, and in some cases provides generalisations or improvements on existing algorithms. This approach allows us to obtain new algorithms for sparse semi-local string comparison and for comparison of highly similar and highly dissimilar strings, as well as of run-length compressed strings. We conclude that the transposition network method is a very general and flexible way of understanding and improving different string comparison algorithms, as well as their efficient implementation.
Statistical RIP and Semi-Circle Distribution of Incoherent Dictionaries
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we formulate and prove a statistical version of the Candes-Tao restricted isometry property (SRIP for short) which holds in general for any incoherent dictionary which is a disjoint union of orthonormal bases. In addition, we prove that, under appropriate normalization, the eigenvalues of the associated Gram matrix fluctuate around 1 according to the Wigner semicircle distribution. The result is then applied to various dictionaries that arise naturally in the setting of finite harmonic analysis, giving, in particular, a better understanding on a remark of Applebaum-Howard-Searle-Calderbank concerning RIP for the Heisenberg dictionary of chirp like functions.
Using Structural Recursion for Corecursion
Venue: arXiv cs.LO 2009
Year: 2009

We propose a (limited) solution to the problem of constructing stream values defined by recursive equations that do not respect the guardedness condition. The guardedness condition is imposed on definitions of corecursive functions in Coq, AGDA, and other higher-order proof assistants. In this paper, we concentrate in particular on those non-guarded equations where recursive calls appear under functions. We use a correspondence between streams and functions over natural numbers to show that some classes of non-guarded definitions can be modelled through the encoding as structural recursive functions. In practice, this work extends the class of stream values that can be defined in a constructive type theory-based theorem prover with inductive and coinductive types, structural recursion and guarded corecursion
Boolean Logic with Fault Tolerant Coding
Venue: arXiv cs.OH 2009
Year: 2009

Error detectable and error correctable coding in Hamming space was researched to discover possible fault tolerant coding constellations, which can implement Boolean logic with fault tolerant property. Basic logic operators of the Boolean algebra were developed to apply fault tolerant coding in the logic circuits. It was shown that application of three-bit fault tolerant codes have provided the digital system skill of auto-recovery without need for designing additional-fault tolerance mechanisms.
Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
Venue: arXiv cs.CC 2009
Year: 2009

The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation, and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. We also consider online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the data stream model. We compare the performance of these two families of compressors with each other and with the general purpose Lempel-Ziv algorithm. This comparison is made without any a priori assumption on the data's source and considering the asymptotic compression ratio for infinite sequences. We prove that in all cases they are incomparable.
On-Line Tests
Venue: arXiv cs.HC 2009
Year: 2009

This paper presents an interactive implementation which makes the link between a human operator and a system of a administration of a relational databases MySQL. This application conceived as a multimedia presentations is illustrative for the way in which the transfer and the remaking of the information between the human operator, the module of data processing and the database which stores the informations can be solved (with help of the PHP language and the web use).
The Risk-Utility Tradeoff for IP Address Truncation
Venue: arXiv cs.NI 2009
Year: 2009

Network operators are reluctant to share traffic data due to security and privacy concerns. Consequently, there is a lack of publicly available traces for validating and generalizing the latest results in network and security research. Anonymization is a possible solution in this context; however, it is unclear how the sanitization of data preserves characteristics important for traffic analysis. In addition, the privacy-preserving property of state-of-the-art IP address anonymization techniques has come into question by recent attacks that successfully identified a large number of hosts in anonymized traces. In this paper, we examine the tradeoff between data utility for anomaly detection and the risk of host identification for IP address truncation. Specifically, we analyze three weeks of unsampled and non-anonymized network traces from a medium-sized backbone network to assess data utility. The risk of de-anonymizing individual IP addresses is formally evaluated, using a metric based on conditional entropy. Our results indicate that truncation effectively prevents host identification but degrades the utility of data for anomaly detection. However, the degree of degradation depends on the metric used and whether network-internal or external addresses are considered. Entropy metrics are more resistant to truncation than unique counts and the detection quality of anomalies degrades much faster in internal addresses than in external addresses. In particular, the usefulness of internal address counts is lost even for truncation of only 4 bits whereas utility of external address entropy is virtually unchanged even for truncation of 20 bits.
Delving into Transition to the Semantic Web
Venue: arXiv cs.SE 2009
Year: 2009

The semantic technologies pose new challenge for the way in which we built and operate systems. They are tools used to represent significances, associations, theories, separated from data and code. Their goal is to create, to discover, to represent, to organize, to process, to manage, to ratiocinate, to represent, to share and use the significances and knowledge to fulfill the business, personal or social goals.
Token Ring Project
Venue: arXiv cs.NI 2009
Year: 2009

Ring topology is a simple configuration used to connect processes that communicate among themselves. A number of network standards such as token ring, token bus, and FDDI are based on the ring connectivity. This article will develop an implementation of a ring of processes that communicate among themselves via pipe links. The processes are nodes in the ring. Each process reads from its standard input and writes in its standard output. N-1 process redirects the its standard output to a standard input of the process through a pipe. When the ring-structure is designed, the project can be extended to simulate networks or to implement algorithms for mutual exclusion.
ShopList: Programming PDA applications for Windows Mobile using C#
Venue: arXiv cs.OH 2009
Year: 2009

This paper is focused on a C# and Sql Server Mobile 2005 application to keep evidence of a shop list. The purpose of the application is to offer to the user an easier way to manage his shopping options.
Virtual Reality
Venue: arXiv cs.MM 2009
Year: 2009

This paper is focused on the presentation of Virtual Reality principles together with the main implementation methods and techniques. An overview of the main development directions is included.
Random Linear Network Coding for Time-Division Duplexing: Queueing Analysis
Venue: arXiv cs.IT 2009
Year: 2009

We study the performance of random linear network coding for time division duplexing channels with Poisson arrivals. We model the system as a bulk-service queue with variable bulk size. A full characterization for random linear network coding is provided for time division duplexing channels [1] by means of the moment generating function. We present numerical results for the mean number of packets in the queue and consider the effect of the range of allowable bulk sizes. We show that there exists an optimal choice of this range that minimizes the mean number of data packets in the queue.