OpenRaiser/Intern-Atlas huggingface dataset:
On Characterizing the Data Movement Complexity of Computational DAGs for Parallel Execution
Venue: arXiv cs.DC 2014
Year: 2014

Technology trends are making the cost of data movement increasingly dominant, both in terms of energy and time, over the cost of performing arithmetic operations in computer systems. The fundamental ratio of aggregate data movement bandwidth to the total computational power (also referred to the machine balance parameter) in parallel computer systems is decreasing. It is there- fore of considerable importance to characterize the inherent data movement requirements of parallel algorithms, so that the minimal architectural balance parameters required to support it on future systems can be well understood. In this paper, we develop an extension of the well-known red-blue pebble game to develop lower bounds on the data movement complexity for the parallel execution of computational directed acyclic graphs (CDAGs) on parallel systems. We model multi-node multi-core parallel systems, with the total physical memory distributed across the nodes (that are connected through some interconnection network) and in a multi-level shared cache hierarchy for processors within a node. We also develop new techniques for lower bound characterization of non-homogeneous CDAGs. We demonstrate the use of the methodology by analyzing the CDAGs of several numerical algorithms, to develop lower bounds on data movement for their parallel execution.
Nearly Optimal Computations with Structured Matrices
Venue: arXiv cs.SC 2014
Year: 2014

We estimate the Boolean complexity of multiplication of structured matrices by a vector and the solution of nonsingular linear systems of equations with these matrices. We study four basic most popular classes, that is, Toeplitz, Hankel, Cauchy and Van-der-monde matrices, for which the cited computational problems are equivalent to the task of polynomial multiplication and division and polynomial and rational multipoint evaluation and interpolation. The Boolean cost estimates for the latter problems have been obtained by Kirrinnis in \cite{kirrinnis-joc-1998}, except for rational interpolation, which we supply now. All known Boolean cost estimates for these problems rely on using Kronecker product. This implies the $d$-fold precision increase for the $d$-th degree output, but we avoid such an increase by relying on distinct techniques based on employing FFT. Furthermore we simplify the analysis and make it more transparent by combining the representation of our tasks and algorithms in terms of both structured matrices and polynomials and rational functions. This also enables further extensions of our estimates to cover Trummer's important problem and computations with the popular classes of structured matrices that generalize the four cited basic matrix classes.
OSHI - Open Source Hybrid IP/SDN networking (and its emulation on Mininet and on distributed SDN testbeds)
Venue: arXiv cs.NI 2014
Year: 2014

The introduction of SDN in IP backbones requires the coexistence of regular IP forwarding and SDN based forwarding. The former is typically applied to best effort Internet traffic, the latter can be used for different types of advanced services (VPNs, Virtual Leased Lines, Traffic Engineering...). In this paper we first introduce the architecture and the services of an "hybrid" IP/SDN networking scenario. Then we describe the design and implementation of an Open Source Hybrid IP/SDN (OSHI) node. It combines Quagga for OSPF routing and Open vSwitch for OpenFlow based switching on Linux. The availability of tools for experimental validation and performance evaluation of SDN solutions is fundamental for the evolution of SDN. We provide a set of open source tools that allow to facilitate the design of hybrid IP/SDN experimental networks, their deployment on Mininet or on distributed SDN research testbeds and their test. Finally, using the provided tools, we evaluate key performance aspects of the proposed solutions. The OSHI development and test environment is available in a VirtualBox VM image that can be downloaded.
Performance Analysis of Ambient RF Energy Harvesting: A Stochastic Geometry Approach
Venue: arXiv cs.IT 2014
Year: 2014

