OpenRaiser/Intern-Atlas huggingface dataset:
Power minimization for OFDM Transmission with Subcarrier-pair based Opportunistic DF Relaying
Venue: arXiv cs.IT 2013
Year: 2013

This paper develops a sum-power minimized resource allocation (RA) algorithm subject to a sum-rate constraint for cooperative orthogonal frequency division modulation (OFDM) transmission with subcarrier-pair based opportunistic decode-and-forward (DF) relaying. The improved DF protocol first proposed in [1] is used with optimized subcarrier pairing. Instrumental to the RA algorithm design is appropriate definition of variables to represent source/relay power allocation, subcarrier pairing and transmission-mode selection elegantly, so that after continuous relaxation, the dual method and the Hungarian algorithm can be used to find an (at least approximately) optimum RA with polynomial complexity. Moreover, the bisection method is used to speed up the search of the optimum Lagrange multiplier for the dual method. Numerical results are shown to illustrate the power-reduction benefit of the improved DF protocol with optimized subcarrier pairing.
Characters and patterns of communities in networks
Venue: arXiv cs.SI 2013
Year: 2013

In this paper, we propose some new notions to characterize and analyze the communities. The new notions are general characters of the communities or local structures of networks. At first, we introduce the notions of internal dominating set and external dominating set of a community. We show that most communities in real networks have a small internal dominating set and a small external dominating set, and that the internal dominating set of a community keeps much of the information of the community. Secondly, based on the notions of the internal dominating set and the external dominating set, we define an internal slope (ISlope, for short) and an external slope (ESlope, for short) to measure the internal heterogeneity and external heterogeneity of a community respectively. We show that the internal slope (ISlope) of a community largely determines the structure of the community, that most communities in real networks are heterogeneous, meaning that most of the communities have a core/periphery structure, and that both ISlopes and ESlopes (reflecting the structure of communities) of all the communities of a network approximately follow a normal distribution. Therefore typical values of both ISolpes and ESoples of all the communities of a given network are in a narrow interval, and there is only a small number of communities having ISlopes or ESlopes out of the range of typical values of the ISlopes and ESlopes of the network. Finally, we show that all the communities of the real networks we studied, have a three degree separation phenomenon, that is, the average distance of communities is approximately 3, implying a general property of true communities for many real networks, and that good community finding algorithms find communities that amplify clustering coefficients of the networks, for many real networks.
Local Thresholding on Distributed Hash Tables
Venue: arXiv cs.DC 2013
Year: 2013

We present a binary routing tree protocol for distributed hash table overlays. Using this protocol each peer can independently route messages to its parent and two descendants on the fly without any maintenance, global context, and synchronization. The protocol is then extended to support tree change notification with similar efficiency. The resulting tree is almost perfectly dense and balanced, and has O(1) stretch if the distributed hash table is symmetric Chord. We use the tree routing protocol to overcome the main impediment for implementation of local thresholding algorithms in peer-to-peer systems -- their requirement for cycle free routing. Direct comparison of a gossip-based algorithm and a corresponding local thresholding algorithm on a majority voting problem reveals that the latter obtains superior accuracy using a fraction of the communication overhead.
Convergence of the D-iteration algorithm: convergence rate and asynchronous distributed scheme
Venue: arXiv cs.NA 2013
Year: 2013

In this paper, we define the general framework to describe the diffusion operators associated to a positive matrix. We define the equations associated to diffusion operators and present some general properties of their state vectors. We show how this can be applied to prove and improve the convergence of a fixed point problem associated to the matrix iteration scheme, including for distributed computation framework. The approach can be understood as a decomposition of the matrix-vector product operation in elementary operations at the vector entry level.
On Formal Reasoning on the Semantics of PLC using Coq
Venue: arXiv cs.SE 2013
Year: 2013

Programmable Logic Controllers (PLC) and its programming standard IEC 61131-3 are widely used in embedded systems for the industrial automation domain. We propose a framework for the formal treatment of PLC based on the IEC 61131-3 standard. A PLC system description typically combines code written in different languages that are defined in IEC 61131-3. For the top-level specification we regard the Sequential Function Charts (SFC) language, a graphical high-level language that allows to describe the main control-flow of the system. In addition to this, we describe the Instruction List (IL) language -- an assembly like language -- and two other graphical languages: Ladder Diagrams (LD) and Function Block Diagrams (FBD). IL, LD, and FBD are used to describe more low level structures of a PLC. We formalize the semantics of these languages and describe and prove relations between them. Formalization and associated proofs are carried out using the proof assistant Coq. In addition to this, we present work on a tool for automatically generating SFC representations from a graphical description -- the IL and LD languages can be handled in Coq directly -- and its usage for verification purposes. We sketch possible usages of our formal framework, and present an example application for a PLC in a project demonstrator and prove safety properties.
Topological Interference Management through Index Coding
Venue: arXiv cs.IT 2013
Year: 2013

