OpenRaiser/Intern-Atlas huggingface dataset:
An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar
Venue: arXiv cs.DC 2016
Year: 2016

DPillar has recently been proposed as a server-centric datacenter network and is combinatorially related to (but distinct from) the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network before proving that the underlying graph of DPillar is a Cayley graph; hence, the datacenter network DPillar is node-symmetric. We use this symmetry property to establish a single-path routing algorithm for DPillar that computes a shortest path and has time complexity $O(k)$, where $k$ parameterizes the dimension of DPillar (we refer to the number of ports in its switches as $n$). Our analysis also enables us to calculate the diameter of DPillar exactly. Moreover, our algorithm is trivial to implement, being essentially a conditional clause of numeric tests, and improves significantly upon a routing algorithm earlier employed for DPillar. Furthermore, we provide empirical data in order to demonstrate this improvement. In particular, we empirically show that our routing algorithm improves the average length of paths found, the aggregate bottleneck throughput, and the communication latency. A secondary, yet important, effect of our work is that it emphasises that datacenter networks are amenable to a closer combinatorial scrutiny that can significantly improve their computational efficiency and performance.
Sensing-Throughput Tradeoff for Interweave Cognitive Radio System: A Deployment-Centric Viewpoint
Venue: arXiv cs.IT 2016
Year: 2016

Secondary access to the licensed spectrum is viable only if interference is avoided at the primary system. In this regard, different paradigms have been conceptualized in the existing literature. Of these, Interweave Systems (ISs) that employ spectrum sensing have been widely investigated. Baseline models investigated in the literature characterize the performance of IS in terms of a sensing-throughput tradeoff, however, this characterization assumes the knowledge of the involved channels at the secondary transmitter, which is unavailable in practice. Motivated by this fact, we establish a novel approach that incorporates channel estimation in the system model, and consequently investigate the impact of imperfect channel estimation on the performance of the IS. More particularly, the variation induced in the detection probability affects the detector's performance at the secondary transmitter, which may result in severe interference at the primary users. In this view, we propose to employ average and outage constraints on the detection probability, in order to capture the performance of the IS. Our analysis reveals that with an appropriate choice of the estimation time determined by the proposed model, the degradation in performance of the IS can be effectively controlled, and subsequently the achievable secondary throughput can be significantly enhanced.
Weighted paths between partitions
Venue: arXiv cs.DM 2016
Year: 2016

How to quantify the distance between any two partitions of a finite set is an important issue in statistical classification, whenever different clustering results need to be compared. Developing from the traditional Hamming distance between subsets or cardinality of their symmetric difference, this work considers alternative metric distances between partitions. With one exception, all of them obtain as minimum-weight paths in the undirected graph corresponding to the Hasse diagram of the partition lattice. Firstly, by focusing on the atoms of the lattice, one well-known partition distance is recognized to be in fact the analog of the Hamming distance between subsets, with weights on edges of the Hasse diagram determined through the number of atoms in the unique maximal join-decomposition of partitions. Secondly, another partition distance known as "variation of information" is seen to correspond to a minimum-weight path with edge weights determined by the entropy of partitions. These two distances are next compared in terms of their upper and lower bounds over all pairs of partitions that are complements of one another. What emerges is that the two distances share the same minimizers and maximizers, while a much rawer behavior is observed for the partition distance which does not correspond to a minimum-weight path. The idea of measuring the distance between partitions by means of minimum-weight paths in the Hasse diagram is further explored by considering alternative symmetric and order-preserving/inverting partition functions (such as the the rank, in the simplest case) for assigning weights to edges. What matters most, in such a general setting, turns out to be whether the weighting function is supermodular or else submodular, as this makes any minimum-weight path visit the meet or else the join of the two partitions, depending on order preserving/inverting.
Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently
Venue: arXiv cs.DS 2016
Year: 2016

