OpenRaiser/Intern-Atlas huggingface dataset:
LAC: Introducing Latency-Aware Caching in Information-Centric Networks - Technical Report
Venue: arXiv cs.NI 2015
Year: 2015

Latency-minimization is recognized as one of the pillars of 5G network architecture design. Information-Centric Networking (ICN) appears a promising candidate technology for building an agile communication model that reduces latency through in-network caching. However, no proposal has developed so far latency-aware cache management mechanisms for ICN. In the paper, we investigate the role of latency awareness on data delivery performance in ICN and introduce LAC, a new simple, yet very effective, Latency-Aware Cache management policy. The designed mechanism leverages in a distributed fashion local latency observations to decide whether to store an object in a network cache. The farther the object, latency-wise, the more favorable the caching decision. By means of simulations, show that LAC outperforms state of the art proposals and results in a reduction of the content mean delivery time and standard deviation by up to 50%, along with a very fast convergence to these figures.
Software realization of the complex spectra analysis algorithm in R
Venue: arXiv cs.MS 2015
Year: 2015

Software realization of the complex spectra decomposition on unknown number of similarcomponents is proposed.The algorithm is based on non-linear minimizing the sum of squared residuals of the spectrum model. For the adequacy checking the complex of criteria is used.It tests the model residuals correspondence with the normal distribution, equality to zero of their mean value and autocorrelation. Also the closeness of residuals and experimental data variances is checked.
Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables
Venue: arXiv cs.DS 2015
Year: 2015