This work studies linear interference networks, both wired and wireless, with no channel state information at the transmitters (CSIT) except a coarse knowledge of the end-to-end one-hop topology of the network that only allows a distinction between weak (zero) and significant (non-zero) channels and no further knowledge of the channel coefficients' realizations. The network capacity (wired) and DoF (wireless) are found to be bounded above by the capacity of an index coding problem for which the antidote graph is the complement of the given interference graph. The problems are shown to be equivalent under linear solutions. An interference alignment perspective is then used to translate the existing index coding solutions into the wired network capacity and wireless network DoF solutions, as well as to find new and unified solutions to different classes of all three problems.
Recommendation system for information services adapted, over terrestrial digital television
Venue: arXiv cs.CY 2013
Year: 2013

The development of digital television in Colombia has grown in last years, specially the digital terrestrial television (DTT), which is an essential part to the projects of National Minister of ICT, thanks to the big distribution and use of the television network and Internet in the country. This article explains how joining different technologies like social networks, information adaptation and DTT, to get an application that offers information services to users, based on their data, preferences, inclinations, use and interaction with others users and groups inside the network.
Instruction sequence based non-uniform complexity classes
Venue: arXiv cs.CC 2013
Year: 2013

We present an approach to non-uniform complexity in which single-pass instruction sequences play a key part, and answer various questions that arise from this approach. We introduce several kinds of non-uniform complexity classes. One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly. Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind. We also formulate a counterpart of the well-known complexity theoretic conjecture that NP is not included in P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.
Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions
Venue: arXiv cs.FL 2013
Year: 2013

The aim of this paper is to design the polynomial construction of a finite recognizer for hairpin completions of regular languages. This is achieved by considering completions as new expression operators and by applying derivation techniques to the associated extended expressions called hairpin expressions. More precisely, we extend partial derivation of regular expressions to two-sided partial derivation of hairpin expressions and we show how to deduce a recognizer for a hairpin expression from its two-sided derived term automaton, providing an alternative proof of the fact that hairpin completions of regular languages are linear context-free.
3D Geological Modeling and Visualization of Rock Masses Based on Google Earth: A Case Study
Venue: arXiv cs.GR 2013
Year: 2013

Google Earth (GE) has become a powerful tool for geological modeling and visualization. An interesting and useful feature of GE, Google Street View, can allow the GE users to view geological structure such as layers of rock masses at a field site. In this paper, we introduce a practical solution for building 3D geological models for rock masses based on the data acquired by use with GE. A real study case at Haut-Barr, France is presented to demonstrate our solution. We first locate the position of Haut-Barr in GE, and then determine the shape and scale of the rock masses in the study area, and thirdly acquire the layout of layers of rock masses in the Google Street View, and finally create the approximate 3D geological models by extruding and intersecting. The generated 3D geological models can simply reflect the basic structure of the rock masses at Haut-Barr, and can be used for visualizing the rock bodies interactively.
Embedding a balanced binary tree on a bounded point set
Venue: arXiv cs.CG 2013
Year: 2013

Given an undirected planar graph G with n vertices and a set S of n points inside a simple polygon P, a point-set embedding of G on S is a planar drawing of G such that each vertex is mapped to a distinct point of S and the edges are polygonal chains surrounded by P. A special case of the embedding problem is that in which G is a balanced binary tree. In this paper, we present a new algorithm for embedding an n-vertex balanced binary tree BBT on a set S of n points bounded by a simple m-gon P in O(m^2 + n(log n)^2 + mn) time with at most O(m) bends per edge.
Many to Many Matching with Demands and Capacities
Venue: arXiv cs.DS 2013
Year: 2013

Let A and B be two finite sets of points with total cardinality n, the many to many point matching with demands and capacities matches each point ai in A to at least alpha'i and at most alphai points in B, and each point bj in B to at least betaj and at most beta'j points in A for all 1 <= i <= s and 1 <= j <= t. In this paper, we present an upper bound for this problem using our new polynomial time algorithm.
Various improvements to text fingerprinting
Venue: arXiv cs.DS 2013
Year: 2013

