OpenRaiser/Intern-Atlas huggingface dataset:
On the Frequency-Selective Scheduling Gain in SDMA-OFDMA Systems
Venue: arXiv cs.NI 2012
Year: 2012

Orthogonal Frequency Division Multiple Access (OFDMA) is a multi-user version of the Orthogonal Frequency Division Multiplexing (OFDM) transmission technique, which divides a wideband channel into a number of orthogonal narrowband subchannels, called subcarriers. An OFDMA system takes advantage of both frequency diversity (FD) gain and frequency-selective scheduling (FSS) gain. A FD gain is achieved by allocating a user the subcarriers distributed over the entire frequency band whereas a FSS gain is achieved by allocating a user adjacent subcarriers located within a subband of a small bandwidth having the most favorable channel conditions among other subbands in the entire frequency band. Multi-User Multiple Input Multiple Output (MU-MIMO) is a promising technology to increase spectral efficiency. A well-known MU-MIMO mode is Space-Division Multiple Access (SDMA) which can be used in the downlink direction to allow a group of spatially separable users to share the same time/frequency resources. In this paper, we study the gain from FSS in SDMA-OFDMA systems using the example of WiMAX. Therefore, a complete SDMA-OFDMA MAC scheduling solution supporting both FD and FSS is proposed. The proposed solution is analyzed in a typical urban macro-cell scenario by means of system-level packet-based simulations, with detailed MAC and physical layer abstractions. By explicitly simulating the MAC layer overhead (MAP) which is required to signal every packed data burst in the OFDMA frame we can present the overall performance to be expected at the MAC layer. Our results show that in general the gain from FSS when applying SDMA is low. However, under specific conditions, small number of BS antennas or large channel bandwidth, a significant gain can be achieved from FSS.
On X-Channels with Feedback and Delayed CSI
Venue: arXiv cs.IT 2012
Year: 2012

The sum degrees of freedom (DoF) of the two-user MIMO X-channel is characterized in the presence of output feedback and delayed channel state information (CSI). The number of antennas at each transmitters is assumed to be M and the number of antennas at each of the receivers is assumed to be N. It is shown that the sum DoF of the two-user MIMO X-channel is the same as the sum DoF of a two-user MIMO broadcast channel with 2M transmit antennas, and N antennas at each receiver. Hence, for this symmetric antenna configuration, there is no performance loss in the sum degrees of freedom due to the distributed nature of the transmitters. This result highlights the usefulness of feedback and delayed CSI for the MIMO X-channel. The K-user X-channel with single antenna at each transmitter and each receiver is also studied. In this network, each transmitter has a message intended for each receiver. For this network, it is shown that the sum DoF with partial output feedback alone is at least 2K/(K+1). This lower bound is strictly better than the best lower bound known for the case of delayed CSI assumption for all values of K.
The black-and-white coloring problem on permutation graphs
Venue: arXiv cs.DS 2012
Year: 2012

Given a graph G and integers b and w. The black-and-white coloring problem asks if there exist disjoint sets of vertices B and W with |B|=b and |W|=w such that no vertex in B is adjacent to any vertex in W. In this paper we show that the problem is polynomial when restricted to permutation graphs.
No input symbol should occur more frequently than 1-1/e
Venue: arXiv cs.IT 2012
Year: 2012

Consider any discrete memoryless channel (DMC) with arbitrarily but finite input and output alphabets X, Y respectively. Then, for any capacity achieving input distribution all symbols occur less frequently than 1-1/e$. That is, \[ \max\limits_{x \in \mathcal{X}} P^*(x) < 1-\frac{1}{e} \] \noindent where $P^*(x)$ is a capacity achieving input distribution. Also, we provide sufficient conditions for which a discrete distribution can be a capacity achieving input distribution for some DMC channel. Lastly, we show that there is no similar restriction on the capacity achieving output distribution.
Broadcast Channels with Confidential Messages by Randomness Constrained Stochastic Encoder
Venue: arXiv cs.IT 2012
Year: 2012

In coding schemes for the wire-tap channel or the broadcast channels with confidential messages, it is well known that the sender needs to use a stochastic encoding to avoid the information about the transmitted confidential message to be leaked to an eavesdropper. In this paper, it is investigated that the trade-off between the rate of the random number to realize the stochastic encoding and the rates of the common, private, and confidential messages. For the direct theorem, the superposition coding scheme for the wire-tap channel recently proposed by Chia and El Gamal is employed, and its strong security is proved. The matching converse theorem is also established. Our result clarifies that a combination of the ordinary stochastic encoding and the channel prefixing by the channel simulation is suboptimal.
Ontologies for the Integration of Air Quality Models and 3D City Models
Venue: arXiv cs.AI 2012
Year: 2012

