OpenRaiser/Intern-Atlas huggingface dataset:
Caching Placement in Stochastic Wireless Caching Helper Networks: Channel Selection Diversity via Caching
Venue: arXiv cs.IT 2016
Year: 2016

Content delivery success in wireless caching helper networks depends mainly on cache-based channel selection diversity and network interference. For given channel fading and network geometry, both channel selection diversity and network interference dynamically vary according to what and how the caching helpers cache at their finite storage space. We study probabilistic content placement (or caching placement) to desirably control cache-based channel selection diversity and network interference in a stochastic wireless caching helper network, with sophisticated considerations of wireless fading channels, interactions among multiple users such as interference and loads at caching helpers, and arbitrary memory size. Using stochastic geometry, we derive optimal caching probabilities in closed form to maximize the average success probability of content delivery and propose an efficient algorithm to find the solution in a noise-limited network. In an interference-limited network, based on a lower bound of the average success probability of content delivery, we find near-optimal caching probabilities in closed form to control the channel selection diversity and the network interference. We numerically verify that the proposed content placement is superior to other comparable content placement strategies.
Self-Paced Learning: an Implicit Regularization Perspective
Venue: arXiv cs.LG 2016
Year: 2016

Self-paced learning (SPL) mimics the cognitive mechanism of humans and animals that gradually learns from easy to hard samples. One key issue in SPL is to obtain better weighting strategy that is determined by minimizer function. Existing methods usually pursue this by artificially designing the explicit form of SPL regularizer. In this paper, we focus on the minimizer function, and study a group of new regularizer, named self-paced implicit regularizer that is deduced from robust loss function. Based on the convex conjugacy theory, the minimizer function for self-paced implicit regularizer can be directly learned from the latent loss function, while the analytic form of the regularizer can be even known. A general framework (named SPL-IR) for SPL is developed accordingly. We demonstrate that the learning procedure of SPL-IR is associated with latent robust loss functions, thus can provide some theoretical inspirations for its working mechanism. We further analyze the relation between SPL-IR and half-quadratic optimization. Finally, we implement SPL-IR to both supervised and unsupervised tasks, and experimental results corroborate our ideas and demonstrate the correctness and effectiveness of implicit regularizers.
Recovering Architectural Variability of a Family of Product Variants
Venue: arXiv cs.SE 2016
Year: 2016

A Software Product Line (SPL) aims at applying a pre-planned systematic reuse of large-grained software artifacts to increase the software productivity and reduce the development cost. The idea of SPL is to analyze the business domain of a family of products to identify the common and the variable parts between the products. However, it is common for companies to develop, in an ad-hoc manner (e.g. clone and own), a set of products that share common functionalities and differ in terms of others. Thus, many recent research contributions are proposed to re-engineer existing product variants to a SPL. Nevertheless, these contributions are mostly focused on managing the variability at the requirement level. Very few contributions address the variability at the architectural level despite its major importance. Starting from this observation, we propose, in this paper, an approach to reverse engineer the architecture of a set of product variants. Our goal is to identify the variability and dependencies among architectural-element variants at the architectural level. Our work relies on Formal Concept Analysis (FCA) to analyze the variability. To validate the proposed approach, we experimented on two families of open-source product variants; Mobile Media and Health Watcher. The results show that our approach is able to identify the architectural variability and the dependencies.
An Alternating Qubit Protocol and Its Correctness Checking
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, a quantum version of classical alternating bit protocol is proposed. This protocol provides a reliable method to transmit the secret quantum data via a noisy quantum channel while the entanglement between particles is not broken. Our protocol is based on quantum teleportation and superdense coding. By assuming that the participants can distinguish the alternating qubit from other messages and also the assumption that data can be resent unlimited times, an abstraction of this protocol can be derived. Using the quantum process algebra \textit{full} $qACP$, we show that the proposed protocol is correct, so the desired external behaviour of the protocol is guaranteed.
OWL: a Reliable Online Watcher for LTE Control Channel Measurements
Venue: arXiv cs.NI 2016
Year: 2016

Reliable network measurements are a fundamental component of networking research as they enable network analysis, system debugging, performance evaluation and optimization. In particular, decoding the LTE control channel would give access to the full base station traffic at a 1 ms granularity, thus allowing for traffic profiling and accurate measurements. Although a few open-source implementations of LTE are available, they do not provide tools to reliably decoding the LTE control channel and, thus, accessing the scheduling information. In this paper, we present OWL, an Online Watcher for LTE that is able to decode all the resource blocks in more than 99% of the system frames, significantly outperforming existing non-commercial prior decoders. Compared to previous attempts, OWL grounds the decoding procedure on information obtained from the LTE random access mechanism. This makes it possible to run our software on inexpensive hardware coupled with almost any software defined radio capable of sampling the LTE signal with sufficient accuracy.
PGMPI: Automatically Verifying Self-Consistent MPI Performance Guidelines
Venue: arXiv cs.DC 2016
Year: 2016

