OpenRaiser/Intern-Atlas huggingface dataset:
Building Bridges into the Unknown: Personalizing Connections to Little-known Countries
Venue: arXiv cs.SI 2015
Year: 2015

How are you related to Malawi? Do recent events on the Comoros effect you in any subtle way? Who in your extended social network is in Croatia? We seldom ask ourselves these questions, yet a "long tail" of content beyond our everyday knowledge is waiting to be explored. In this work we propose a recommendation task of creating interest in little-known content by building personalized "bridges" to users. We consider an example task of interesting users in little-known countries, and propose a system which aggregates a user's Twitter profile, network, and tweets to create an interest model, which is then matched to a library of knowledge about the countries. We perform a user study of 69 participants and conduct 11 in-depth interviews in order to evaluate the efficacy of the proposed approach and gather qualitative insight into the effect of multi-faceted use of Twitter on the perception of the bridges. We find the increase in interest concerning little-known content to greatly depend on the pre-existing disposition to it. Additionally, we discover a set of vital properties good bridges must possess, including recency, novelty, emotiveness, and a proper selection of language. Using the proposed approach we aim to harvest the "invisible connections" to make explicit the idea of a "small world" where even a faraway country is more closely connected to you than you might have imagined.
Do Read Errors Matter for Genome Assembly?
Venue: arXiv cs.IT 2015
Year: 2015

While most current high-throughput DNA sequencing technologies generate short reads with low error rates, emerging sequencing technologies generate long reads with high error rates. A basic question of interest is the tradeoff between read length and error rate in terms of the information needed for the perfect assembly of the genome. Using an adversarial erasure error model, we make progress on this problem by establishing a critical read length, as a function of the genome and the error rate, above which perfect assembly is guaranteed. For several real genomes, including those from the GAGE dataset, we verify that this critical read length is not significantly greater than the read length required for perfect assembly from reads without errors.
Robust Subjective Visual Property Prediction from Crowdsourced Pairwise Labels
Venue: arXiv cs.CV 2015
Year: 2015

The problem of estimating subjective visual properties from image and video has attracted increasing interest. A subjective visual property is useful either on its own (e.g. image and video interestingness) or as an intermediate representation for visual recognition (e.g. a relative attribute). Due to its ambiguous nature, annotating the value of a subjective visual property for learning a prediction model is challenging. To make the annotation more reliable, recent studies employ crowdsourcing tools to collect pairwise comparison labels because human annotators are much better at ranking two images/videos (e.g. which one is more interesting) than giving an absolute value to each of them separately. However, using crowdsourced data also introduces outliers. Existing methods rely on majority voting to prune the annotation outliers/errors. They thus require large amount of pairwise labels to be collected. More importantly as a local outlier detection method, majority voting is ineffective in identifying outliers that can cause global ranking inconsistencies. In this paper, we propose a more principled way to identify annotation outliers by formulating the subjective visual property prediction task as a unified robust learning to rank problem, tackling both the outlier detection and learning to rank jointly. Differing from existing methods, the proposed method integrates local pairwise comparison labels together to minimise a cost that corresponds to global inconsistency of ranking order. This not only leads to better detection of annotation outliers but also enables learning with extremely sparse annotations. Extensive experiments on various benchmark datasets demonstrate that our new approach significantly outperforms state-of-the-arts alternatives.
A Roofline Visualization Framework
Venue: arXiv cs.PF 2015
Year: 2015

The Roofline Model and its derivatives provide an intuitive representation of the best achievable performance on a given architecture. The Roofline Toolkit project is a collaboration among researchers at Argonne National Laboratory, Lawrence Berkeley National Laboratory, and the University of Oregon and consists of three main parts: hardware characterization, software characterization, and data manipulation and visualization interface. These components address the different aspects of performance data acquisition and manipulation required for performance analysis, modeling and optimization of codes on existing and emerging architectures. In this paper we introduce an initial implementation of the third component, a system for visualizing roofline charts and managing roofline performance analysis data. We discuss the implementation and rationale for the integration of the roofline visualization system into the Eclipse IDE. An overview of our continuing efforts and goals in the development of this project is provided.
Disaster Monitoring with Wikipedia and Online Social Networking Sites: Structured Data and Linked Data Fragments to the Rescue?
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we present the first results of our ongoing early-stage research on a realtime disaster detection and monitoring tool. Based on Wikipedia, it is language-agnostic and leverages user-generated multimedia content shared on online social networking sites to help disaster responders prioritize their efforts. We make the tool and its source code publicly available as we make progress on it. Furthermore, we strive to publish detected disasters and accompanying multimedia content following the Linked Data principles to facilitate its wide consumption, redistribution, and evaluation of its usefulness.
Average power limitations in Sliding Window Contention Resolution Diversity Slotted Aloha
Venue: arXiv cs.IT 2015
Year: 2015

