OpenRaiser/Intern-Atlas huggingface dataset:
3D Density Histograms for Criteria-driven Edge Bundling
Venue: arXiv cs.GR 2015
Year: 2015

This paper presents a graph bundling algorithm that agglomerates edges taking into account both spatial proximity as well as user-defined criteria in order to reveal patterns that were not perceivable with previous bundling techniques. Each edge belongs to a group that may either be an input of the problem or found by clustering one or more edge properties such as origin, destination, orientation, length or domain-specific properties. Bundling is driven by a stack of density maps, with each map capturing both the edge density of a given group as well as interactions with edges from other groups. Density maps are efficiently calculated by smoothing 2D histograms of edge occurrence using repeated averaging filters based on integral images. A CPU implementation of the algorithm is tested on several graphs, and different grouping criteria are used to illustrate how the proposed technique can render different visualizations of the same data. Bundling performance is much higher than on previous approaches, being particularly noticeable on large graphs, with millions of edges being bundled in seconds.
Syntactic Monoids in a Category
Venue: arXiv cs.LO 2015
Year: 2015

The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polak (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is an entropic variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in case the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.
High Density Noise Removal by Cascading Algorithms
Venue: arXiv cs.CV 2015
Year: 2015

An advanced non-linear cascading filter algorithm for the removal of high density salt and pepper noise from the digital images is proposed. The proposed method consists of two stages. The first stage Decision base Median Filter (DMF) acts as the preliminary noise removal algorithm. The second stage is either Modified Decision Base Partial Trimmed Global Mean Filter (MDBPTGMF) or Modified Decision Based Unsymmetric Trimmed Median Filter (MDBUTMF) which is used to remove the remaining noise and enhance the image quality. The DMF algorithm performs well at low noise density but it fails to remove the noise at medium and high level. The MDBPTGMF and MDUTMF have excellent performance at low, medium and high noise density but these reduce the image quality and blur the image at high noise level. So the basic idea behind this paper is to combine the advantages of the filters used in both the stages to remove the Salt and Pepper noise and enhance the image quality at all the noise density level. The proposed method is tested against different gray scale images and it gives better Mean Absolute Error (MAE), Peak Signal to Noise Ratio (PSNR) and Image Enhancement Factor (IEF) than the Adaptive Median Filter (AMF), Decision Base Unsymmetric Trimmed Median Filter (DBUTMF), Modified Decision Base Unsymmetric Trimmed Median Filter (MDBUTMF) and Decision Base Partial Trimmed Global Mean Filter (DBPTGMF).
Looking at Mean-Payoff through Foggy Windows
Venue: arXiv cs.LO 2015
Year: 2015

Mean-payoff games (MPGs) are infinite duration two-player zero-sum games played on weighted graphs. Under the hypothesis of perfect information, they admit memoryless optimal strategies for both players and can be solved in NP-intersect-coNP. MPGs are suitable quantitative models for open reactive systems. However, in this context the assumption of perfect information is not always realistic. For the partial-observation case, the problem that asks if the first player has an observation-based winning strategy that enforces a given threshold on the mean-payoff, is undecidable. In this paper, we study the window mean-payoff objectives that were introduced recently as an alternative to the classical mean-payoff objectives. We show that, in sharp contrast to the classical mean-payoff objectives, some of the window mean-payoff objectives are decidable in games with partial-observation.
Non-wellfounded trees in Homotopy Type Theory
Venue: arXiv cs.LO 2015
Year: 2015

We prove a conjecture about the constructibility of coinductive types - in the principled form of indexed M-types - in Homotopy Type Theory. The conjecture says that in the presence of inductive types, coinductive types are derivable. Indeed, in this work, we construct coinductive types in a subsystem of Homotopy Type Theory; this subsystem is given by Intensional Martin-Löf type theory with natural numbers and Voevodsky's Univalence Axiom. Our results are mechanized in the computer proof assistant Agda.
On the Scalability of LISP Mappings Caches
Venue: arXiv cs.NI 2015
Year: 2015

The Locator/ID Separation Protocol (LISP) limits the growth of the Default-Free Zone routing tables by creating a highly aggregatable and quasi-static Internet core. However, LISP pushes the forwarding state to edge routers whose timely operation relies on caching of location to identity bindings. In this paper we develop an analytical model to study the asymptotic scalability of the LISP cache. Under the assumptions that (i) long-term popularity can be modeled as a constant Generalized Zipf distribution and (ii) temporal locality is predominantly determined by long-term popularity, we find that the scalability of the LISP cache is O(1) with respect to the amount of prefixes (Internet growth) and users (growth of the LISP site). We validate the model and discuss the accuracy of our assumptions using several one-day-long packet traces.
Almost Lossless Analog Compression without Phase Information
Venue: arXiv cs.IT 2015
Year: 2015

We propose an information-theoretic framework for phase retrieval. Specifically, we consider the problem of recovering an unknown n-dimensional vector x up to an overall sign factor from m=Rn phaseless measurements with compression rate R and derive a general achievability bound for R. Surprisingly, it turns out that this bound on the compression rate is the same as the one for almost lossless analog compression obtained by Wu and Verdú (2010): Phaseless linear measurements are as good as linear measurements with full phase information in the sense that ignoring the sign of m measurements only leaves us with an ambiguity with respect to an overall sign factor of x.
Analysis of a Classical Matrix Preconditioning Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

We study a classical iterative algorithm for balancing matrices in the $L_\infty$ norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett \& Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for any irreducible $n\times n$ (real or complex) input matrix~$A$, a natural variant of the algorithm converges in $O(n^3\log(nρ/\varepsilon))$ elementary balancing operations, where $ρ$ measures the initial imbalance of~$A$ and $\varepsilon$ is the target imbalance of the output matrix. (The imbalance of~$A$ is $\max_i |\log(a_i^{\text{out}}/a_i^{\text{in}})|$, where $a_i^{\text{out}},a_i^{\text{in}}$ are the maximum entries in magnitude in the $i$th row and column respectively.) This bound is tight up to the $\log n$ factor. A balancing operation scales the $i$th row and column so that their maximum entries are equal, and requires $O(m/n)$ arithmetic operations on average, where $m$ is the number of non-zero elements in~$A$. Thus the running time of the iterative algorithm is $\tilde{O}(n^2m)$. This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed.
Wide-area Wireless Communication Challenges for the Internet of Things
Venue: arXiv cs.IT 2015
Year: 2015

Aided by the ubiquitous wireless connectivity, declining communication costs, and the emergence of cloud platforms, the deployment of Internet of Things (IoT) devices and services is accelerating. Most major mobile network operators view machine-to-machine (M2M) communication networks for supporting IoT as a significant source of new revenue. In this paper, we motivate the need for wide-area M2M wireless networks, especially for short data packet communication to support a very large number of IoT devices. We first present a brief overview of current and emerging technologies for supporting wide area M2M, and then using communication theory principles, discuss the fundamental challenges and potential solutions for these networks, highlighting tradeoffs and strategies for random and scheduled access. We conclude with recommendations for how future 5G networks should be designed for efficient wide-area M2M communications.
Testing Cluster Structure of Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter $\varepsilon$, a $d$-bounded degree graph is defined to be $(k, ϕ)$-clusterable, if it can be partitioned into no more than $k$ parts, such that the (inner) conductance of the induced subgraph on each part is at least $ϕ$ and the (outer) conductance of each part is at most $c_{d,k}\varepsilon^4ϕ^2$, where $c_{d,k}$ depends only on $d,k$. Our main result is a sublinear algorithm with the running time $\widetilde{O}(\sqrt{n}\cdot\mathrm{poly}(ϕ,k,1/\varepsilon))$ that takes as input a graph with maximum degree bounded by $d$, parameters $k$, $ϕ$, $\varepsilon$, and with probability at least $\frac23$, accepts the graph if it is $(k,ϕ)$-clusterable and rejects the graph if it is $\varepsilon$-far from $(k, ϕ^*)$-clusterable for $ϕ^* = c'_{d,k}\frac{ϕ^2 \varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower bound of $Ω(\sqrt{n})$ on the number of queries needed for testing graph expansion, which corresponds to $k=1$ in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.
A Survey on Privacy and Security in Online Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Online Social Networks (OSN) are a permanent presence in today's personal and professional lives of a huge segment of the population, with direct consequences to offline activities. Built on a foundation of trust-users connect to other users with common interests or overlapping personal trajectories-online social networks and the associated applications extract an unprecedented volume of personal information. Unsurprisingly, serious privacy and security risks emerged, positioning themselves along two main types of attacks: attacks that exploit the implicit trust embedded in declared social relationships; and attacks that harvest user's personal information for ill-intended use. This article provides an overview of the privacy and security issues that emerged so far in OSNs. We introduce a taxonomy of privacy and security attacks in OSNs, we overview existing solutions to mitigate those attacks, and outline challenges still to overcome.
Tractable Query Answering and Optimization for Extensions of Weakly-Sticky Datalog+-
Venue: arXiv cs.DB 2015
Year: 2015

We consider a semantic class, weakly-chase-sticky (WChS), and a syntactic subclass, jointly-weakly-sticky (JWS), of Datalog+- programs. Both extend that of weakly-sticky (WS) programs, which appear in our applications to data quality. For WChS programs we propose a practical, polynomial-time query answering algorithm (QAA). We establish that the two classes are closed under magic-sets rewritings. As a consequence, QAA can be applied to the optimized programs. QAA takes as inputs the program (including the query) and semantic information about the "finiteness" of predicate positions. For the syntactic subclasses JWS and WS of WChS, this additional information is computable.
Clustering Assisted Fundamental Matrix Estimation
Venue: arXiv cs.CV 2015
Year: 2015

In computer vision, the estimation of the fundamental matrix is a basic problem that has been extensively studied. The accuracy of the estimation imposes a significant influence on subsequent tasks such as the camera trajectory determination and 3D reconstruction. In this paper we propose a new method for fundamental matrix estimation that makes use of clustering a group of 4D vectors. The key insight is the observation that among the 4D vectors constructed from matching pairs of points obtained from the SIFT algorithm, well-defined cluster points tend to be reliable inliers suitable for fundamental matrix estimation. Based on this, we utilizes a recently proposed efficient clustering method through density peaks seeking and propose a new clustering assisted method. Experimental results show that the proposed algorithm is faster and more accurate than currently commonly used methods.
Image Denoising Using Low Rank Minimization With Modified Noise Estimation
Venue: arXiv cs.CV 2015
Year: 2015

Recently, the application of low rank minimization to image denoising has shown remarkable denoising results which are equivalent or better than those of the existing state-of-the-art algorithms. However, due to iterative nature of low rank optimization, estimation of residual noise is an essential requirement after each iteration. Currently, this noise is estimated by using the filtered noise in the previous iteration without considering the geometric structure of the given image. This estimate may be affected in the presence of moderate and severe levels of noise. To obtain a more reliable estimate of residual noise, we propose a modified algorithm (GWNNM) which includes the contribution of the geometric structure of an image to the existing noise estimation. Furthermore, the proposed algorithm exploits the difference of large and small singular values to enhance the edges and textures during the denoising process. Consequently, the proposed modifications achieve significant improvements in the denoising results of the existing low rank optimization algorithms.
Design Tool To Express Failure Detection Protocols
Venue: arXiv cs.DC 2015
Year: 2015

Failure detection protocols---a fundamental building block for crafting fault-tolerant distributed systems---are in many cases described by their authors making use of informal pseudo-codes of their conception. Often these pseudo-codes use syntactical constructs that are not available in COTS programming languages such as C or C++. This translates into informal descriptions that call for ad hoc interpretations and implementations. Being informal, these descriptions cannot be tested by their authors, which may translate into insufficiently detailed or even faulty specifications. This paper tackles this problem introducing a formal syntax for those constructs and a C library that implements them---a tool-set to express and reason about failure detection protocols. The resulting specifications are longer but non ambiguous, and eligible for becoming a standard form.
Distributed Nonlinear MPC of Multi-Agent Systems with Data Compression and Random Delays - Extended Version
Venue: arXiv cs.SY 2015
Year: 2015

This is an extended version of a technical note accepted for publication in IEEE Transactions on Automatic Control. The note proposes an Input to State practically Stable (ISpS) formulation of distributed nonlinear model predictive controller (NMPC) for formation control of constrained autonomous vehicles in presence of communication bandwidth limitation and transmission delays. Planned trajectories are compressed using neural networks resulting in considerable reduction of data packet size, while being robust to propagation delays and uncertainty in neighbors' trajectories. Collision avoidance is achieved by means of spatially filtered potential field. Analytical results proving ISpS and generalized small gain conditions are presented for both strongly- and weakly-connected networks, and illustrated by simulations.
Regret vs. Communication: Distributed Stochastic Multi-Armed Bandits and Beyond
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we consider the distributed stochastic multi-armed bandit problem, where a global arm set can be accessed by multiple players independently. The players are allowed to exchange their history of observations with each other at specific points in time. We study the relationship between regret and communication. When the time horizon is known, we propose the Over-Exploration strategy, which only requires one-round communication and whose regret does not scale with the number of players. When the time horizon is unknown, we measure the frequency of communication through a new notion called the density of the communication set, and give an exact characterization of the interplay between regret and communication. Specifically, a lower bound is established and stable strategies that match the lower bound are developed. The results and analyses in this paper are specific but can be translated into more general settings.
ISP-friendly Peer-assisted On-demand Streaming of Long Duration Content in BBC iPlayer
Venue: arXiv cs.NI 2015
Year: 2015

In search of scalable solutions, CDNs are exploring P2P support. However, the benefits of peer assistance can be limited by various obstacle factors such as ISP friendliness - requiring peers to be within the same ISP, bitrate stratification - the need to match peers with others needing similar bitrate, and partial participation - some peers choosing not to redistribute content. This work relates potential gains from peer assistance to the average number of users in a swarm, its capacity, and empirically studies the effects of these obstacle factors at scale, using a month-long trace of over 2 million users in London accessing BBC shows online. Results indicate that even when P2P swarms are localised within ISPs, up to 88% of traffic can be saved. Surprisingly, bitrate stratification results in 2 large sub-swarms and does not significantly affect savings. However, partial participation, and the need for a minimum swarm size do affect gains. We investigate improvements to gain from increasing content availability through two well-studied techniques: content bundling - combining multiple items to increase availability, and historical caching of previously watched items. Bundling proves ineffective as increased server traffic from larger bundles outweighs benefits of availability, but simple caching can considerably boost traffic gains from peer assistance.
An New Type Of Artificial Brain Using Controlled Neurons
Venue: arXiv cs.ET 2015
Year: 2015

Plans for a new type of artificial brain are possible because of realistic neurons in logically structured arrays of controlled toggles, one toggle per neuron. Controlled toggles can be made to compute, in parallel, parameters of critical importance for each of several complex images recalled from associative long term memory. Controlled toggles are shown below to amount to a new type of neural network that supports autonomous behavior and action.
Towards Verifiably Ethical Robot Behaviour
Venue: arXiv cs.AI 2015
Year: 2015

Ensuring that autonomous systems work ethically is both complex and difficult. However, the idea of having an additional `governor' that assesses options the system has, and prunes them to select the most ethical choices is well understood. Recent work has produced such a governor consisting of a `consequence engine' that assesses the likely future outcomes of actions then applies a Safety/Ethical logic to select actions. Although this is appealing, it is impossible to be certain that the most ethical options are actually taken. In this paper we extend and apply a well-known agent verification approach to our consequence engine, allowing us to verify the correctness of its ethical decision-making.
Caching with Unknown Popularity Profiles in Small Cell Networks
Venue: arXiv cs.IT 2015
Year: 2015

A heterogenous network is considered where the base stations (BSs), small base stations (SBSs) and users are distributed according to independent Poisson point processes (PPPs). We let the SBS nodes to posses high storage capacity and are assumed to form a distributed caching network. Popular data files are stored in the local cache of SBS, so that users can download the desired files from one of the SBS in the vicinity subject to availability. The offloading-loss is captured via a cost function that depends on a random caching strategy proposed in this paper. The cost function depends on the popularity profile, which is, in general, unknown. In this work, the popularity profile is estimated at the BS using the available instantaneous demands from the users in a time interval $[0,τ]$. This is then used to find an estimate of the cost function from which the optimal random caching strategy is devised. The main results of this work are the following: First it is shown that the waiting time $τ$ to achieve an $ε>0$ difference between the achieved and optimal costs is finite, provided the user density is greater than a predefined threshold. In this case, $τ$ is shown to scale as $N^2$, where $N$ is the support of the popularity profile. Secondly, a transfer learning-based approach is proposed to obtain an estimate of the popularity profile used to compute the empirical cost function. A condition is derived under which the proposed transfer learning-based approach performs better than the random caching strategy.
The Maximum Cut Problem in Co-bipartite Chain Graphs
Venue: arXiv cs.DS 2015
Year: 2015

A \emph{co-bipartite chain} graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cut problem (MaxCut) is NP-Hard in co-bipartite graphs. We consider MaxCut in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that MaxCut is polynomial time solvable in this graph class.
Checking Interaction-Based Declassification Policies for Android Using Symbolic Execution
Venue: arXiv cs.CR 2015
Year: 2015

Mobile apps can access a wide variety of secure information, such as contacts and location. However, current mobile platforms include only coarse access control mechanisms to protect such data. In this paper, we introduce interaction-based declassification policies, in which the user's interactions with the app constrain the release of sensitive information. Our policies are defined extensionally, so as to be independent of the app's implementation, based on sequences of security-relevant events that occur in app runs. Policies use LTL formulae to precisely specify which secret inputs, read at which times, may be released. We formalize a semantic security condition, interaction-based noninterference, to define our policies precisely. Finally, we describe a prototype tool that uses symbolic execution to check interaction-based declassification policies for Android, and we show that it enforces policies correctly on a set of apps.
Safety enhancement through situation-aware user interfaces
Venue: arXiv cs.HC 2015
Year: 2015

Due to their privileged position halfway between the physical and the cyber universes, user interfaces may play an important role in preventing, tolerating, and learning from scenarios potentially affecting mission safety and the user's quality of experience. This vision is embodied here in the main ideas and a proof-of-concepts implementation of user interfaces that combine dynamic profiling with context- and situation-awareness and autonomic software adaptation.