OpenRaiser/Intern-Atlas huggingface dataset:
Parallel Exhaustive Search without Coordination
Venue: arXiv cs.DC 2015
Year: 2015

We analyze parallel algorithms in the context of exhaustive search over totally ordered sets. Imagine an infinite list of "boxes", with a "treasure" hidden in one of them, where the boxes' order reflects the importance of finding the treasure in a given box. At each time step, a search protocol executed by a searcher has the ability to peek into one box, and see whether the treasure is present or not. By equally dividing the workload between them, $k$ searchers can find the treasure $k$ times faster than one searcher. However, this straightforward strategy is very sensitive to failures (e.g., crashes of processors), and overcoming this issue seems to require a large amount of communication. We therefore address the question of designing parallel search algorithms maximizing their speed-up and maintaining high levels of robustness, while minimizing the amount of resources for coordination. Based on the observation that algorithms that avoid communication are inherently robust, we analyze the best running time performance of non-coordinating algorithms. Specifically, we devise non-coordinating algorithms that achieve a speed-up of $9/8$ for two searchers, a speed-up of $4/3$ for three searchers, and in general, a speed-up of $\frac{k}{4}(1+1/k)^2$ for any $k\geq 1$ searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full-coordination, and our algorithms are surprisingly simple and hence applicable. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Overall, we highlight that, in faulty contexts in which coordination between the searchers is technically difficult to implement, intrusive with respect to privacy, and/or costly in term of resources, it might well be worth giving up on coordination, and simply run our non-coordinating exhaustive search algorithms.
Pixel-wise Segmentation of Street with Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Pixel-wise street segmentation of photographs taken from a drivers perspective is important for self-driving cars and can also support other object recognition tasks. A framework called SST was developed to examine the accuracy and execution time of different neural networks. The best neural network achieved an $F_1$-score of 89.5% with a simple feedforward neural network which trained to solve a regression task.
A Pareto Optimal D* Search Algorithm for Multiobjective Path Planning
Venue: arXiv cs.AI 2015
Year: 2015

Path planning is one of the most vital elements of mobile robotics, providing the agent with a collision-free route through the workspace. The global path plan can be calculated with a variety of informed search algorithms, most notably the A* search method, guaranteed to deliver a complete and optimal solution that minimizes the path cost. D* is widely used for its dynamic replanning capabilities. Path planning optimization typically looks to minimize the distance traversed from start to goal, but many mobile robot applications call for additional path planning objectives, presenting a multiobjective optimization (MOO) problem. Common search algorithms, e.g. A* and D*, are not well suited for MOO problems, yielding suboptimal results. The search algorithm presented in this paper is designed for optimal MOO path planning. The algorithm incorporates Pareto optimality into D*, and is thus named D*-PO. Non-dominated solution paths are guaranteed by calculating the Pareto front at each search step. Simulations were run to model a planetary exploration rover in a Mars environment, with five path costs. The results show the new, Pareto optimal D*-PO outperforms the traditional A* and D* algorithms for MOO path planning.
A Lower Bound for the Distributed Lovász Local Lemma
Venue: arXiv cs.DC 2015
Year: 2015