The Message Passing Interface (MPI) is the most commonly used application programming interface for process communication on current large-scale parallel systems. Due to the scale and complexity of modern parallel architectures, it is becoming increasingly difficult to optimize MPI libraries, as many factors can influence the communication performance. To assist MPI developers and users, we propose an automatic way to check whether MPI libraries respect self-consistent performance guidelines for collective communication operations. We introduce the PGMPI framework to detect violations of performance guidelines through benchmarking. Our experimental results show that PGMPI can pinpoint undesired and often unexpected performance degradations of collective MPI operations. We demonstrate how to overcome performance issues of several libraries by adapting the algorithmic implementations of their respective collective MPI calls.
Two-Way Visibly Pushdown Automata and Transducers
Venue: arXiv cs.FL 2016
Year: 2016

Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a finite number of registers. Nested words are words with a nesting structure, allowing to model unranked trees as their depth-first-search linearisations. In this paper, we consider transformations from nested words to words, allowing in particular to produce unranked trees if output words have a nesting structure. The model of visibly pushdown transducers allows to describe such transformations, and we propose a simple deterministic extension of this model with two-way moves that has the following properties: i) it is a simple computational model, that naturally has a good evaluation complexity; ii) it is expressive: it subsumes nested word-to-word MSO transducers, and the exact expressiveness of MSO transducers is recovered using a simple syntactic restriction; iii) it has good algorithmic/closure properties: the model is closed under composition with a unambiguous one-way letter-to-letter transducer which gives closure under regular look-around, and has a decidable equivalence problem.
Relational type-checking for MELL proof-structures. Part 1: Multiplicatives
Venue: arXiv cs.LO 2016
Year: 2016

Relational semantics for linear logic is a form of non-idempotent intersection type system, from which several informations on the execution of a proof-structure can be recovered. An element of the relational interpretation of a proof-structure R with conclusion $Γ$ acts thus as a type (refining $Γ$) having R as an inhabitant. We are interested in the following type-checking question: given a proof-structure R, a list of formulae $Γ$, and a point x in the relational interpretation of $Γ$, is x in the interpretation of R? This question is decidable. We present here an algorithm that decides it in time linear in the size of R, if R is a proof-structure in the multiplicative fragment of linear logic. This algorithm can be extended to larger fragments of multiplicative-exponential linear logic containing $λ$-calculus.
A Review of Star Schema Benchmark
Venue: arXiv cs.DB 2016
Year: 2016

This paper examines the Star Schema Benchmark, an alternative to the flawed TPC-H decision support system and presents reasons why this benchmark should be adopted over the industry standard for decision support systems.
Deeper Depth Prediction with Fully Convolutional Residual Networks
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the problem of estimating the depth map of a scene given a single RGB image. We propose a fully convolutional architecture, encompassing residual learning, to model the ambiguous mapping between monocular images and depth maps. In order to improve the output resolution, we present a novel way to efficiently learn feature map up-sampling within the network. For optimization, we introduce the reverse Huber loss that is particularly suited for the task at hand and driven by the value distributions commonly present in depth maps. Our model is composed of a single architecture that is trained end-to-end and does not rely on post-processing techniques, such as CRFs or other additional refinement steps. As a result, it runs in real-time on images or videos. In the evaluation, we show that the proposed model contains fewer parameters and requires fewer training data than the current state of the art, while outperforming all approaches on depth estimation. Code and models are publicly available.
DINAMITE: A modern approach to memory performance profiling
Venue: arXiv cs.PF 2016
Year: 2016

Diagnosing and fixing performance problems on multicore machines with deep memory hierarchies is extremely challenging. Certain problems are best addressed when we can analyze the entire trace of program execution, e.g., every memory access. Unfortunately such detailed execution logs are very large and cannot be analyzed by direct inspection. We present DINAMITE: a toolkit for Dynamic INstrumentation and Analysis for MassIve Trace Exploration. DINAMITE is a collection of tools for end-to-end performance analysis: from the LLVM compiler pass that instruments the program to plug-and-play tools that use a modern data analytics engine Spark Streaming for trace introspection. Using DINAMITE we found opportunities to improve data layout in several applications that resulted in 15-20% performance improvements and found a shared-variable bottleneck in a popular key-value store, whose elimination improved performance by 20x.
Preliminary Results Towards Contract Monitorability
Venue: arXiv cs.LO 2016
Year: 2016