The holistic approach to sustainable urban planning implies using different models in an integrated way that is capable of simulating the urban system. As the interconnection of such models is not a trivial task, one of the key elements that may be applied is the description of the urban geometric properties in an "interoperable" way. Focusing on air quality as one of the most pronounced urban problems, the geometric aspects of a city may be described by objects such as those defined in CityGML, so that an appropriate air quality model can be applied for estimating the quality of the urban air on the basis of atmospheric flow and chemistry equations. In this paper we first present theoretical background and motivations for the interconnection of 3D city models and other models related to sustainable development and urban planning. Then we present a practical experiment based on the interconnection of CityGML with an air quality model. Our approach is based on the creation of an ontology of air quality models and on the extension of an ontology of urban planning process (OUPP) that acts as an ontology mediator.
The Filter-Placement Problem and its Application to Minimizing Information Multiplicity
Venue: arXiv cs.DB 2012
Year: 2012

In many information networks, data items -- such as updates in social networks, news flowing through interconnected RSS feeds and blogs, measurements in sensor networks, route updates in ad-hoc networks -- propagate in an uncoordinated manner: nodes often relay information they receive to neighbors, independent of whether or not these neighbors received the same information from other sources. This uncoordinated data dissemination may result in significant, yet unnecessary communication and processing overheads, ultimately reducing the utility of information networks. To alleviate the negative impacts of this information multiplicity phenomenon, we propose that a subset of nodes (selected at key positions in the network) carry out additional information filtering functionality. Thus, nodes are responsible for the removal (or significant reduction) of the redundant data items relayed through them. We refer to such nodes as filters. We formally define the Filter Placement problem as a combinatorial optimization problem, and study its computational complexity for different types of graphs. We also present polynomial-time approximation algorithms and scalable heuristics for the problem. Our experimental results, which we obtained through extensive simulations on synthetic and real-world information flow networks, suggest that in many settings a relatively small number of filters are fairly effective in removing a large fraction of redundant information.
Fast and Exact Top-k Search for Random Walk with Restart
Venue: arXiv cs.DB 2012
Year: 2012