A \itbf{cover} of a string $x = x[1..n]$ is a proper substring $u$ of $x$ such that $x$ can be constructed from possibly overlapping instances of $u$. A recent paper \cite{FIKPPST13} relaxes this definition --- an \itbf{enhanced cover} $u$ of $x$ is a border of $x$ (that is, a proper prefix that is also a suffix) that covers a {\it maximum} number of positions in $x$ (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbf{border array} $β[1..n]$, where $β[i]$ is the length of the longest border of $x[1..i]$, $1 \le i \le n$. In this paper, we first show how to compute enhanced covers using instead the \itbf{prefix table}: an array $π[1..n]$ such that $π[i]$ is the length of the longest substring of $x$ beginning at position $i$ that matches a prefix of $x$. Unlike the border array, the prefix table is robust: its properties hold also for \itbf{indeterminate strings} --- that is, strings defined on {\it subsets} of the alphabet $Σ$ rather than individual elements of $Σ$. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \cite{FIKPPST13}, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string $x$ is approximately 1.64 for binary alphabets, less for larger ones.
On the Optimal Space Complexity of Consensus for Anonymous Processes
Venue: arXiv cs.DC 2015
Year: 2015

The optimal space complexity of consensus in shared memory is a decades-old open problem. For a system of $n$ processes, no algorithm is known that uses a sublinear number of registers. However, the best known lower bound due to Fich, Herlihy, and Shavit requires $Ω(\sqrt{n})$ registers. The special symmetric case of the problem where processes are anonymous (run the same algorithm) has also attracted attention. Even in this case, the best lower and upper bounds are still $Ω(\sqrt{n})$ and $O(n)$. Moreover, Fich, Herlihy, and Shavit first proved their lower bound for anonymous processes, and then extended it to the general case. As such, resolving the anonymous case might be a significant step towards understanding and solving the general problem. In this work, we show that in a system of anonymous processes, any consensus algorithm satisfying nondeterministic solo termination has to use $Ω(n)$ read-write registers in some execution. This implies an $Ω(n)$ lower bound on the space complexity of deterministic obstruction-free and randomized wait-free consensus, matching the upper bound and closing the symmetric case of the open problem.
Modeling and Correspondence of Topologically Complex 3D Shapes
Venue: arXiv cs.GR 2015
Year: 2015

3D shape creation and modeling remains a challenging task especially for novice users. Many methods in the field of computer graphics have been proposed to automate the often repetitive and precise operations needed during the modeling of detailed shapes. This report surveys different approaches of shape modeling and correspondence especially for shapes exhibiting topological complexity. We focus on methods designed to help generate or process shapes with large number of interconnected components often found in man-made shapes. We first discuss a variety of modeling techniques, that leverage existing shapes, in easy to use creative modeling systems. We then discuss possible correspondence strategies for topologically different shapes as it is a requirement for such systems. Finally, we look at different shape representations and tools that facilitate the modification of shape topology and we focus on those particularly useful in free-form 3D modeling.
Justification logic enjoys the strong finite model property
Venue: arXiv cs.LO 2015
Year: 2015

We observe that justification logic enjoys a form the strong finite model property (sometimes also called small model property). Thus we obtain decidability proofs for justification logic that do not rely on Post's theorem.
Strategic Classification
Venue: arXiv cs.LG 2015
Year: 2015

Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior---often referred to as gaming---the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming. We model classification as a sequential game between a player named "Jury" and a player named "Contestant." Jury designs a classifier, and Contestant receives an input to the classifier, which he may change at some cost. Jury's goal is to achieve high classification accuracy with respect to Contestant's original input and some underlying target classification function. Contestant's goal is to achieve a favorable classification outcome while taking into account the cost of achieving it. For a natural class of cost functions, we obtain computationally efficient learning algorithms which are near-optimal. Surprisingly, our algorithms are efficient even on concept classes that are computationally hard to learn. For general cost functions, designing an approximately optimal strategy-proof classifier, for inverse-polynomial approximation, is NP-hard.
Linear Algorithms for Computing the Lyndon Border Array and the Lyndon Suffix Array
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of finding repetitive structures and inherent patterns in a given string $\s{s}$ of length $n$ over a finite totally ordered alphabet. A border $\s{u}$ of a string $\s{s}$ is both a prefix and a suffix of $\s{s}$ such that $\s{u} \not= \s{s}$. The computation of the border array of a string $\s{s}$, namely the borders of each prefix of $\s{s}$, is strongly related to the string matching problem: given a string $\s{w}$, find all of its occurrences in $\s{s}$. A {\itshape Lyndon word} is a primitive word (i.e., it is not a power of another word) which is minimal for the lexicographical order of its conjugacy class (i.e., the set of words obtained by cyclic rotations of the letters). In this paper we combine these concepts to introduce the \emph{Lyndon Border Array} $\mathcal L β$ of $\s{s}$, whose $i$-th entry $\mathcal L β(\s{s})[i]$ is the length of the longest border of $\s{s}[1 \dd i]$ which is also a Lyndon word. We propose linear-time and linear-space algorithms for computing $\mathcal L β(\s{s})$. %in the case of both binary and bounded alphabets. Further, we introduce the \emph{Lyndon Suffix Array}, and by modifying the efficient suffix array technique of Ko and Aluru \cite{KA03} outline a linear time and space algorithm for its construction.
Weighted Automata and Logics for Infinite Nested Words
Venue: arXiv cs.FL 2015
Year: 2015

Nested words introduced by Alur and Madhusudan are used to capture structures with both linear and hierarchical order, e.g. XML documents, without losing valuable closure properties. Furthermore, Alur and Madhusudan introduced automata and equivalent logics for both finite and infinite nested words, thus extending Büchi's theorem to nested words. Recently, average and discounted computations of weights in quantitative systems found much interest. Here, we will introduce and investigate weighted automata models and weighted MSO logics for infinite nested words. As weight structures we consider valuation monoids which incorporate average and discounted computations of weights as well as the classical semirings. We show that under suitable assumptions, two resp. three fragments of our weighted logics can be transformed into each other. Moreover, we show that the logic fragments have the same expressive power as weighted nested word automata.
Improving Fiber Alignment in HARDI by Combining Contextual PDE Flow with Constrained Spherical Deconvolution
Venue: arXiv cs.CV 2015
Year: 2015

We propose two strategies to improve the quality of tractography results computed from diffusion weighted magnetic resonance imaging (DW-MRI) data. Both methods are based on the same PDE framework, defined in the coupled space of positions and orientations, associated with a stochastic process describing the enhancement of elongated structures while preserving crossing structures. In the first method we use the enhancement PDE for contextual regularization of a fiber orientation distribution (FOD) that is obtained on individual voxels from high angular resolution diffusion imaging (HARDI) data via constrained spherical deconvolution (CSD). Thereby we improve the FOD as input for subsequent tractography. Secondly, we introduce the fiber to bundle coherence (FBC), a measure for quantification of fiber alignment. The FBC is computed from a tractography result using the same PDE framework and provides a criterion for removing the spurious fibers. We validate the proposed combination of CSD and enhancement on phantom data and on human data, acquired with different scanning protocols. On the phantom data we find that PDE enhancements improve both local metrics and global metrics of tractography results, compared to CSD without enhancements. On the human data we show that the enhancements allow for a better reconstruction of crossing fiber bundles and they reduce the variability of the tractography output with respect to the acquisition parameters. Finally, we show that both the enhancement of the FODs and the use of the FBC measure on the tractography improve the stability with respect to different stochastic realizations of probabilistic tractography. This is shown in a clinical application: the reconstruction of the optic radiation for epilepsy surgery planning.
From Random Matrix Theory to Coding Theory: Volume of a Metric Ball in Unitary Group
Venue: arXiv cs.IT 2015
Year: 2015

Volume estimates of metric balls in manifolds find diverse applications in information and coding theory. In this paper, some new results for the volume of a metric ball in unitary group are derived via various tools from random matrix theory. The first result is an integral representation of the exact volume, which involves a Toeplitz determinant of Bessel functions. The connection to matrix-variate hypergeometric functions and Szegő's strong limit theorem lead independently from the finite size formula to an asymptotic one. The convergence of the limiting formula is exceptionally fast due to an underlying mock-Gaussian behavior. The proposed volume estimate enables simple but accurate analytical evaluation of coding-theoretic bounds of unitary codes. In particular, the Gilbert-Varshamov lower bound and the Hamming upper bound on cardinality as well as the resulting bounds on code rate and minimum distance are derived. Moreover, bounds on the scaling law of code rate are found. Lastly, a closed-form bound on diversity sum relevant to unitary space-time codes is obtained, which was only computed numerically in literature.
Sonification of guidance data during road crossing for people with visual impairments or blindness
Venue: arXiv cs.HC 2015
Year: 2015

In the last years several solutions were proposed to support people with visual impairments or blindness during road crossing. These solutions focus on computer vision techniques for recognizing pedestrian crosswalks and computing their relative position from the user. Instead, this contribution addresses a different problem; the design of an auditory interface that can effectively guide the user during road crossing. Two original auditory guiding modes based on data sonification are presented and compared with a guiding mode based on speech messages. Experimental evaluation shows that there is no guiding mode that is best suited for all test subjects. The average time to align and cross is not significantly different among the three guiding modes, and test subjects distribute their preferences for the best guiding mode almost uniformly among the three solutions. From the experiments it also emerges that higher effort is necessary for decoding the sonified instructions if compared to the speech instructions, and that test subjects require frequent `hints' (in the form of speech messages). Despite this, more than 2/3 of test subjects prefer one of the two guiding modes based on sonification. There are two main reasons for this: firstly, with speech messages it is harder to hear the sound of the environment, and secondly sonified messages convey information about the "quantity" of the expected movement.
Orienting edges to fight fire in graphs
Venue: arXiv cs.DM 2015
Year: 2015

We investigate a new oriented variant of the Firefighter Problem. In the traditional Firefighter Problem, a fire breaks out at a given vertex of a graph, and at each time interval spreads to neighbouring vertices that have not been protected, while a constant number of vertices are protected at each time interval. In the version of the problem considered here, the firefighters are able to orient the edges of the graph before the fire breaks out, but the fire could start at any vertex. We consider this problem when played on a graph in one of several graph classes, and give upper and lower bounds on the number of vertices that can be saved. In particular, when one firefighter is available at each time interval, and the given graph is a complete graph, or a complete bipartite graph, we present firefighting strategies that are provably optimal. We also provide lower bounds on the number of vertices that can be saved as a function of the chromatic number, of the maximum degree, and of the treewidth of a graph. For a subcubic graph, we show that the firefighters can save all but two vertices, and this is best possible.
Energy-Efficient 5G Outdoor-to-Indoor Communication: SUDAS Over Licensed and Unlicensed Spectrum
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the joint resource allocation algorithm design for downlink and uplink multicarrier transmission assisted by a shared user equipment (UE)-side distributed antenna system (SUDAS). The proposed SUDAS simultaneously utilizes licensed frequency bands and unlicensed frequency bands, (e.g. millimeter wave bands), to enable a spatial multiplexing gain for single-antenna UEs to improve energy efficiency and system throughput of $5$-th generation (5G) outdoor-to-indoor communication. The design of the UE selection, the time allocation to uplink and downlink, and the transceiver processing matrix is formulated as a non-convex optimization problem for the maximization of the end-to-end system energy efficiency (bits/Joule). The proposed problem formulation takes into account minimum data rate requirements for delay sensitive UEs and the circuit power consumption of all transceivers. In order to design a tractable resource allocation algorithm, we first show that the optimal transmitter precoding and receiver post-processing matrices jointly diagonalize the end-to-end communication channel for both downlink and uplink communication via SUDAS. Subsequently, the matrix optimization problem is converted to an equivalent scalar optimization problem for multiple parallel channels, which is solved by an asymptotically globally optimal iterative algorithm. Besides, we propose a suboptimal algorithm which finds a locally optimal solution of the non-convex optimization problem. Simulation results illustrate that the proposed resource allocation algorithms for SUDAS achieve a significant performance gain in terms of system energy efficiency and spectral efficiency compared to conventional baseline systems by offering multiple parallel data streams for single-antenna UEs.
Chaining fragments in sequences: to sweep or not
Venue: arXiv cs.DS 2015
Year: 2015

Computing an optimal chain of fragments is a classical problem in string algorithms, with important applications in computational biology. There exist two efficient dynamic programming algorithms solving this problem, based on different principles. In the present note, we show how it is possible to combine the principles of two of these algorithms in order to design a hybrid dynamic programming algorithm that combines the advantages of both algorithms.
Two Power Series Models of Self-Similarity in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Two power series models are proposed to represent self-similarity and they are compared to the Zipf and Benford distributions. Since evolution of a social network is associated with replicating self-similarity at many levels, the nature of interconnections can serve as a measure of the optimality of its organization. In contrast with the Zipf distribution where the middle term is the harmonic mean of the adjoining terms, our distribution considers the middle term to be the geometric mean. In one of the power series models, the scaling factor at one level is shown to be the golden ratio. A model for evolution of networks by oscillations between two different self-similarity measures is described.
Benchmarking Machine Learning Technologies for Software Defect Detection
Venue: arXiv cs.SE 2015
Year: 2015

Machine Learning approaches are good in solving problems that have less information. In most cases, the software domain problems characterize as a process of learning that depend on the various circumstances and changes accordingly. A predictive model is constructed by using machine learning approaches and classified them into defective and non-defective modules. Machine learning techniques help developers to retrieve useful information after the classification and enable them to analyse data from different perspectives. Machine learning techniques are proven to be useful in terms of software bug prediction. This study used public available data sets of software modules and provides comparative performance analysis of different machine learning techniques for software bug prediction. Results showed most of the machine learning methods performed well on software bug datasets.
Performance Characterization of In-Memory Data Analytics on a Modern Cloud Server
Venue: arXiv cs.DC 2015
Year: 2015

In last decade, data analytics have rapidly progressed from traditional disk-based processing to modern in-memory processing. However, little effort has been devoted at enhancing performance at micro-architecture level. This paper characterizes the performance of in-memory data analytics using Apache Spark framework. We use a single node NUMA machine and identify the bottlenecks hampering the scalability of workloads. We also quantify the inefficiencies at micro-architecture level for various data analysis workloads. Through empirical evaluation, we show that spark workloads do not scale linearly beyond twelve threads, due to work time inflation and thread level load imbalance. Further, at the micro-architecture level, we observe memory bound latency to be the major cause of work time inflation.
ADsafety: Type-Based Verification of JavaScript Sandboxing
Venue: arXiv cs.PL 2015
Year: 2015

Web sites routinely incorporate JavaScript programs from several sources into a single page. These sources must be protected from one another, which requires robust sandboxing. The many entry-points of sandboxes and the subtleties of JavaScript demand robust verification of the actual sandbox source. We use a novel type system for JavaScript to encode and verify sandboxing properties. The resulting verifier is lightweight and efficient, and operates on actual source. We demonstrate the effectiveness of our technique by applying it to ADsafe, which revealed several bugs and other weaknesses.
Programming Flows in Dense Mobile Environments: A Multi-user Diversity Perspective
Venue: arXiv cs.NI 2015
Year: 2015

The emergence of OpenFlow and Software Defined Networks brings new perspectives into how we design the next generation networks, where the number of base stations/access points as well as the devices per subscriber will be dramatically higher. In such dense environments, devices can communicate with each other directly and can attach to multiple base stations (or access points) for simultaneous data communication over multiple paths. This paper explores how networks can maximally enable this multi-path diversity through network programmability. In particular, we propose programmable flow clustering and set policies for inter-group as well as intra-group wireless scheduling. Further, we propose programmable demultiplexing of a single network flow onto multiple paths before the congestion areas and multiplexing them together post congestion areas. We show the benefits of such programmability first for legacy applications that cannot take advantage of multi-homing without such programmability. We then evaluate the benefits for smart applications that take advantage of multi-homing by either opening multiple TCP connections over multiple paths or utilizing a transport protocol such as MP-TCP designed for supporting such environments. More specifically, we built an emulation environment over Mininet for our experiments. Our evaluations using synthetic and trace driven channel models indicate that the proposed programmability in wireless scheduling and flow splitting can increase the throughput substantially for both the legacy applications and the current state of the art.