We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires $Ω(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where $d$ is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of $O(\log n)$ rounds in bounded-degree graphs, and the best lower bound before our work was $Ω(\log^* n)$ rounds [Chung et al. 2014].
SWISH: SWI-Prolog for Sharing
Venue: arXiv cs.PL 2015
Year: 2015

Recently, we see a new type of interfaces for programmers based on web technology. For example, JSFiddle, IPython Notebook and R-studio. Web technology enables cloud-based solutions, embedding in tutorial web pages, atractive rendering of results, web-scale cooperative development, etc. This article describes SWISH, a web front-end for Prolog. A public website exposes SWI-Prolog using SWISH, which is used to run small Prolog programs for demonstration, experimentation and education. We connected SWISH to the ClioPatria semantic web toolkit, where it allows for collaborative development of programs and queries related to a dataset as well as performing maintenance tasks on the running server and we embedded SWISH in the Learn Prolog Now! online Prolog book.
Bound Your Models! How to Make OWL an ASP Modeling Language
Venue: arXiv cs.PL 2015
Year: 2015

To exploit the Web Ontology Language OWL as an answer set programming (ASP) language, we introduce the notion of bounded model semantics, as an intuitive and computationally advantageous alternative to its classical semantics. We show that a translation into ASP allows for solving a wide range of bounded-model reasoning tasks, including satisfiability and axiom entailment but also novel ones such as model extraction and enumeration. Ultimately, our work facilitates harnessing advanced semantic web modeling environments for the logic programming community through an "off-label use" of OWL.
Sexual videos in Internet: a test of 11 hypotheses about intimate practices and gender interactions in Latin America
Venue: arXiv cs.CY 2015
Year: 2015

There is a marked lack of literature on user-submitted sexual videos from Latin America. To start filling that gap, we present a formal statistical testing of several hypotheses about the characteristics of 214 videos from Nereliatube.com posted from the inauguration of the site until December 2010. We found that in most cases the video was made consensually and the camera was operated by the man. The most frequent practice shown was fellatio, followed by vaginal penetration. The great majority of videos showed the sexual interactions of one woman with one man; group sex was rare. Violence and manifestations of power were rare and when there was violence it was mostly simulated. Latin American user-submitted sexual videos in Nereliatube generally reflect a society in which women and men have a variety of sexual practices that are mostly consensual and that do not differ from the biologically and anthropologically expected patterns.
Color Space Transformation Network
Venue: arXiv cs.CV 2015
Year: 2015

Deep networks have become very popular over the past few years. The main reason for this widespread use is their excellent ability to learn and predict knowledge in a very easy and efficient way. Convolutional neural networks and auto-encoders have become the normal in the area of imaging and computer vision achieving unprecedented accuracy levels in many applications. The most common strategy is to build and train networks with many layers by tuning their hyper-parameters. While this approach has proven to be a successful way to build robust deep learning schemes it suffers from high complexity. In this paper we introduce a module that learns color space transformations within a network. Given a large dataset of colored images the color space transformation module tries to learn color space transformations that increase overall classification accuracy. This module has shown to increase overall accuracy for the same network design and to achieve faster convergence. It is part of a broader family of image transformations (e.g. spatial transformer network).
Liquid Price of Anarchy
Venue: arXiv cs.GT 2015
Year: 2015

Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency in auctions, is inadequate for settings with budgets, since there may be a large disconnect between the value a bidder derives from obtaining an item and what can be liquidated from her. The Liquid Welfare objective function has been suggested as a natural alternative for settings with budgets. Simple auctions, like simultaneous item auctions, are evaluated by their performance at equilibrium using the Price of Anarchy (PoA) measure -- the ratio of the objective function value of the optimal outcome to the worst equilibrium. Accordingly, we evaluate the performance of simultaneous item auctions in budgeted settings by the Liquid Price of Anarchy (LPoA) measure -- the ratio of the optimal Liquid Welfare to the Liquid Welfare obtained in the worst equilibrium. Our main result is that the LPoA for mixed Nash equilibria is bounded by a constant when bidders are additive and items can be divided into sufficiently many discrete parts. Our proofs are robust, and can be extended to achieve similar bounds for simultaneous second price auctions as well as Bayesian Nash equilibria. For pure Nash equilibria, we establish tight bounds on the LPoA for the larger class of fractionally-subadditive valuations. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique does not fit into the smoothness framework.
Robust Registration of Calcium Images by Learned Contrast Synthesis
Venue: arXiv cs.CV 2015
Year: 2015

Multi-modal image registration is a challenging task that is vital to fuse complementary signals for subsequent analyses. Despite much research into cost functions addressing this challenge, there exist cases in which these are ineffective. In this work, we show that (1) this is true for the registration of in-vivo Drosophila brain volumes visualizing genetically encoded calcium indicators to an nc82 atlas and (2) that machine learning based contrast synthesis can yield improvements. More specifically, the number of subjects for which the registration outright failed was greatly reduced (from 40% to 15%) by using a synthesized image.
Modular Responsive Web Design using Element Queries
Venue: arXiv cs.SE 2015
Year: 2015

Responsive Web Design (RWD) enables web applications to adapt to the characteristics of different devices such as screen size which is important for mobile browsing. Today, the only W3C standard to support this adaptability is CSS media queries. However, using media queries it is impossible to create applications in a modular way, because responsive elements then always depend on the global context. Hence, responsive elements can only be reused if the global context is exactly the same, severely limiting their reusability. This makes it extremely challenging to develop large responsive applications, because the lack of true modularity makes certain requirement changes either impossible or expensive to realize. In this paper we extend RWD to also include responsive modules, i.e., modules that adapt their design based on their local context independently of the global context. We present the ELQ project which implements our approach. ELQ is a novel implementation of so-called element queries which generalize media queries. Importantly, our design conforms to existing web specifications, enabling adoption on a large scale. ELQ is designed to be heavily extensible using plugins. Experimental results show speed-ups of the core algorithms of up to 37x compared to previous approaches.
Power Consumption of Virtualization Technologies: an Empirical Investigation
Venue: arXiv cs.DC 2015
Year: 2015

Virtualization is growing rapidly as a result of the increasing number of alternative solutions in this area, and of the wide range of application field. Until now, hypervisor-based virtualization has been the de facto solution to perform server virtualization. Recently, container-based virtualization - an alternative to hypervisors - has gained more attention because of lightweight characteristics, attracting cloud providers that have already made use of it to deliver their services. However, a gap in the existing research on containers exists in the area of power consumption. This paper presents the results of a performance comparison in terms of power consumption of four different virtualization technologies: KVM and Xen, which are based on hypervisor virtualization, Docker and LXC which are based on container virtualization. The aim of this empirical investigation, carried out by means of a testbed, is to understand how these technologies react to particular workloads. Our initial results show how, despite of the number of virtual entities running, both kinds of virtualization alternatives behave similarly in idle state and in CPU/Memory stress test. Contrarily, the results on network performance show differences between the two technologies.
Interactive Answer Set Programming - Preliminary Report
Venue: arXiv cs.PL 2015
Year: 2015

Traditional Answer Set Programming (ASP) rests upon one-shot solving. A logic program is fed into an ASP system and its stable models are computed. The high practical relevance of dynamic applications led to the development of multi-shot solving systems. An operative system solves continuously changing logic programs. Although this was primarily aiming at dynamic applications in assisted living, robotics, or stream reasoning, where solvers interact with an environment, it also opened up the opportunity of interactive ASP, where a solver interacts with a user. We begin with a formal characterization of interactive ASP in terms of states and operations on them. In turn, we describe the interactive ASP shell aspic along with its basic functionalities.
Factorizing LambdaMART for cold start recommendations
Venue: arXiv cs.LG 2015
Year: 2015

Recommendation systems often rely on point-wise loss metrics such as the mean squared error. However, in real recommendation settings only few items are presented to a user. This observation has recently encouraged the use of rank-based metrics. LambdaMART is the state-of-the-art algorithm in learning to rank which relies on such a metric. Despite its success it does not have a principled regularization mechanism relying in empirical approaches to control model complexity leaving it thus prone to overfitting. Motivated by the fact that very often the users' and items' descriptions as well as the preference behavior can be well summarized by a small number of hidden factors, we propose a novel algorithm, LambdaMART Matrix Factorization (LambdaMART-MF), that learns a low rank latent representation of users and items using gradient boosted trees. The algorithm factorizes lambdaMART by defining relevance scores as the inner product of the learned representations of the users and items. The low rank is essentially a model complexity controller; on top of it we propose additional regularizers to constraint the learned latent representations that reflect the user and item manifolds as these are defined by their original feature based descriptors and the preference behavior. Finally we also propose to use a weighted variant of NDCG to reduce the penalty for similar items with large rating discrepancy. We experiment on two very different recommendation datasets, meta-mining and movies-users, and evaluate the performance of LambdaMART-MF, with and without regularization, in the cold start setting as well as in the simpler matrix completion setting. In both cases it outperforms in a significant manner current state of the art algorithms.
An exploration of fetish social networks and communities
Venue: arXiv cs.SI 2015
Year: 2015

Online Social Networks (OSNs) provide a venue for virtual interactions and relationships between individuals. In some communities, OSNs also facilitate arranging online meetings and relationships. FetLife, the worlds largest anonymous social network for the BDSM, fetish and kink communities, provides a unique example of an OSN that serves as an interaction space, community organizing tool, and sexual market. In this paper, we present a first look at the characteristics of European members of Fetlife, comprising 504,416 individual nodes with 1,912,196 connections. We looked at user characteristics in terms of gender, sexual orientation, and preferred role. We further examined the topological and structural properties of groups, as well as the type of interactions and relations between their members. Our results suggest there are important differences between the FetLife community and conventional OSNs. The network can be characterised by complex gender based interactions both from a sexual market and platonic viewpoint which point to a truly fascinating social network.
ATLAS: An Adaptive Failure-aware Scheduler for Hadoop
Venue: arXiv cs.DC 2015
Year: 2015

Hadoop has become the de facto standard for processing large data in today's cloud environment. The performance of Hadoop in the cloud has a direct impact on many important applications ranging from web analytic, web indexing, image and document processing to high-performance scientific computing. However, because of the scale, complexity and dynamic nature of the cloud, failures are common and these failures often impact the performance of jobs running in Hadoop. Although Hadoop possesses built-in failure detection and recovery mechanisms, several scheduled jobs still fail because of unforeseen events in the cloud environment. A single task failure can cause the failure of the whole job and unpredictable job running times. In this report, we propose ATLAS (AdapTive faiLure-Aware Scheduler), a new scheduler for Hadoop that can adapt its scheduling decisions to events occurring in the cloud environment. Using statistical models, ATLAS predicts task failures and adjusts its scheduling decisions on the fly to reduce task failure occurrences. We implement ATLAS in the Hadoop framework of Amazon Elastic MapReduce (EMR) and perform a case study to compare its performance with those of the FIFO, Fair and Capacity schedulers. Results show that ATLAS can reduce the percentage of failed jobs by up to 28% and the percentage of failed tasks by up to 39%, and the total execution time of jobs by 10 minutes on average. ATLAS also reduces CPU and memory usages.
64-APSK Constellation and Mapping Optimization for Satellite Broadcasting Using Genetic Algorithms
Venue: arXiv cs.IT 2015
Year: 2015

DVB-S2 and DVB-SH satellite broadcasting standards currently deploy 16- and 32-amplitude phase shift keying (APSK) modulation using the consultative committee for space data systems (CCSDS) mapping. Such standards also include hierarchical modulation as a mean to provide unequal error protection in highly variable channels over satellite. Foreseeing the increasing need for higher data rates, this paper tackles the optimization of 64-APSK constellations to minimize the mean square error between the original and received symbol. Optimization is performed according to the sensitivity of the data to the channel errors, by means of genetic algorithms, a well-known technique currently used in a variety of application domains, when close form solutions are impractical. Test results show that through non-uniform constellation and asymmetric symbol mapping, it is possible to significantly reduce the distortion while preserving bandwidth efficiency. Tests performed on real signals based on perceptual quality measurements allow validating the proposed scheme against conventional 64-APSK constellations and CCSDS mapping.
Ranking scientists
Venue: arXiv cs.DL 2015
Year: 2015

Currently the ranking of scientists is based on the $h$-index, which is widely perceived as an imprecise and simplistic though still useful metric. We find that the $h$-index actually favours modestly performing researchers and propose a simple criterion for proper ranking.
Mining Local Gazetteers of Literary Chinese with CRF and Pattern based Methods for Biographical Information in Chinese History
Venue: arXiv cs.CL 2015
Year: 2015

Person names and location names are essential building blocks for identifying events and social networks in historical documents that were written in literary Chinese. We take the lead to explore the research on algorithmically recognizing named entities in literary Chinese for historical studies with language-model based and conditional-random-field based methods, and extend our work to mining the document structures in historical documents. Practical evaluations were conducted with texts that were extracted from more than 220 volumes of local gazetteers (Difangzhi). Difangzhi is a huge and the single most important collection that contains information about officers who served in local government in Chinese history. Our methods performed very well on these realistic tests. Thousands of names and addresses were identified from the texts. A good portion of the extracted names match the biographical information currently recorded in the China Biographical Database (CBDB) of Harvard University, and many others can be verified by historians and will become as new additions to CBDB.
Geodesic Spanners for Points on a Polyhedral Terrain
Venue: arXiv cs.CG 2015
Year: 2015

We show that there exists a geodesic spanner with almost linear number of edges.
Comparing Writing Styles using Word Embedding and Dynamic Time Warping
Venue: arXiv cs.CL 2015
Year: 2015

The development of plot or story in novels is reflected in the content and the words used. The flow of sentiments, which is one aspect of writing style, can be quantified by analyzing the flow of words. This study explores literary works as signals in word embedding space and tries to compare writing styles of popular classic novels using dynamic time warping.
PRIME: Phase Retrieval via Majorization-Minimization
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the phase retrieval problem in which measurements consist of only the magnitude of several linear measurements of the unknown, e.g., spectral components of a time sequence. We develop low-complexity algorithms with superior performance based on the majorization-minimization (MM) framework. The proposed algorithms are referred to as PRIME: Phase Retrieval vIa the Majorization-minimization techniquE. They are preferred to existing benchmark methods since at each iteration a simple surrogate problem is solved with a closed-form solution that monotonically decreases the original objective function. In total, four algorithms are proposed using different majorization-minimization techniques. Experimental results validate that our algorithms outperform existing methods in terms of successful recovery and mean square error under various settings.