Recently a new Random Access technique based on Aloha and using Interference Cancellation (IC) named Sliding Window Contention Resolution Diversity Slotted Aloha (SW-CRDSA) has been introduced. Differently from classic CRDSA that operates grouping slots in frames, this technique operates in an unframed manner yielding to better throughput results and smaller average packet delay with respect to frame-based CRDSA. However as classic CRDSA also SW-CRDSA relies on multiple transmission of the same packet. While this can be acceptable in systems where the only limit resides in the peak transmission power, it could represent a problem when constraints on the average power (e.g. at the transponder of a satellite system) are present. In this paper, a comparison in terms of normalized efficiency is carried out between Slotted Aloha and the two CRDSA techniques.
Augmented Test Collections: A Step in the Right Direction
Venue: arXiv cs.IR 2015
Year: 2015

In this position paper we argue that certain aspects of relevance assessment in the evaluation of IR systems are oversimplified and that human assessments represented by qrels should be augmented to take account of contextual factors and the subjectivity of the task at hand. We propose enhancing test collections used in evaluation with information related to human assessors and their interpretation of the task. Such augmented collections would provide a more realistic and user-focused evaluation, enabling us to better understand the evaluation process, the performance of systems and user interactions. A first step is to conduct user studies to examine in more detail what people actually do when we ask them to judge the relevance of a document.
Document Distance for the Automated Expansion of Relevance Judgements for Information Retrieval Evaluation
Venue: arXiv cs.IR 2015
Year: 2015

This paper reports the use of a document distance-based approach to automatically expand the number of available relevance judgements when these are limited and reduced to only positive judgements. This may happen, for example, when the only available judgements are extracted from a list of references in a published review paper. We compare the results on two document sets: OHSUMED, based on medical research publications, and TREC-8, based on news feeds. We show that evaluations based on these expanded relevance judgements are more reliable than those using only the initially available judgements, especially when the number of available judgements is very limited.
Design of a Novel Network Architecture for Distributed Event-Based Systems Using Directional Random Walks in an Ubiquitous Sensing Scenario
Venue: arXiv cs.DC 2015
Year: 2015

Ubiquitous sensing devices frequently disseminate data among them. The use of a distributed event-based system that decouples publishers from subscribers arises as an ideal candidate to implement the dissemination process. In this paper, we present a network architecture that merges the network and overlay layers of typical structured event-based systems. Directional random walks are used for the construction of this merged layer. Our strategy avoids using a specific network protocol that provides point-to-point communication. This implies that the topology of the network is not maintained, so that nodes not involved in the system are able to save energy and computing resources. We evaluate the performance of the overlay layer using directional random walks and pure random walks for its construction. Our results show that directional random walks are more efficient because: (1) they use less nodes of the network for the establishment of the active path of the overlay layer and (2) they have a more reliable performance. Furthermore, as the number of nodes in the network increases, so do the number of nodes in the active path of the overlay layer for the same number of publishers and subscribers. Finally, we discard any correlation between the number of nodes that form the overlay layer and the maximum Euclidean distance traversed by the walkers.
Symmetric Strategy Improvement
Venue: arXiv cs.GT 2015
Year: 2015

Symmetry is inherent in the definition of most of the two-player zero-sum games, including parity, mean-payoff, and discounted-payoff games. It is therefore quite surprising that no symmetric analysis techniques for these games exist. We develop a novel symmetric strategy improvement algorithm where, in each iteration, the strategies of both players are improved simultaneously. We show that symmetric strategy improvement defies Friedmann's traps, which shook the belief in the potential of classic strategy improvement to be polynomial.
Average probability of a dangerous failure on demand: Different modelling methods, similar results
Venue: arXiv cs.SE 2015
Year: 2015

According to the IEC 61508 functional safety standard, it is required to estimate the achieved safety integrity of the system due to random hardware failures. For a safety function operating in a low demand mode, this measure is the average probability of a dangerous failure on demand (PFDavg). In the present paper, four techniques have been applied to various configurations of a case study: fault tree analyses supported by GRIF/Tree, multi-phase Markov models supported by GRIF/Markov, stochastic Petri nets with predicates supported by GRIF/Petri, and approximate equations (developed by DNV and different from those given in IEC 61508) supported by OrbitSIL. It is shown that all these methods yield very similar results for PFDavg, taking the characteristics required by the standard into account. The choice of a method should therefore not be determined by dogmatic assumptions, but should result of a balance between modelling effort and objectives, given the system properties. For this task, a discussion about pros and cons of each method is proposed.
Approximation Algorithms for P2P Orienteering and Stochastic Vehicle Routing Problem
Venue: arXiv cs.DS 2015
Year: 2015