Graphs are fundamental data structures and have been employed for centuries to model real-world systems and phenomena. Random walk with restart (RWR) provides a good proximity score between two nodes in a graph, and it has been successfully used in many applications such as automatic image captioning, recommender systems, and link prediction. The goal of this work is to find nodes that have top-k highest proximities for a given node. Previous approaches to this problem find nodes efficiently at the expense of exactness. The main motivation of this paper is to answer, in the affirmative, the question, `Is it possible to improve the search time without sacrificing the exactness?'. Our solution, {it K-dash}, is based on two ideas: (1) It computes the proximity of a selected node efficiently by sparse matrices, and (2) It skips unnecessary proximity computations when searching for the top-k nodes. Theoretical analyses show that K-dash guarantees result exactness. We perform comprehensive experiments to verify the efficiency of K-dash. The results show that K-dash can find top-k nodes significantly faster than the previous approaches while it guarantees exactness.
Aggregation in Probabilistic Databases via Knowledge Compilation
Venue: arXiv cs.DB 2012
Year: 2012

This paper presents a query evaluation technique for positive relational algebra queries with aggregates on a representation system for probabilistic data based on the algebraic structures of semiring and semimodule. The core of our evaluation technique is a procedure that compiles semimodule and semiring expressions into so-called decomposition trees, for which the computation of the probability distribution can be done in time linear in the product of the sizes of the probability distributions represented by its nodes. We give syntactic characterisations of tractable queries with aggregates by exploiting the connection between query tractability and polynomial-time decomposition trees. A prototype of the technique is incorporated in the probabilistic database engine SPROUT. We report on performance experiments with custom datasets and TPC-H data.
Empowerment for Continuous Agent-Environment Systems
Venue: arXiv cs.AI 2012
Year: 2012

This paper develops generalizations of empowerment to continuous states. Empowerment is a recently introduced information-theoretic quantity motivated by hypotheses about the efficiency of the sensorimotor loop in biological organisms, but also from considerations stemming from curiosity-driven learning. Empowemerment measures, for agent-environment systems with stochastic transitions, how much influence an agent has on its environment, but only that influence that can be sensed by the agent sensors. It is an information-theoretic generalization of joint controllability (influence on environment) and observability (measurement by sensors) of the environment by the agent, both controllability and observability being usually defined in control theory as the dimensionality of the control/observation spaces. Earlier work has shown that empowerment has various interesting and relevant properties, e.g., it allows us to identify salient states using only the dynamics, and it can act as intrinsic reward without requiring an external reward. However, in this previous work empowerment was limited to the case of small-scale and discrete domains and furthermore state transition probabilities were assumed to be known. The goal of this paper is to extend empowerment to the significantly more important and relevant case of continuous vector-valued state spaces and initially unknown state transition probabilities. The continuous state space is addressed by Monte-Carlo approximation; the unknown transitions are addressed by model learning and prediction for which we apply Gaussian processes regression with iterated forecasting. In a number of well-known continuous control tasks we examine the dynamics induced by empowerment and include an application to exploration and online model learning.
A General Approach for Securely Querying and Updating XML Data
Venue: arXiv cs.CR 2012
Year: 2012

Over the past years several works have proposed access control models for XML data where only read-access rights over non-recursive DTDs are considered. A few amount of works have studied the access rights for updates. In this paper, we present a general model for specifying access control on XML data in the presence of update operations of W3C XQuery Update Facility. Our approach for enforcing such updates specifications is based on the notion of query rewriting where each update operation defined over arbitrary DTD (recursive or not) is rewritten to a safe one in order to be evaluated only over XML data which can be updated by the user. We investigate in the second part of this report the secure of XML updating in the presence of read-access rights specified by a security views. For an XML document, a security view represents for each class of users all and only the parts of the document these users are able to see. We show that an update operation defined over a security view can cause disclosure of sensitive data hidden by this view if it is not thoroughly rewritten with respect to both read and update access rights. Finally, we propose a security view based approach for securely updating XML in order to preserve the confidentiality and integrity of XML data.
Inference and Plausible Reasoning in a Natural Language Understanding System Based on Object-Oriented Semantics
Venue: arXiv cs.CL 2012
Year: 2012

Algorithms of inference in a computer system oriented to input and semantic processing of text information are presented. Such inference is necessary for logical questions when the direct comparison of objects from a question and database can not give a result. The following classes of problems are considered: a check of hypotheses for persons and non-typical actions, the determination of persons and circumstances for non-typical actions, planning actions, the determination of event cause and state of persons. To form an answer both deduction and plausible reasoning are used. As a knowledge domain under consideration is social behavior of persons, plausible reasoning is based on laws of social psychology. Proposed algorithms of inference and plausible reasoning can be realized in computer systems closely connected with text processing (criminology, operation of business, medicine, document systems).
Opportunistic Scheduling in Heterogeneous Networks: Distributed Algorithms and System Capacity
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we design and analyze novel distributed scheduling algorithms for multi-user MIMO systems. In particular, we consider algorithms which do not require sending channel state information to a central processing unit, nor do they require communication between the users themselves, yet, we prove their performance closely approximates that of a centrally-controlled system, which is able to schedule the strongest user in each time-slot. Our analysis is based on a novel application of the Point-Process approximation. This novel technique allows us to examine non-homogeneous cases, such as non-identically distributed users, or handling various QoS considerations, and give exact expressions for the capacity of the system under these schemes, solving analytically problems which to date had been open. Possible application include, but are not limited to, modern 4G networks such as 3GPP LTE, or random access protocols.
Increasing Randomness Using Permutations on Blocks
Venue: arXiv cs.CR 2012
Year: 2012

This paper investigates the effect of permutations on blocks of a prime reciprocal sequence on its randomness. A relationship between the number of permutations used and the improvement of performance is presented. This can be used as a method for increasing the cryptographic strength of pseudorandom sequences.
Multi-hop Moving Relays for IMT-Advanced and Beyond
Venue: arXiv cs.NI 2012
Year: 2012

Relaying is a promising enhancement to current radio technologies, which has been considered in IMT-Advanced candidate technologies such as 3GPP LTE-Advanced and IEEE 802.16m. Relay enhanced networks are expected to fulfill the demanding coverage and capacity requirements in a cost efficient way. Among various relaying architectures multi-hop moving relays can provide additional capacity for the cases when fixed relays are inaccessible or not able to provide adequate solutions in terms of cost. In this paper, an overview of multi-hop moving relays along with some of the envisioned deployment scenarios is presented. Furthermore, different types of multi-hop moving relays are discussed and the challenges are addressed.
The watershed concept and its use in segmentation : a brief history
Venue: arXiv cs.CV 2012
Year: 2012

The watershed is one of the most used tools in image segmentation. We present how its concept is born and developed over time. Its implementation as an algorithm or a hardwired device evolved together with the technology which allowed it. We present also how it is used in practice, first together with markers, and later introduced in a multiscale framework, in order to produce not a unique partition but a complete hierarchy.
Weak Forms of Monotonicity and Coordination-Freeness
Venue: arXiv cs.DB 2012
Year: 2012

Our earlier work titled: "Win-move is Coordination-Free (Sometimes)" has shown that the classes of queries that can be distributedly computed in a coordination-free manner form a strict hierarchy depending on the assumptions of the model for distributed computations. In this paper, we further characterize these classes by revealing a tight relationship between them and novel weakened forms of monotonicity.
Error Performance of Multidimensional Lattice Constellations-Part I: A Parallelotope Geometry Based Approach for the AWGN Channel
Venue: arXiv cs.IT 2012
Year: 2012

Multidimensional lattice constellations which present signal space diversity (SSD) have been extensively studied for single-antenna transmission over fading channels, with focus on their optimal design for achieving high diversity gain. In this two-part series of papers we present a novel combinatorial geometrical approach based on parallelotope geometry, for the performance evaluation of multidimensional finite lattice constellations with arbitrary structure, dimension and rank. In Part I, we present an analytical expression for the exact symbol error probability (SEP) of multidimensional signal sets, and two novel closed-form bounds, named Multiple Sphere Lower Bound (MLSB) and Multiple Sphere Upper Bound (MSUB). Part II extends the analysis to the transmission over fading channels, where multidimensional signal sets are commonly used to combat fading degradation. Numerical and simulation results show that the proposed geometrical approach leads to accurate and tight expressions, which can be efficiently used for the performance evaluation and the design of multidimensional lattice constellations, both in Additive White Gaussian Noise (AWGN) and fading channels.
Error Performance of Multidimensional Lattice Constellations-Part II: Evaluation over Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

This is the second part of a two-part series of papers, where the error performance of multidimensional lattice constellations with signal space diversity (SSD) is investigated. In Part I, following a novel combinatorial geometrical approach which is based on parallelotope geometry, we have presented an exact analytical expression and two closed-form bounds for the symbol error probability (SEP) in Additive White Gaussian Noise (AWGN). In the present Part II, we extend the analysis and present a novel analytical expression for the Frame Error Probability (FEP) of multidimensional lattice constellations over Nakagami-m fading channels. As the FEP of infinite lattice constellations is lower bounded by the Sphere Lower Bound (SLB), we propose the Sphere Upper Bound (SUB) for block fading channels. Furthermore, two novel bounds for the FEP of multidimensional lattice constellations over block fading channels, named Multiple Sphere Lower Bound (MSLB) and Multiple Sphere Upper Bound (MSUB), are presented. The expressions for the SLB and SUB are given in closed form, while the corresponding ones for MSLB and MSUB are given in closed form for unitary block length. Numerical and simulation results illustrate the tightness of the proposed bounds and demonstrate that they can be efficiently used to set the performance limits on the FEP of lattice constellations of arbitrary structure, dimension and rank.
On the admissible families of components of Hamming codes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we describe the properties of the $i$-components of Hamming codes. We suggest constructions of the admissible families of components of Hamming codes. It is shown that every $q$-ary code of length $m$ and minimum distance 5 (for $q = 3$ the minimum distance is 3) can be embedded in a $q$-ary 1-perfect code of length $n = (q^{m}-1)/(q-1)$. It is also shown that every binary code of length $m + k$ and minimum distance $3k + 3$ can be embedded in a binary 1-perfect code of length $n = 2^{m}-1$.
Bounds and Invariant Sets for a Class of Switching Systems with Delayed-state-dependent Perturbations
Venue: arXiv cs.SY 2012
Year: 2012

We present a novel method to compute componentwise transient bounds, ultimate bounds, and invariant regions for a class of switching continuous-time linear systems with perturbation bounds that may depend nonlinearly on a delayed state. The main advantage of the method is its componentwise nature, i.e. the fact that it allows each component of the perturbation vector to have an independent bound and that the bounds and sets obtained are also given componentwise. This componentwise method does not employ a norm for bounding either the perturbation or state vectors, avoids the need for scaling the different state vector components in order to obtain useful results, and may also reduce conservativeness in some cases. We give conditions for the derived bounds to be of local or semi-global nature. In addition, we deal with the case of perturbation bounds whose dependence on a delayed state is of affine form as a particular case of nonlinear dependence for which the bounds derived are shown to be globally valid. A sufficient condition for practical stability is also provided. The present paper builds upon and extends to switching systems with delayed-state-dependent perturbations previous results by the authors. In this sense, the contribution is three-fold: the derivation of the aforementioned extension; the elucidation of the precise relationship between the class of switching linear systems to which the proposed method can be applied and those that admit a common quadratic Lyapunov function (a question that was left open in our previous work); and the derivation of a technique to compute a common quadratic Lyapunov function for switching linear systems with perturbations bounded componentwise by affine functions of the absolute value of the state vector components.