Let s = s_1 .. s_n be a text (or sequence) on a finite alphabet Σof size σ. A fingerprint in s is the set of distinct characters appearing in one of its substrings. The problem considered here is to compute the set {\cal F} of all fingerprints of all substrings of s in order to answer efficiently certain questions on this set. A substring s_i .. s_j is a maximal location for a fingerprint f in F (denoted by <i,j>) if the alphabet of s_i .. s_j is f and s_{i-1}, s_{j+1}, if defined, are not in f. The set of maximal locations ins is {\cal L} (it is easy to see that |{\cal L}| \leq n σ). Two maximal locations <i,j> and <k,l> such that s_i .. s_j = s_k .. s_l are named {\em copies}, and the quotient set of {\cal L} according to the copy relation is denoted by {\cal L}_C. We present new exact and approximate efficient algorithms and data structures for the following three problems: (1) to compute {\cal F}; (2) given f as a set of distinct characters in Σ, to answer if f represents a fingerprint in {\cal F}; (3) given f, to find all maximal locations of f in s.
How good is the Electricity benchmark for evaluating concept drift adaptation
Venue: arXiv cs.LG 2013
Year: 2013

In this correspondence, we will point out a problem with testing adaptive classifiers on autocorrelated data. In such a case random change alarms may boost the accuracy figures. Hence, we cannot be sure if the adaptation is working well.
Statistical Analysis of Self-Organizing Networks with Biased Cell Association and Interference Avoidance
Venue: arXiv cs.NI 2013
Year: 2013

In this work, we assess the viability of heterogeneous networks composed of legacy macrocells which are underlaid with self-organizing picocells. Aiming to improve coverage, cell-edge throughput and overall system capacity, self-organizing solutions, such as range expansion bias, almost blank subframe and distributed antenna systems are considered. Herein, stochastic geometry is used to model network deployments, while higher-order statistics through the cumulants concept is utilized to characterize the probability distribution of the received power and aggregate interference at the user of interest. A compre- hensive analytical framework is introduced to evaluate the performance of such self-organizing networks in terms of outage probability and average channel capacity with respect to the tagged receiver. To conduct our studies, we consider a shadowed fading channel model incorporating log-normal shadowing and Nakagami-m fading. Results show that the analytical framework matches well with numerical results obtained from Monte Carlo simulations. We also observed that by simply using almost blank subframes the aggregate interference at the tagged receiver is reduced by about 12dB. Although more elaborated interference control techniques such as, downlink bitmap and distributed antennas systems become needed, when the density of picocells in the underlaid tier gets high.
On an unified framework for approachability in games with or without signals
Venue: arXiv cs.GT 2013
Year: 2013

We unify standard frameworks for approachability both in full or partial monitoring by defining a new abstract game, called the "purely informative game", where the outcome at each stage is the maximal information players can obtain, represented as some probability measure. Objectives of players can be rewritten as the convergence (to some given set) of sequences of averages of these probability measures. We obtain new results extending the approachability theory developed by Blackwell moreover this new abstract framework enables us to characterize approachable sets with, as usual, a remarkably simple and clear reformulation for convex sets. Translated into the original games, those results become the first necessary and sufficient condition under which an arbitrary set is approachable and they cover and extend previous known results for convex sets. We also investigate a specific class of games where, thanks to some unusual definition of averages and convexity, we again obtain a complete characterization of approachable sets along with rates of convergence.
A Principled Analysis of Merging Operations in Possibilistic Logic
Venue: arXiv cs.AI 2013
Year: 2013

Possibilistic logic offers a qualitative framework for representing pieces of information associated with levels of uncertainty of priority. The fusion of multiple sources information is discussed in this setting. Different classes of merging operators are considered including conjunctive, disjunctive, reinforcement, adaptive and averaging operators. Then we propose to analyse these classes in terms of postulates. This is done by first extending the postulate for merging classical bases to the case where priorites are avaialbe.
A Bayesian Method for Causal Modeling and Discovery Under Selection
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a Bayesian method for learning causal networks using samples that were selected in a non-random manner from a population of interest. Examples of data obtained by non-random sampling include convenience samples and case-control data in which a fixed number of samples with and without some condition is collected; such data are not uncommon. The paper describes a method for combining data under selection with prior beliefs in order to derive a posterior probability for a model of the causal processes that are generating the data in the population of interest. The priors include beliefs about the nature of the non-random sampling procedure. Although exact application of the method would be computationally intractable for most realistic datasets, efficient special-case and approximation methods are discussed. Finally, the paper describes how to combine learning under selection with previous methods for learning from observational and experimental data that are obtained on random samples of the population of interest. The net result is a Bayesian methodology that supports causal modeling and discovery from a rich mixture of different types of data.
Any-Space Probabilistic Inference
Venue: arXiv cs.AI 2013
Year: 2013