Ambient RF (Radio Frequency) energy harvesting technique has recently been proposed as a potential solution to provide proactive energy replenishment for wireless devices. This paper aims to analyze the performance of a battery-free wireless sensor powered by ambient RF energy harvesting using a stochastic-geometry approach. Specifically, we consider a random network model in which ambient RF sources are distributed as a Ginibre $α$-determinantal point process which recovers the Poisson point process when alpha? approaches zero. We characterize the expected RF energy harvesting rate.We also perform a worst-case study which derives the upper bounds of both power outage and transmission outage probabilities. Numerical results show that our upper bounds are accurate and that better performance is achieved when the distribution of ambient sources exhibits stronger repulsion.
Matching Curves to Imprecise Point Sets using Fréchet Distance
Venue: arXiv cs.CG 2014
Year: 2014

Let $P$ be a polygonal curve in $\mathbb{R}^d$ of length $n$, and $S$ be a point-set of size $k$. The Curve/Point Set Matching problem consists of finding a polygonal curve $Q$ on $S$ such that the Fréchet distance from $P$ is less than a given $\varepsilon$. We consider eight variations of the problem based on the distance metric used and the omittability or repeatability of the points. We provide closure to a recent series of complexity results for the case where $S$ consists of precise points. More importantly, we formulate a more realistic version of the problem that takes into account measurement errors. This new problem is posed as the matching of a given curve to a set of imprecise points. We prove that all three variations of the problem that are in P when $S$ consists of precise points become NP-complete when $S$ consists of imprecise points. We also discuss approximation results.
Comparison of the Research Effectiveness of Chemistry Nobelists and Fields Medalist Mathematicians with Google Scholar: the Yule-Simon Model
Venue: arXiv cs.DL 2014
Year: 2014

This paper uses the Yule-Simon model to estimate to what extent the work of chemistry Nobelists and Fields medalist mathematicians is incorporated into the knowledge corpus of their disciplines as measured by Google Scholar inlinks. Due to differences in the disciplines and prizes, it finds that the work of chemistry Nobelists is better incorporated than that of Fields medalists.
Geometric Abstraction from Noisy Image-Based 3D Reconstructions
Venue: arXiv cs.CV 2014
Year: 2014

Creating geometric abstracted models from image-based scene reconstructions is difficult due to noise and irregularities in the reconstructed model. In this paper, we present a geometric modeling method for noisy reconstructions dominated by planar horizontal and orthogonal vertical structures. We partition the scene into horizontal slices and create an inside/outside labeling represented by a floor plan for each slice by solving an energy minimization problem. Consecutively, we create an irregular discretization of the volume according to the individual floor plans and again label each cell as inside/outside by minimizing an energy function. By adjusting the smoothness parameter, we introduce different levels of detail. In our experiments, we show results with varying regularization levels using synthetically generated and real-world data.
A Generalized Cut-Set Bound for Deterministic Multi-Flow Networks and its Applications
Venue: arXiv cs.IT 2014
Year: 2014

We present a new outer bound for the sum capacity of general multi-unicast deterministic networks. Intuitively, this bound can be understood as applying the cut-set bound to concatenated copies of the original network with a special restriction on the allowed transmit signal distributions. We first study applications to finite-field networks, where we obtain a general outer-bound expression in terms of ranks of the transfer matrices. We then show that, even though our outer bound is for deterministic networks, a recent result relating the capacity of AWGN KxKxK networks and the capacity of a deterministic counterpart allows us to establish an outer bound to the DoF of KxKxK wireless networks with general connectivity. This bound is tight in the case of the "adjacent-cell interference" topology, and yields graph-theoretic necessary and sufficient conditions for K DoF to be achievable in general topologies.
A Geometric Distance Oracle for Large Real-World Graphs
Venue: arXiv cs.SI 2014
Year: 2014