$\newcommand{\dist}{\operatorname{dist}}$ In this paper we define the notion of a probabilistic neighborhood in spatial data: Let a set $P$ of $n$ points in $\mathbb{R}^d$, a query point $q \in \mathbb{R}^d$, a distance metric $\dist$, and a monotonically decreasing function $f : \mathbb{R}^+ \rightarrow [0,1]$ be given. Then a point $p \in P$ belongs to the probabilistic neighborhood $N(q, f)$ of $q$ with respect to $f$ with probability $f(\dist(p,q))$. We envision applications in facility location, sensor networks, and other scenarios where a connection between two entities becomes less likely with increasing distance. A straightforward query algorithm would determine a probabilistic neighborhood in $Θ(n\cdot d)$ time by probing each point in $P$. To answer the query in sublinear time for the planar case, we augment a quadtree suitably and design a corresponding query algorithm. Our theoretical analysis shows that -- for certain distributions of planar $P$ -- our algorithm answers a query in $O((|N(q,f)| + \sqrt{n})\log n)$ time with high probability (whp). This matches up to a logarithmic factor the cost induced by quadtree-based algorithms for deterministic queries and is asymptotically faster than the straightforward approach whenever $|N(q,f)| \in o(n / \log n)$. As practical proofs of concept we use two applications, one in the Euclidean and one in the hyperbolic plane. In particular, our results yield the first generator for random hyperbolic graphs with arbitrary temperatures in subquadratic time. Moreover, our experimental data show the usefulness of our algorithm even if the point distribution is unknown or not uniform: The running time savings over the pairwise probing approach constitute at least one order of magnitude already for a modest number of points and queries.
Emulating long-term synaptic dynamics with memristive devices
Venue: arXiv cs.ET 2016
Year: 2016

The potential of memristive devices is often seeing in implementing neuromorphic architectures for achieving brain-like computation. However, the designing procedures do not allow for extended manipulation of the material, unlike CMOS technology, the properties of the memristive material should be harnessed in the context of such computation, under the view that biological synapses are memristors. Here we demonstrate that single solid-state TiO2 memristors can exhibit associative plasticity phenomena observed in biological cortical synapses, and are captured by a phenomenological plasticity model called triplet rule. This rule comprises of a spike-timing dependent plasticity regime and a classical hebbian associative regime, and is compatible with a large amount of electrophysiology data. Via a set of experiments with our artificial, memristive, synapses we show that, contrary to conventional uses of solid-state memory, the co-existence of field- and thermally-driven switching mechanisms that could render bipolar and/or unipolar programming modes is a salient feature for capturing long-term potentiation and depression synaptic dynamics. We further demonstrate that the non-linear accumulating nature of memristors promotes long-term potentiating or depressing memory transitions.
Diffusion tensor imaging with deterministic error bounds
Venue: arXiv cs.CV 2016
Year: 2016

Errors in the data and the forward operator of an inverse problem can be handily modelled using partial order in Banach lattices. We present some existing results of the theory of regularisation in this novel framework, where errors are represented as bounds by means of the appropriate partial order. We apply the theory to Diffusion Tensor Imaging, where correct noise modelling is challenging: it involves the Rician distribution and the nonlinear Stejskal-Tanner equation. Linearisation of the latter in the statistical framework would complicate the noise model even further. We avoid this using the error bounds approach, which preserves simple error structure under monotone transformations.
On the energy efficiency of client-centric data consistency management under random read/write access to Big Data with Apache HBase
Venue: arXiv cs.DC 2016
Year: 2016

The total estimated energy bill for data centers in 2010 was \$11.5 billion, and experts estimate that the energy cost of a typical data center doubles every five years. On the other hand, computational developments have started to lag behind storage advancements, therein becoming a future bottleneck for the ongoing data growth which already approaches Exascale levels. We investigate the relationship among data throughput and energy footprint on a large storage cluster, with the goal of formalizing it as a metric that reflects the trading among consistency and energy. Employing a client-centric consistency approach, and while honouring ACID properties of the chosen columnar store for the case study (Apache HBase), we present the factors involved in the energy consumption of the system as well as lessons learned to underpin further design of energy-efficient cluster scale storage systems.
Gramian-based reachability metrics for bilinear networks
Venue: arXiv cs.SY 2016
Year: 2016