We have recently introduced an any-space algorithm for exact inference in Bayesian networks, called Recursive Conditioning, RC, which allows one to trade space with time at increments of X-bytes, where X is the number of bytes needed to cache a floating point number. In this paper, we present three key extensions of RC. First, we modify the algorithm so it applies to more general factorization of probability distributions, including (but not limited to) Bayesian network factorizations. Second, we present a forgetting mechanism which reduces the space requirements of RC considerably and then compare such requirmenets with those of variable elimination on a number of realistic networks, showing orders of magnitude improvements in certain cases. Third, we present a version of RC for computing maximum a posteriori hypotheses (MAP), which turns out to be the first MAP algorithm allowing a smooth time-space tradeoff. A key advantage of presented MAP algorithm is that it does not have to start from scratch each time a new query is presented, but can reuse some of its computations across multiple queries, leading to significant savings in ceratain cases.
Building a Stochastic Dynamic Model of Application Use
Venue: arXiv cs.AI 2013
Year: 2013

Many intelligent user interfaces employ application and user models to determine the user's preferences, goals and likely future actions. Such models require application analysis, adaptation and expansion. Building and maintaining such models adds a substantial amount of time and labour to the application development cycle. We present a system that observes the interface of an unmodified application and records users' interactions with the application. From a history of such observations we build a coarse state space of observed interface states and actions between them. To refine the space, we hypothesize sub-states based upon the histories that led users to a given state. We evaluate the information gain of possible state splits, varying the length of the histories considered in such splits. In this way, we automatically produce a stochastic dynamic model of the application and of how it is used. To evaluate our approach, we present models derived from real-world application usage data.
Probabilistic Arc Consistency: A Connection between Constraint Reasoning and Probabilistic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

We document a connection between constraint reasoning and probabilistic reasoning. We present an algorithm, called {em probabilistic arc consistency}, which is both a generalization of a well known algorithm for arc consistency used in constraint reasoning, and a specialization of the belief updating algorithm for singly-connected networks. Our algorithm is exact for singly- connected constraint problems, but can work well as an approximation for arbitrary problems. We briefly discuss some empirical results, and related methods.
Feature Selection and Dualities in Maximum Entropy Discrimination
Venue: arXiv cs.LG 2013
Year: 2013

Incorporating feature selection into a classification or regression method often carries a number of advantages. In this paper we formalize feature selection specifically from a discriminative perspective of improving classification/regression accuracy. The feature selection method is developed as an extension to the recently proposed maximum entropy discrimination (MED) framework. We describe MED as a flexible (Bayesian) regularization approach that subsumes, e.g., support vector classification, regression and exponential family models. For brevity, we restrict ourselves primarily to feature selection in the context of linear classification/regression methods and demonstrate that the proposed approach indeed carries substantial improvements in practice. Moreover, we discuss and develop various extensions of feature selection, including the problem of dealing with example specific but unobserved degrees of freedom -- alignments or invariants.
Causal Mechanism-based Model Construction
Venue: arXiv cs.AI 2013
Year: 2013

We propose a framework for building graphical causal model that is based on the concept of causal mechanisms. Causal models are intuitive for human users and, more importantly, support the prediction of the effect of manipulation. We describe an implementation of the proposed framework as an interactive model construction module, ImaGeNIe, in SMILE (Structural Modeling, Inference, and Learning Engine) and in GeNIe (SMILE's Windows user interface).
Representing and Solving Asymmetric Bayesian Decision Problems
Venue: arXiv cs.AI 2013
Year: 2013

This paper deals with the representation and solution of asymmetric Bayesian decision problems. We present a formal framework, termed asymmetric influence diagrams, that is based on the influence diagram and allows an efficient representation of asymmetric decision problems. As opposed to existing frameworks, the asymmetric influece diagram primarily encodes asymmetry at the qualitative level and it can therefore be read directly from the model. We give an algorithm for solving asymmetric influence diagrams. The algorithm initially decomposes the asymmetric decision problem into a structure of symmetric subproblems organized as a tree. A solution to the decision problem can then be found by propagating from the leaves toward the root using existing evaluation methods to solve the sub-problems.