Many graph processing algorithms require determination of shortest-path distances between arbitrary numbers of node pairs. Since computation of exact distances between all node-pairs of a large graph, e.g., 10M nodes and up, is prohibitively expensive both in computational time and storage space, distance approximation is often used in place of exact computation. In this paper, we present a novel and scalable distance oracle that leverages the hyperbolic core of real-world large graphs for fast and scalable distance approximation. We show empirically that the proposed oracle significantly outperforms prior oracles on a random set of test cases drawn from public domain graph libraries. There are two sets of prior work against which we benchmark our approach. The first set, which often outperforms other oracles, employs embedding of the graph into low dimensional Euclidean spaces with carefully constructed hyperbolic distances, but provides no guarantees on the distance estimation error. The second set leverages Gromov-type tree contraction of the graph with the additive error guaranteed not to exceed $2δ\log{n}$, where $δ$ is the hyperbolic constant of the graph. We show that our proposed oracle 1) is significantly faster than those oracles that use hyperbolic embedding (first set) with similar approximation error and, perhaps surprisingly, 2) exhibits substantially lower average estimation error compared to Gromov-like tree contractions (second set). We substantiate our claims through numerical computations on a collection of a dozen real world networks and synthetic test cases from multiple domains, ranging in size from 10s of thousand to 10s of millions of nodes.
Using Covert Topological Information for Defense Against Malicious Attacks on DC State Estimation
Venue: arXiv cs.CR 2014
Year: 2014

Accurate state estimation is of paramount importance to maintain the power system operating in a secure and efficient state. The recently identified coordinated data injection attacks to meter measurements can bypass the current security system and introduce errors to the state estimates. The conventional wisdom to mitigate such attacks is by securing meter measurements to evade malicious injections. In this paper, we provide a novel alternative to defend against false-data injection attacks using covert power network topological information. By keeping the exact reactance of a set of transmission lines from attackers, no false data injection attack can be launched to compromise any set of state variables. We first investigate from the attackers' perspective the necessary condition to perform injection attack. Based on the arguments, we characterize the optimal protection problem, which protects the state variables with minimum cost, as a well-studied Steiner tree problem in a graph. Besides, we also propose a mixed defending strategy that jointly considers the use of covert topological information and secure meter measurements when either method alone is costly or unable to achieve the protection objective. A mixed integer linear programming (MILP) formulation is introduced to obtain the optimal mixed defending strategy. To tackle the NP-hardness of the problem, a tree pruning-based heuristic is further presented to produce an approximate solution in polynomial time. The advantageous performance of the proposed defending mechanisms is verified in IEEE standard power system testcases.
TurKPF: TurKontrol as a Particle Filter
Venue: arXiv cs.AI 2014
Year: 2014

TurKontrol, and algorithm presented in (Dai et al. 2010), uses a POMDP to model and control an iterative workflow for crowdsourced work. Here, TurKontrol is re-implemented as "TurKPF," which uses a Particle Filter to reduce computation time & memory usage. Most importantly, in our experimental environment with default parameter settings, the action is chosen nearly instantaneously. Through a series of experiments we see that TurKPF and TurKontrol perform similarly.
InfluenceTracker: Rating the impact of a Twitter account
Venue: arXiv cs.SI 2014
Year: 2014

We describe a methodology of rating the influence of a Twitter ac-count in this famous microblogging service. We then evaluate it over real ac-counts, under the belief that influence is not only a matter of quantity (amount of followers), but also a mixture of quality measures that reflect interaction, awareness, and visibility in the social sphere. The authors of this paper have created InfluenceTracker, a publicly available website where anyone can rate and compare the recent activity of any Twitter account.
Intelligent Remote Control for TV Program based on Emotion in Arabic Speech
Venue: arXiv cs.HC 2014
Year: 2014

Recommender systems for TV program have been studied for the realization of personalized TV Electronic Program Guides. In this paper, we propose automatic emotion Arabic speech recognition in order to achieve an intelligent remote control. In addition, the TV can estimate our interests and preferences by observing our behavior to watch and have a conversation on topics that might be interesting to us.
Simultaneous Source for non-uniform data variance and missing data
Venue: arXiv cs.CE 2014
Year: 2014