We consider the P2P orienteering problem on general metrics and present a (2+ε) approximation algorithm. In the stochastic P2P orienteering problem we are given a metric and each node has a fixed reward and random size. The goal is to devise a strategy for visiting the nodes so as to maximize the expected value of the reward without violating the budget constraints. We present an approximation algorithm for the non-adaptive variant of the P2P Stochastic orienteering. As an implication of the approximation to the stochastic P2P orienteering problem, we define a stochastic vehicle routing problem with time-windows and present a constant factor approximation solution.
Competitive Equilibrium with Equal Incomes for Allocation of Indivisible Objects
Venue: arXiv cs.GT 2015
Year: 2015

In AAMAS 2014, Bouveret and Lemaitre (2014) presented a hierarchy of fairness concepts for allocation of indivisible objects. Among them CEEI (Competitive Equilibrium with Equal Incomes) was the strongest. In this note, we settle the complexity of computing a discrete CEEI assignment by showing it is strongly NP-hard. We then highlight a fairness notion (CEEI-FRAC) that is even stronger than CEEI for discrete assignments, is always Pareto optimal, and can be verified in polynomial time. We also show that computing a CEEI-FRAC discrete assignment is strongly NP-hard in general but polynomial-time computable if the utilities are zero or one.
maxDNN: An Efficient Convolution Kernel for Deep Learning with Maxwell GPUs
Venue: arXiv cs.NE 2015
Year: 2015

This paper describes maxDNN, a computationally efficient convolution kernel for deep learning with the NVIDIA Maxwell GPU. maxDNN reaches 96.3% computational efficiency on typical deep learning network architectures. The design combines ideas from cuda-convnet2 with the Maxas SGEMM assembly code. We only address forward propagation (FPROP) operation of the network, but we believe that the same techniques used here will be effective for backward propagation (BPROP) as well.
The Complexity of the Kth Largest Subset Problem and Related Problems
Venue: arXiv cs.CC 2015
Year: 2015

We show that the Kth largest subset problem and the Kth largest m-tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literature were previously shown NP-hard via reductions from those two problems, and by our main result they become PP-hard as well. We also provide complementary PP-upper bounds for some of them.
Error and Erasure Exponents for the Broadcast Channel with Degraded Message Sets
Venue: arXiv cs.IT 2015
Year: 2015

Error and erasure exponents for the broadcast channel with degraded message sets are analyzed. The focus of our error probability analysis is on the main receiver where, nominally, both messages are to be decoded. A two-step decoding algorithm is proposed and analyzed. This receiver first attempts to decode both messages, failing which, it attempts to decode only the message representing the coarser information, i.e., the cloud center. This algorithm reflects the intuition that we should decode both messages only if we have confidence in the estimates; otherwise one should only decode the coarser information. The resulting error and erasure exponents, derived using the method of types, are expressed in terms of a penalized form of the modified random coding error exponent.
Measuring the local GitHub developer community
Venue: arXiv cs.SI 2015
Year: 2015

Creating rankings might seem like a vain exercise in belly-button gazing, even more so for people so unlike that kind of things as programmers. However, in this paper we will try to prove how creating city (or province) based rankings in Spain has led to all kind of interesting effects, including increased productivity and community building. We describe the methodology we have used to search for programmers residing in a particular province focusing on those where most population is concentrated and apply different measures to show how these communities differ in structure, number and productivity.
JMS: A workflow management system and web-based cluster front-end for the Torque resource manager
Venue: arXiv cs.SE 2015
Year: 2015

Motivation: Complex computational pipelines are becoming a staple of modern scientific research. Often these pipelines are resource intensive and require days of computing time. In such cases, it makes sense to run them over distributed computer clusters where they can take advantage of the aggregated resources of many powerful computers. In addition to this, researchers often want to integrate their workflows into their own web servers. In these cases, software is needed to manage the submission of jobs from the web interface to the cluster and then return the results once the job has finished executing. Results: We have developed the Job Management System (JMS), a workflow management system and interface for the Torque resource manager. The JMS provides users with a user-friendly interface for creating complex workflows with multiple stages. It integrates this workflow functionality with Torque, a tool that is used to control and manage batch jobs on distributed computing clusters. The JMS can be used by researchers to build and run complex computational pipelines and provides functionality to include these pipelines in external interfaces. The JMS is currently being used to house a number of structural bioinformatics pipelines at the Research Unit in Bioinformatics (RUBi) at Rhodes University. Availability: The JMS is an open-source project and is freely available at https://github.com/RUBi-ZA/JMS
New Bounds on Optimal Sorting Networks
Venue: arXiv cs.DM 2015
Year: 2015