This paper discusses preliminary investigations on the monitorability of contracts for web service descriptions. There are settings where servers do not guarantee statically whether they satisfy some specified contract, which forces the client (i.e., the entity interacting with the server) to perform dynamic checks. This scenario may be viewed as an instance of Runtime Verification, where a pertinent question is whether contracts can be monitored for adequately at runtime, otherwise stated as the monitorability of contracts. We consider a simple language of finitary contracts describing both clients and servers, and develop a formal framework that describes server contract monitoring. We define monitor properties that potentially contribute towards a comprehensive notion of contract monitorability and show that our simple contract language satisfies these properties.
Development of Krylov and AMG linear solvers for large-scale sparse matrices on GPUs
Venue: arXiv cs.MS 2016
Year: 2016

This research introduce our work on developing Krylov subspace and AMG solvers on NVIDIA GPUs. As SpMV is a crucial part for these iterative methods, SpMV algorithms for single GPU and multiple GPUs are implemented. A HEC matrix format and a communication mechanism are established. And also, a set of specific algorithms for solving preconditioned systems in parallel environments are designed, including ILU(k), RAS and parallel triangular solvers. Based on these work, several Krylov solvers and AMG solvers are developed. According to numerical experiments, favorable acceleration performance is acquired from our Krylov solver and AMG solver under various parameter conditions.
On the performance of different mutation operators of a subpopulation-based genetic algorithm for multi-robot task allocation problems
Venue: arXiv cs.NE 2016
Year: 2016

The performance of different mutation operators is usually evaluated in conjunc-tion with specific parameter settings of genetic algorithms and target problems. Most studies focus on the classical genetic algorithm with different parameters or on solving unconstrained combinatorial optimization problems such as the traveling salesman problems. In this paper, a subpopulation-based genetic al-gorithm that uses only mutation and selection is developed to solve multi-robot task allocation problems. The target problems are constrained combinatorial optimization problems, and are more complex if cooperative tasks are involved as these introduce additional spatial and temporal constraints. The proposed genetic algorithm can obtain better solutions than classical genetic algorithms with tournament selection and partially mapped crossover. The performance of different mutation operators in solving problems without/with cooperative tasks is evaluated. The results imply that inversion mutation performs better than others when solving problems without cooperative tasks, and the swap-inversion combination performs better than others when solving problems with cooperative tasks.
Storytelling of Photo Stream with Bidirectional Multi-thread Recurrent Neural Network
Venue: arXiv cs.CV 2016
Year: 2016

Visual storytelling aims to generate human-level narrative language (i.e., a natural paragraph with multiple sentences) from a photo streams. A typical photo story consists of a global timeline with multi-thread local storylines, where each storyline occurs in one different scene. Such complex structure leads to large content gaps at scene transitions between consecutive photos. Most existing image/video captioning methods can only achieve limited performance, because the units in traditional recurrent neural networks (RNN) tend to "forget" the previous state when the visual sequence is inconsistent. In this paper, we propose a novel visual storytelling approach with Bidirectional Multi-thread Recurrent Neural Network (BMRNN). First, based on the mined local storylines, a skip gated recurrent unit (sGRU) with delay control is proposed to maintain longer range visual information. Second, by using sGRU as basic units, the BMRNN is trained to align the local storylines into the global sequential timeline. Third, a new training scheme with a storyline-constrained objective function is proposed by jointly considering both global and local matches. Experiments on three standard storytelling datasets show that the BMRNN model outperforms the state-of-the-art methods.
Measure of Node Similarity in Multilayer Networks
Venue: arXiv cs.SI 2016
Year: 2016

The weight of links in a network is often related to the similarity of the nodes. Here, we introduce a simple tunable measure for analysing the similarity of nodes across different link weights. In particular, we use the measure to analyze homophily in a group of 659 freshman students at a large university. Our analysis is based on data obtained using smartphones equipped with custom data collection software, complemented by questionnaire-based data. The network of social contacts is represented as a weighted multilayer network constructed from different channels of telecommunication as well as data on face-to-face contacts. We find that even strongly connected individuals are not more similar with respect to basic personality traits than randomly chosen pairs of individuals. In contrast, several socio-demographics variables have a significant degree of similarity. We further observe that similarity might be present in one layer of the multilayer network and simultaneously be absent in the other layers. For a variable such as gender, our measure reveals a transition from similarity between nodes connected with links of relatively low weight to dis-similarity for the nodes connected by the strongest links. We finally analyze the overlap between layers in the network for different levels of acquaintanceships.
Biased Contribution Index: A Simpler Mechanism to Maintain Fairness in Peer to Peer Network
Venue: arXiv cs.NI 2016
Year: 2016