The use of simultaneous sources in geophysical inverse problems has revolutionized the ability to deal with large scale data sets that are obtained from multiple source experiments. However, the technique breaks when the data has non-uniform standard deviation or when some data are missing. In this paper we develop, study, and compare a number of techniques that enable to utilize advantages of the simultaneous source framework for these cases. We show that the inverse problem can still be solved efficiently by using these new techniques. We demonstrate our new approaches on the Direct Current Resistivity inverse problem.
Fast Approximate Matching of Cell-Phone Videos for Robust Background Subtraction
Venue: arXiv cs.CV 2014
Year: 2014

We identify a novel instance of the background subtraction problem that focuses on extracting near-field foreground objects captured using handheld cameras. Given two user-generated videos of a scene, one with and the other without the foreground object(s), our goal is to efficiently generate an output video with only the foreground object(s) present in it. We cast this challenge as a spatio-temporal frame matching problem, and propose an efficient solution for it that exploits the temporal smoothness of the video sequences. We present theoretical analyses for the error bounds of our approach, and validate our findings using a detailed set of simulation experiments. Finally, we present the results of our approach tested on multiple real videos captured using handheld cameras, and compare them to several alternate foreground extraction approaches.
Vers l'auto-gestion d'un réseau de radio cognitive
Venue: arXiv cs.NI 2014
Year: 2014

Cognitive Radio (CR) operates in different fields as varied, one of these is cognitive radio networks. In this paper, we propose a new approach used CR, which aims to manage potential failures of computer systems and applications through the introduction of two aspects of autonomous networks to make systems capable of managing themselves with minimum human intervention.
Cooperating distributed context-free hexagonal array grammar systems with permitting contexts
Venue: arXiv cs.FL 2014
Year: 2014

In this paper we associate permitting symbols with rules of Grammars in the components of cooperating distributed context free hexagonal array grammar systems as a control mechanism and investigating the generative power of the resulting systems in the terminal mode. This feature of associating permitting symbols with rules when extended to patterns in the form of connected arrays also requires checking of symbols, but this is simpler than usual pattern matching. The benefit of allowing permitting symbols is that it enables us to reduce the number of components required in a cooperating distributed hexagonal array grammar system for generating a set of picture arrays.
Degradation Analysis of Probabilistic Parallel Choice Systems
Venue: arXiv cs.PF 2014
Year: 2014

Degradation analysis is used to analyze the useful lifetimes of systems, their failure rates, and various other system parameters like mean time to failure (MTTF), mean time between failures (MTBF), and the system failure rate (SFR). In many systems, certain possible parallel paths of execution that have greater chances of success are preferred over others. Thus we introduce here the concept of probabilistic parallel choice. We use binary and $n$-ary probabilistic choice operators in describing the selections of parallel paths. These binary and $n$-ary probabilistic choice operators are considered so as to represent the complete system (described as a series-parallel system) in terms of the probabilities of selection of parallel paths and their relevant parameters. Our approach allows us to derive new and generalized formulae for system parameters like MTTF, MTBF, and SFR. We use a generalized exponential distribution, allowing distinct installation times for individual components, and use this model to derive expressions for such system parameters.
Stochastic Privacy
Venue: arXiv cs.AI 2014
Year: 2014

Online services such as web search and e-commerce applications typically rely on the collection of data about users, including details of their activities on the web. Such personal data is used to enhance the quality of service via personalization of content and to maximize revenues via better targeting of advertisements and deeper engagement of users on sites. To date, service providers have largely followed the approach of either requiring or requesting consent for opting-in to share their data. Users may be willing to share private information in return for better quality of service or for incentives, or in return for assurances about the nature and extend of the logging of data. We introduce \emph{stochastic privacy}, a new approach to privacy centering on a simple concept: A guarantee is provided to users about the upper-bound on the probability that their personal data will be used. Such a probability, which we refer to as \emph{privacy risk}, can be assessed by users as a preference or communicated as a policy by a service provider. Service providers can work to personalize and to optimize revenues in accordance with preferences about privacy risk. We present procedures, proofs, and an overall system for maximizing the quality of services, while respecting bounds on allowable or communicated privacy risk. We demonstrate the methodology with a case study and evaluation of the procedures applied to web search personalization. We show how we can achieve near-optimal utility of accessing information with provable guarantees on the probability of sharing data.
Causal study of Network Performance
Venue: arXiv cs.NI 2014
Year: 2014