We present new parallel sorting networks for $17$ to $20$ inputs. For $17, 19,$ and $20$ inputs these new networks are faster (i.e., they require less computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on $17, 19,$ and $20$ channels. Furthermore, we show that our sorting network for $17$ inputs is optimal in the sense that no sorting network using less layers exists. This solves the main open problem of [D. Bundala & J. Zavodný. Optimal sorting networks, Proc. LATA 2014].
Feature Sampling Strategies for Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Although dense local spatial-temporal features with bag-of-features representation achieve state-of-the-art performance for action recognition, the huge feature number and feature size prevent current methods from scaling up to real size problems. In this work, we investigate different types of feature sampling strategies for action recognition, namely dense sampling, uniformly random sampling and selective sampling. We propose two effective selective sampling methods using object proposal techniques. Experiments conducted on a large video dataset show that we are able to achieve better average recognition accuracy using 25% less features, through one of proposed selective sampling methods, and even remain comparable accuracy while discarding 70% features.
Survey:Natural Language Parsing For Indian Languages
Venue: arXiv cs.CL 2015
Year: 2015

Syntactic parsing is a necessary task which is required for NLP applications including machine translation. It is a challenging task to develop a qualitative parser for morphological rich and agglutinative languages. Syntactic analysis is used to understand the grammatical structure of a natural language sentence. It outputs all the grammatical information of each word and its constituent. Also issues related to it help us to understand the language in a more detailed way. This literature survey is groundwork to understand the different parser development for Indian languages and various approaches that are used to develop such tools and techniques. This paper provides a survey of research papers from well known journals and conferences.
On the stability of asynchronous Random Access Schemes
Venue: arXiv cs.IT 2015
Year: 2015

Slotted Aloha-based Random Access (RA) techniques have recently regained attention in light of the use of Interference Cancellation (IC) as a mean to exploit diversity created through the transmission of multiple burst copies per packet content (CRDSA). Subsequently, the same concept has been extended to pure ALOHA-based techniques in order to boost the performance also in case of asynchronous RA schemes. In this paper, throughput as well as packet delay and related stability for asynchronous ALOHA techniques under geometrically distributed retransmissions are analyzed both in case of finite and infinite population size. Moreover, a comparison between pure ALOHA, its evolution (known as CRA) and CRDSA techniques is presented, in order to give a measure of the achievable gain that can be reached in a closed-loop scenario with respect to the previous state of the art.
The Affinity Effects of Parallelized Libraries in Concurrent Environments
Venue: arXiv cs.DC 2015
Year: 2015

The use of cloud computing grows as it appears to be an additional resource for High-Performance Parallel and Distributed Computing (HPDC), especially with respect to its use in support of scientific applications. Many studies have been devoted to determining the effect of the virtualization layer on the performance, but most of the studies conducted so far lack insight into the joint effects between application type, virtualization layer and parallelized libraries in applications. This work introduces the concept of affinity with regard to the combined effects of the virtualization layer, class of application and parallelized libraries used in these applications. Affinity is here defined as the degree of influence that one application has on other applications when running concurrently in virtual environments hosted on the same real server. The results presented here show how parallel libraries used in application implementation have a significant influence and how the combinations between these types of libraries and classes of applications could significantly influence the performance of the environment. In this context, the concept of affinity is then used to evaluate these impacts to contribute to better stability and performance in the computational environment.
FMAP: Distributed Cooperative Multi-Agent Planning
Venue: arXiv cs.AI 2015
Year: 2015

This paper proposes FMAP (Forward Multi-Agent Planning), a fully-distributed multi-agent planning method that integrates planning and coordination. Although FMAP is specifically aimed at solving problems that require cooperation among agents, the flexibility of the domain-independent planning model allows FMAP to tackle multi-agent planning tasks of any type. In FMAP, agents jointly explore the plan space by building up refinement plans through a complete and flexible forward-chaining partial-order planner. The search is guided by $h_{DTG}$, a novel heuristic function that is based on the concepts of Domain Transition Graph and frontier state and is optimized to evaluate plans in distributed environments. Agents in FMAP apply an advanced privacy model that allows them to adequately keep private information while communicating only the data of the refinement plans that is relevant to each of the participating agents. Experimental results show that FMAP is a general-purpose approach that efficiently solves tightly-coupled domains that have specialized agents and cooperative goals as well as loosely-coupled problems. Specifically, the empirical evaluation shows that FMAP outperforms current MAP systems at solving complex planning tasks that are adapted from the International Planning Competition benchmarks.