This paper studies Gramian-based reachability metrics for bilinear control systems. In the context of complex networks, bilinear systems capture scenarios where an actuator not only can affect the state of a node but also interconnections among nodes. Under the assumption that the input's infinity norm is bounded by some function of the network dynamic matrices, we derive a Gramian-based lower bound on the minimum input energy required to steer the state from the origin to any reachable target state. This result motivates our study of various objects associated to the reachability Gramian to quantify the ease of controllability of the bilinear network: the minimum eigenvalue (worst-case minimum input energy to reach a state), the trace (average minimum input energy to reach a state), and its determinant (volume of the ellipsoid containing the reachable states using control inputs with no more than unit energy). We establish an increasing returns property of the reachability Gramian as a function of the actuators, which in turn allows us to derive a general lower bound on the reachability metrics in terms of the aggregate contribution of the individual actuators. We conclude by examining the effect on the worst-case minimum input energy of the addition of bilinear inputs to difficult-to-control linear symmetric networks. We show that the bilinear networks resulting from the addition of either inputs at a finite number of interconnections or at all self loops with weight vanishing with the network scale remain difficult-to-control. Various examples illustrate our results.
Modulation Classification for MIMO-OFDM Signals via Approximate Bayesian Inference
Venue: arXiv cs.IT 2016
Year: 2016