To maintain fairness, in the terms of resources shared by an individual peer, a proper incentive policy is required in a peer to peer network. This letter proposes, a simpler mechanism to rank the peers based on their resource contributions to the network. This mechanism will suppress the free riders from downloading the resources from the network. Contributions of the peers are biased in such a way that it can balance the download and upload amount of resources at each peer. This mechanism can be implemented in a distributed system and it converges much faster than the other existing approaches.
A Crowd Monitoring Framework using Emotion Analysis of Social Media for Emergency Management in Mass Gatherings
Venue: arXiv cs.CY 2016
Year: 2016

In emergency management for mass gathering, the knowledge about crowd types can highly assist with providing timely response and effective resource allocation. Crowd monitoring can be achieved using computer vision based approaches and sensory data analysis. The emergence of social media platforms presents an opportunity to capture valuable information about how people feel and think. However, reviewing current works shows that there are a limited number of studies that use social media in crowd monitoring and/or incorporate a unified crowd model for consistency and interoperability. This presents a novel framework for crowd monitoring using social media. It includes a standard crowd model to represent different types of crowds. The proposed framework considers the effect of emotion on crowd behaviour and uses the emotion analysis of social media to identify the crowd types in an event. An experiment using historical data of a past event to validate our framework and model is described.
Social learning strategies modify the effect of network structure on group performance
Venue: arXiv cs.SI 2016
Year: 2016

The structure of communication networks is an important determinant of the capacity of teams, organizations and societies to solve policy, business and science problems. Yet, previous studies reached contradictory results about the relationship between network structure and performance, finding support for the superiority of both well-connected efficient and poorly connected inefficient network structures. Here we argue that understanding how communication networks affect group performance requires taking into consideration the social learning strategies of individual team members. We show that efficient networks outperform inefficient networks when individuals rely on conformity by copying the most frequent solution among their contacts. However, inefficient networks are superior when individuals follow the best member by copying the group member with the highest payoff. In addition, groups relying on conformity based on a small sample of others excel at complex tasks, while groups following the best member achieve greatest performance for simple tasks. Our findings reconcile contradictory results in the literature and have broad implications for the study of social learning across disciplines.
Performance Prediction of Nonbinary Forward Error Correction in Optical Transmission Experiments
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we compare different metrics to predict the error rate of optical systems based on nonbinary forward error correction (FEC). It is shown that the correct metric to predict the performance of coded modulation based on nonbinary FEC is the mutual information. The accuracy of the prediction is verified in a detailed example with multiple constellation formats, FEC overheads in both simulations and optical transmission experiments over a recirculating loop. It is shown that the employed FEC codes must be universal if performance prediction based on thresholds is used. A tutorial introduction into the computation of the threshold from optical transmission measurements is also given.
Locality-Aware Laplacian Mesh Smoothing
Venue: arXiv cs.NA 2016
Year: 2016

In this paper, we propose a novel reordering scheme to improve the performance of a Laplacian Mesh Smoothing (LMS). While the Laplacian smoothing algorithm is well optimized and studied, we show how a simple reordering of the vertices of the mesh can greatly improve the execution time of the smoothing algorithm. The idea of our reordering is based on (i) the postulate that cache misses are a very time consuming part of the execution of LMS, and (ii) the study of the reuse distance patterns of various executions of the LMS algorithm. Our reordering algorithm is very simple but allows for huge performance improvement. We ran it on a Westmere-EX platform and obtained a speedup of 75 on 32 cores compared to the single core execution without reordering, and a gain in execution of 32% on 32 cores compared to state of the art reordering. Finally, we show that we leave little room for a better ordering by reducing the L2 and L3 cache misses to a bare minimum.
Some Results on Reversible Gate Classes Over Non-Binary Alphabets
Venue: arXiv cs.ET 2016
Year: 2016

We present a collection of results concerning the structure of reversible gate classes over non-binary alphabets, including (1) a reversible gate class over non-binary alphabets that is not finitely generated (2) an explicit set of generators for the class of all gates, the class of all conservative gates, and a class of generalizations of the two (3) an embedding of the poset of reversible gate classes over an alphabet of size $k$ into that of an alphabet of size $k+1$ (4) a classification of gate classes containing the class of $(k-1,1)$-conservative gates, meaning gates that preserve the number of occurrences of a certain element in the alphabet.