The use of Internet in the every day life has pushed its evolution in a very fast way. The heterogeneity of the equipments supporting its networks, as well as the different devices from which it can be accessed, have participated in increasing the complexity of understanding its global behavior and performance. In our study we propose a new method for studying the performance of TCP protocol based on causal graphs. Causal graphs offer models easy to interpret and use. They highlight the structural model of the system they represent and give us access to the causal dependences between the different parameters of the system. One of the major contribution of causal graphs is their ability to predict the effects of an intervention from observations made before this intervention.
Electricity Pooling Markets with Strategic Producers Possessing Asymmetric Information II: Inelastic Demand
Venue: arXiv cs.GT 2014
Year: 2014

In the restructured electricity industry, electricity pooling markets are an oligopoly with strategic producers possessing private information (private production cost function). We focus on pooling markets where aggregate demand is represented by a non-strategic agent. Inelasticity of demand is a main difficulty in electricity markets which can potentially result in market failure and high prices. We consider demand to be inelastic. We propose a market mechanism that has the following features. (F1) It is individually rational. (F2) It is budget balanced. (F3) It is price efficient, that is, at equilibrium the price of electricity is equal to the marginal cost of production. (F4) The energy production profile corresponding to every non-zero Nash equilibrium of the game induced by the mechanism is a solution of the corresponding centralized problem where the objective is the maximization of the sum of the producers' and consumers' utilities. We identify some open problems associated with our approach to electricity pooling markets.
ILP Modulo Data
Venue: arXiv cs.LO 2014
Year: 2014

The vast quantity of data generated and captured every day has led to a pressing need for tools and processes to organize, analyze and interrelate this data. Automated reasoning and optimization tools with inherent support for data could enable advancements in a variety of contexts, from data-backed decision making to data-intensive scientific research. To this end, we introduce a decidable logic aimed at database analysis. Our logic extends quantifier-free Linear Integer Arithmetic with operators from Relational Algebra, like selection and cross product. We provide a scalable decision procedure that is based on the BC(T) architecture for ILP Modulo Theories. Our decision procedure makes use of database techniques. We also experimentally evaluate our approach, and discuss potential applications.
Straightening out planar poly-line drawings
Venue: arXiv cs.CG 2014
Year: 2014

We show that any $y$-monotone poly-line drawing can be straightened out while maintaining $y$-coordinates and height. The width may increase much, but we also show that on some graphs exponential width is required if we do not want to increase the height. Likewise $y$-monotonicity is required: there are poly-line drawings (not $y$-monotone) that cannot be straightened out while maintaining the height. We give some applications of our result.
Linearization of Time-Varying Nonlinear Systems Using A Modified Linear Iterative Method
Venue: arXiv cs.SY 2014
Year: 2014

The linearization of nonlinear systems is an important digital enhancement technique. In this paper, a real-time capable post- and pre-linearization method for the widely applicable time-varying discrete-time Volterra series is presented. To this end, an alternative view on the Volterra series is established, which enables the utilization of certain modified linear iterative methods for linearization. For one particular linear iterative method, the Richardson iteration, the corresponding post- and pre-linearizers are discussed in detail. It is motivated that the resulting algorithm can be regarded as a generalization of some existing methods. Furthermore, a simply verifiable condition for convergence is presented, which allows the straightforward evaluation of applicability. The proposed method is demonstrated by means of the linearization of a time-varying nonlinear amplifier, which highlights its capability of linearizing significantly distorted signals, illustrates the advantageous convergence behavior, and depicts its robustness against modeling errors.