The problem of modulation classification for a multiple-antenna (MIMO) system employing orthogonal frequency division multiplexing (OFDM) is investigated under the assumption of unknown frequency-selective fading channels and signal-to-noise ratio (SNR). The classification problem is formulated as a Bayesian inference task, and solutions are proposed based on Gibbs sampling and mean field variational inference. The proposed methods rely on a selection of the prior distributions that adopts a latent Dirichlet model for the modulation type and on the Bayesian network formalism. The Gibbs sampling method converges to the optimal Bayesian solution and, using numerical results, its accuracy is seen to improve for small sample sizes when switching to the mean field variational inference technique after a number of iterations. The speed of convergence is shown to improve via annealing and random restarts. While most of the literature on modulation classification assume that the channels are flat fading, that the number of receive antennas is no less than that of transmit antennas, and that a large number of observed data symbols are available, the proposed methods perform well under more general conditions. Finally, the proposed Bayesian methods are demonstrated to improve over existing non-Bayesian approaches based on independent component analysis and on prior Bayesian methods based on the `superconstellation' method.
A Closer Look at Variance Implementations in Modern Database Systems
Venue: arXiv cs.DB 2016
Year: 2016

Variance is a popular and often necessary component of sampled aggregation queries. It is typically used as a secondary measure to ascertain statistical properties of the result such as its error. Yet, it is more expensive to compute than simple, primary measures such as \texttt{SUM}, \texttt{MEAN}, and \texttt{COUNT}. There exist numerous techniques to compute variance. While the definition of variance is considered to require multiple passes on the data, other mathematical representations can compute the value in a single pass. Some single-pass representations, however, can suffer from severe precision loss, especially for large number of data points. In this paper, we study variance implementations in various real-world systems and find that major database systems such as PostgreSQL 9.4 and most likely System X, a major commercially used closed-source database, use a representation that is efficient, but suffers from floating point precision loss resulting from catastrophic cancellation. We note deficiencies in another popular representation, used by databases such as MySQL and Impala, that suffers from not being distributive and therefore cannot take advantage of modern parallel computational resources. We review literature over the past five decades on variance calculation in both the statistics and database communities, and summarize recommendations on implementing variance functions in various settings, such as approximate query processing and large-scale distributed aggregation.
Open Access and Discovery Tools: How do Primo Libraries Manage Green Open Access Collections?
Venue: arXiv cs.DL 2016
Year: 2016

Scholarly Open Access repositories contain lots of treasures including rare or otherwise unpublished materials and articles that scholars self-archive, often as part of their institution's mandate. But it can be hard to discover this material unless users know exactly where to look. Since the very beginning, libraries have played a major role in supporting the OA movement. Next to all services they can provide to support the deposit of research output in the repositories, they can make Open Access materials widely discoverable by their patrons through general search engines (Google, Bing...), specialized search engines (like Google Scholar) and library discovery tools, thus expanding their collection to include materials that they would not necessarily pay for. In this paper, we intend to focus on two aspects regarding Open Access and Primo discovery tool. In early 2013, Ex Libris Group started to add institutional repositories to Primo Central Index (PCI), their mega-aggregation of hundreds of millions of scholarly e-resources. After 2 years, it may be interesting to take stock of the current situation of PCI regarding Open Access institutional repositories. On basis of a survey to carry out among the Primo community, the paper also shows how libraries using Primo discovery tool integrate Green Open Access contents in their catalog. Two major ways are possible for them: Firstly, they can directly harvest, index and manage any repository in their Primo and display those free contents next to the more traditional library collections; Secondly, if they are PCI subscribers, they can quickly and easily activate any, if not all, of the Open Access repositories contained PCI, making thus the contents of those directly discoverable to their end users.
Mapping Heritability of Large-Scale Brain Networks with a Billion Connections {\em via} Persistent Homology
Venue: arXiv cs.AI 2016
Year: 2016

In many human brain network studies, we do not have sufficient number (n) of images relative to the number (p) of voxels due to the prohibitively expensive cost of scanning enough subjects. Thus, brain network models usually suffer the small-n large-p problem. Such a problem is often remedied by sparse network models, which are usually solved numerically by optimizing L1-penalties. Unfortunately, due to the computational bottleneck associated with optimizing L1-penalties, it is not practical to apply such methods to construct large-scale brain networks at the voxel-level. In this paper, we propose a new scalable sparse network model using cross-correlations that bypass the computational bottleneck. Our model can build sparse brain networks at the voxel level with p > 25000. Instead of using a single sparse parameter that may not be optimal in other studies and datasets, the computational speed gain enables us to analyze the collection of networks at every possible sparse parameter in a coherent mathematical framework via persistent homology. The method is subsequently applied in determining the extent of heritability on a functional brain network at the voxel-level for the first time using twin fMRI.
SPECFACE - A Dataset of Human Faces Wearing Spectacles
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a database of human faces for persons wearing spectacles. The database consists of images of faces having significant variations with respect to illumination, head pose, skin color, facial expressions and sizes, and nature of spectacles. The database contains data of 60 subjects. This database is expected to be a precious resource for the development and evaluation of algorithms for face detection, eye detection, head tracking, eye gaze tracking, etc., for subjects wearing spectacles. As such, this can be a valuable contribution to the computer vision community.
Distributed PROMPT-LTL Synthesis
Venue: arXiv cs.LO 2016
Year: 2016

We consider the synthesis of distributed implementations for specifications in Prompt Linear Temporal Logic (PROMPT-LTL), which extends LTL by temporal operators equipped with parameters that bound their scope. For single process synthesis it is well-established that such parametric extensions do not increase worst-case complexities. For synchronous systems, we show that, despite being more powerful, the distributed realizability problem for PROMPT-LTL is not harder than its LTL counterpart. For asynchronous systems we have to consider an assume-guarantee synthesis problem, as we have to express scheduling assumptions. As asynchronous distributed synthesis is already undecidable for LTL, we give a semi-decision procedure for the PROMPT-LTL assume-guarantee synthesis problem based on bounded synthesis.
A Reliable and Cost-Efficient Auto-Scaling System for Web Applications Using Heterogeneous Spot Instances
Venue: arXiv cs.DC 2016
Year: 2016

Cloud providers sell their idle capacity on markets through an auction-like mechanism to increase their return on investment. The instances sold in this way are called spot instances. In spite that spot instances are usually 90% cheaper than on-demand instances, they can be terminated by provider when their bidding prices are lower than market prices. Thus, they are largely used to provision fault-tolerant applications only. In this paper, we explore how to utilize spot instances to provision web applications, which are usually considered availability-critical. The idea is to take advantage of differences in price among various types of spot instances to reach both high availability and significant cost saving. We first propose a fault-tolerant model for web applications provisioned by spot instances. Based on that, we devise novel auto-scaling polices for hourly billed cloud markets. We implemented the proposed model and policies both on a simulation testbed for repeatable validation and Amazon EC2. The experiments on the simulation testbed and the real platform against the benchmarks show that the proposed approach can greatly reduce resource cost and still achieve satisfactory Quality of Service (QoS) in terms of response time and availability.
On space efficiency of algorithms working on structural decompositions of graphs
Venue: arXiv cs.CC 2016
Year: 2016

Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's width. Following the work of Allender et al. [Theory of Computing, '14], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., '03], we prove that the question is closely related to a conjecture that the Longest Common Subsequence problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses XP time and FPT space. Moreover, we complete the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter tree-depth. We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth. Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non-deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth.
On a linearization technique for solving quadratic set covering problem and variations
Venue: arXiv cs.DM 2016
Year: 2016

In this paper we identify some inaccuracies in the paper by R.R. Saxena and S.R. Arora, A Linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm need not guarantee optimality, contrary to what is claimed. Experimental analysis with the algorithm has been carried out to evaluate its merit as a heuristic and compared with CPLEX. The results disclose that for some class of problems the algorithm is reasonably effective while for some other class, it's performance is very poor. we also discussion similar inaccuracies in another related paper.