OpenRaiser/Intern-Atlas huggingface dataset:
Gerbil: A Fast and Memory-Efficient $k$-mer Counter with GPU-Support
Venue: arXiv cs.DS 2016
Year: 2016

A basic task in bioinformatics is the counting of $k$-mers in genome strings. The $k$-mer counting problem is to build a histogram of all substrings of length $k$ in a given genome sequence. We present the open source $k$-mer counting software Gerbil that has been designed for the efficient counting of $k$-mers for $k\geq32$. Given the technology trend towards long reads of next-generation sequencers, support for large $k$ becomes increasingly important. While existing $k$-mer counting tools suffer from excessive memory resource consumption or degrading performance for large $k$, Gerbil is able to efficiently support large $k$ without much loss of performance. Our software implements a two-disk approach. In the first step, DNA reads are loaded from disk and distributed to temporary files that are stored at a working disk. In a second step, the temporary files are read again, split into $k$-mers and counted via a hash table approach. In addition, Gerbil can optionally use GPUs to accelerate the counting step. For large $k$, we outperform state-of-the-art open source $k$-mer counting tools for large genome data sets.
CYCLONE Unified Deployment and Management of Federated, Multi-Cloud Applications
Venue: arXiv cs.DC 2016
Year: 2016

Various Cloud layers have to work in concert in order to manage and deploy complex multi-cloud applications, executing sophisticated workflows for Cloud resource deployment, activation, adjustment, interaction, and monitoring. While there are ample solutions for managing individual Cloud aspects (e.g. network controllers, deployment tools, and application security software), there are no well-integrated suites for managing an entire multi cloud environment with multiple providers and deployment models. This paper presents the CYCLONE architecture that integrates a number of existing solutions to create an open, unified, holistic Cloud management platform for multi-cloud applications, tailored to the needs of research organizations and SMEs. It discusses major challenges in providing a network and security infrastructure for the Intercloud and concludes with the demonstration how the architecture is implemented in a real life bioinformatics use case.
Prior-based Coregistration and Cosegmentation
Venue: arXiv cs.CV 2016
Year: 2016

We propose a modular and scalable framework for dense coregistration and cosegmentation with two key characteristics: first, we substitute ground truth data with the semantic map output of a classifier; second, we combine this output with population deformable registration to improve both alignment and segmentation. Our approach deforms all volumes towards consensus, taking into account image similarities and label consistency. Our pipeline can incorporate any classifier and similarity metric. Results on two datasets, containing annotations of challenging brain structures, demonstrate the potential of our method.
Searching for the Internet of Things on the Web: Where It Is and What It Looks Like
Venue: arXiv cs.IR 2016
Year: 2016

The Internet of Things (IoT), in general, is a compelling paradigm that aims to connect everyday objects to the Internet. Nowadays, IoT is considered as one of the main technologies which contribute towards reshaping our daily lives in the next decade. IoT unlocks many exciting new opportunities in a variety of applications in research and industry domains. However, many have complained about the absence of the real-world IoT data. Unsurprisingly, a common question that arises regularly nowadays is "Does the IoT already exist?". So far, little has been known about the real-world situation on IoT, its attributes, the presentation of data and user interests. To answer this question, in this work, we conduct an in-depth analytical investigation on real IoT data. More specifically, we identify IoT data sources over the Web and develop a crawler engine to collect large-scale real-world IoT data for the first time. We make the results of our work available to the public in order to assist the community in the future research. In particular, we collect the data of nearly two million Internet connected objects and study trends in IoT using a real-world query set from an IoT search engine. Based on the collected data and our analysis, we identify the typical characteristics of IoT data. The most intriguing finding of our study is that IoT data is mainly disseminated using Web Mapping while the emerging IoT solutions such as the Web of Things, are currently not well adopted. On top of our findings, we further discuss future challenges and open research problems in the IoT area.
On the effects of a centralized computer routing and reservation system on the electric vehicle public charging network
Venue: arXiv cs.SY 2016
Year: 2016

One solution to the limited range of battery electric vehicles is the provision of a public charging infrastructure to enable longer journeys. This paper describes a simulation model of a centralized computer routing and reservation system based on the current charging infrastructure deployed (early 2016) in Ireland using the Irish population density and a trip length distribution. Monte Carlo simulations show quantitatively the effects of EV on-board charger power rating and the advantages of a routing and reservation systems on a country wide scale in terms of the number of electric vehicles that can be supported. The effect of charge point fault rates based on the currently deployed charging infrastructure is also assessed.
Large Alphabet Source Coding using Independent Component Analysis
Venue: arXiv cs.IT 2016
Year: 2016

Large alphabet source coding is a basic and well-studied problem in data compression. It has many applications such as compression of natural language text, speech and images. The classic perception of most commonly used methods is that a source is best described over an alphabet which is at least as large as the observed alphabet. In this work we challenge this approach and introduce a conceptual framework in which a large alphabet source is decomposed into "as statistically independent as possible" components. This decomposition allows us to apply entropy encoding to each component separately, while benefiting from their reduced alphabet size. We show that in many cases, such decomposition results in a sum of marginal entropies which is only slightly greater than the entropy of the source. Our suggested algorithm, based on a generalization of the Binary Independent Component Analysis, is applicable for a variety of large alphabet source coding setups. This includes the classical lossless compression, universal compression and high-dimensional vector quantization. In each of these setups, our suggested approach outperforms most commonly used methods. Moreover, our proposed framework is significantly easier to implement in most of these cases.
Deep nets for local manifold learning
Venue: arXiv cs.LG 2016
Year: 2016

The problem of extending a function $f$ defined on a training data $\mathcal{C}$ on an unknown manifold $\mathbb{X}$ to the entire manifold and a tubular neighborhood of this manifold is considered in this paper. For $\mathbb{X}$ embedded in a high dimensional ambient Euclidean space $\mathbb{R}^D$, a deep learning algorithm is developed for finding a local coordinate system for the manifold {\bf without eigen--decomposition}, which reduces the problem to the classical problem of function approximation on a low dimensional cube. Deep nets (or multilayered neural networks) are proposed to accomplish this approximation scheme by using the training data. Our methods do not involve such optimization techniques as back--propagation, while assuring optimal (a priori) error bounds on the output in terms of the number of derivatives of the target function. In addition, these methods are universal, in that they do not require a prior knowledge of the smoothness of the target function, but adjust the accuracy of approximation locally and automatically, depending only upon the local smoothness of the target function. Our ideas are easily extended to solve both the pre--image problem and the out--of--sample extension problem, with a priori bounds on the growth of the function thus extended.
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
Venue: arXiv cs.CC 2016
Year: 2016

In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomness-efficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for the question of the other prover. In recent years, there have been indications that randomness-efficient parallel repetition (also called derandomized parallel repetition) might be possible for games with large degree, circumventing the impossibility result of Feige and Kilian. In particular, Dinur and Meir (CCC'11) construct games with large degree whose repetition can be derandomized using a theorem of Impagliazzo, Kabanets and Wigderson (SICOMP'12). However, obtaining derandomized parallel repetition theorems that would yield optimal inapproximability results has remained elusive. This paper presents an explanation for the current impasse in progress, by proving a limitation on derandomized parallel repetition. We formalize two properties which we call "fortification-friendliness" and "yields robust embeddings." We show that any proof of derandomized parallel repetition achieving almost-linear blow-up cannot both (a) be fortification-friendly and (b) yield robust embeddings. Unlike Feige and Kilian, we do not require the small degree assumption. Given that virtually all existing proofs of parallel repetition, including the derandomized parallel repetition result of Dinur and Meir, share these two properties, our no-go theorem highlights a major barrier to achieving almost-linear derandomized parallel repetition.
Approximating Multicut and the Demand Graph
Venue: arXiv cs.DM 2016
Year: 2016

In the minimum Multicut problem, the input is an edge-weighted supply graph $G=(V,E)$ and a simple demand graph $H=(V,F)$. Either $G$ and $H$ are directed (DMulC) or both are undirected (UMulC). The goal is to remove a minimum weight set of edges in $G$ such that there is no path from $s$ to $t$ in the remaining graph for any $(s,t) \in F$. UMulC admits an $O(\log k)$-approximation where $k$ is the vertex cover size of $H$ while the best known approximation for DMulC is $\min\{k, \tilde{O}(n^{11/23})\}$. These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In contrast to these results some special cases of Multicut, such as the well-studied Multiway Cut problem, admit a constant factor approximation in both undirected and directed graphs. Motivated by both concrete instances from applications and abstract considerations, we consider the role that the structure of the demand graph $H$ plays in determining the approximability of Multicut. In undirected graphs our main result is a $2$-approximation in $n^{O(t)}$ time when the demand graph $H$ excludes an induced matching of size $t$. This gives a constant factor approximation for a specific demand graph that motivated this work. In contrast to undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. Assuming the Unique Games Conjecture (UGC), for a large class of fixed demand graphs DMulC cannot be approximated to a factor better than worst-case flow-cut gap. As a consequence we prove that for any fixed $k$, assuming UGC, DMulC with $k$ demand pairs is hard to approximate to within a factor better than $k$. On the positive side, we prove an approximation of $k$ when the demand graph excludes certain graphs as an induced subgraph. This generalizes the Multiway Cut result to a much larger class of demand graphs.
Self-presentation and emotional contagion on Facebook: new experimental measures of profiles' emotional coherence
Venue: arXiv cs.SI 2016
Year: 2016

Social Networks allow users to self-present by sharing personal contents with others which may add comments. Recent studies highlighted how the emotions expressed in a post affect others' posts, eliciting a congruent emotion. So far, no studies have yet investigated the emotional coherence between wall posts and its comments. This research evaluated posts and comments mood of Facebook profiles, analyzing their linguistic features, and a measure to assess an excessive self-presentation was introduced. Two new experimental measures were built, describing the emotional loading (positive and negative) of posts and comments, and the mood correspondence between them was evaluated. The profiles "empathy", the mood coherence between post and comments, was used to investigate the relation between an excessive self-presentation and the emotional coherence of a profile. Participants publish a higher average number of posts with positive mood. To publish an emotional post corresponds to get more likes, comments and receive a coherent mood of comments, confirming the emotional contagion effect reported in literature. Finally, the more empathetic profiles are characterized by an excessive self-presentation, having more posts, and receiving more comments and likes. To publish emotional contents appears to be functional to receive more comments and likes, fulfilling needs of attention-seeking.
An Evolutionary Algorithm to Learn SPARQL Queries for Source-Target-Pairs: Finding Patterns for Human Associations in DBpedia
Venue: arXiv cs.AI 2016
Year: 2016

Efficient usage of the knowledge provided by the Linked Data community is often hindered by the need for domain experts to formulate the right SPARQL queries to answer questions. For new questions they have to decide which datasets are suitable and in which terminology and modelling style to phrase the SPARQL query. In this work we present an evolutionary algorithm to help with this challenging task. Given a training list of source-target node-pair examples our algorithm can learn patterns (SPARQL queries) from a SPARQL endpoint. The learned patterns can be visualised to form the basis for further investigation, or they can be used to predict target nodes for new source nodes. Amongst others, we apply our algorithm to a dataset of several hundred human associations (such as "circle - square") to find patterns for them in DBpedia. We show the scalability of the algorithm by running it against a SPARQL endpoint loaded with > 7.9 billion triples. Further, we use the resulting SPARQL queries to mimic human associations with a Mean Average Precision (MAP) of 39.9 % and a Recall@10 of 63.9 %.
Covering segments with unit squares
Venue: arXiv cs.CG 2016
Year: 2016

We study several variations of line segment covering problem with axis-parallel unit squares in $I\!\!R^2$. A set $S$ of $n$ line segments is given. The objective is to find the minimum number of axis-parallel unit squares which cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP-complete, and give constant factor approximation algorithms for those problems. For some variations, we have polynomial time exact algorithms. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a factor 16 approximation result based on multilevel linear programming relaxation technique, which may be useful for solving some other problems. Further, we show that our problems have connections with the problems studied by Arkin et al. 2015 on conflict-free covering problem. Our NP-completeness results hold for more simplified types of objects than those of Arkin et al. 2015.
Students' patterns of interaction with a mathematics intelligent tutor: Learning analytics application
Venue: arXiv cs.CY 2016
Year: 2016

The purpose of this paper is to determine potential identifiers of students' academic success in foundation mathematics course from the data logs of an intelligent tutor. A cross-sectional study design was used. A sample of 58 records was extracted from the data-logs of an intelligent tutor, Assessment for Learning using Knowledge Spaces (ALEKS). This data was triangulated with the data collected from surveys. Two-step clustering, regression analysis, paired-sample t-tests were applied to address the research questions. The data-logs of ALEKS include information about number of topics practiced and number of topics mastered. A derived attribute, which is the ratio of number of topics mastered to number of topics practiced is found to be a predictor of final marks. Students' prior knowledge and this derived attribute are predictors of final grades with R square=42%. Students were asked to report their preferred way of selecting topics as either sequential or random. Results of paired sample t-test demonstrated that the students who selected topics in sequential manner were able to retain their mastery of learning after the summative assessment whereas the students who chose topics randomly were not able to retain their mastery of learning.
Estimating Activity at Multiple Scales using Spatial Abstractions
Venue: arXiv cs.AI 2016
Year: 2016

Autonomous robots operating in dynamic environments must maintain beliefs over a hypothesis space that is rich enough to represent the activities of interest at different scales. This is important both in order to accommodate the availability of evidence at varying degrees of coarseness, such as when interpreting and assimilating natural instructions, but also in order to make subsequent reactive planning more efficient. We present an algorithm that combines a topology-based trajectory clustering procedure that generates hierarchically-structured spatial abstractions with a bank of particle filters at each of these abstraction levels so as to produce probability estimates over an agent's navigation activity that is kept consistent across the hierarchy. We study the performance of the proposed method using a synthetic trajectory dataset in 2D, as well as a dataset taken from AIS-based tracking of ships in an extended harbour area. We show that, in comparison to a baseline which is a particle filter that estimates activity without exploiting such structure, our method achieves a better normalised error in predicting the trajectory as well as better time to convergence to a true class when compared against ground truth.
An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level, Small Field Size and All-Node Repair
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents an explicit construction for an $((n,k,d=n-1), (α,β))$ regenerating code over a field $\mathbb{F}_Q$ operating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate $k/n$ as close to $1$ as desired, sub-packetization given by $r^{\frac{n}{r}}$, for $r=(n-k)$, field size no larger than $n$ and where all code symbols can be repaired with the same minimum data download. The construction modifies a prior construction by Sasidharan et. al. which required far larger field-size. A building block appearing in the construction is a scalar MDS code of block length $n$. The code has a simple layered structure with coupling across layers, that allows both node repair and data recovery to be carried out by making multiple calls to a decoder for the scalar MDS code. While this work was carried out independently, there is considerable overlap with a prior construction by Ye and Barg. It is shown here that essentially the same architecture can be employed to construct MSR codes using vector binary MDS codes as building blocks in place of scalar MDS codes. The advantage here is that computations can now be carried out over a field of smaller size potentially even over the binary field as we demonstrate in an example. Further, we show how the construction can be extended to handle the case of $d<(n-1)$ under a mild restriction on the choice of helper nodes.
On the Ubiquity of Web Tracking: Insights from a Billion-Page Web Crawl
Venue: arXiv cs.SI 2016
Year: 2016

We perform a large-scale analysis of third-party trackers on the World Wide Web from more than 3.5 billion web pages of the CommonCrawl 2012 corpus. We extract a dataset containing more than 140 million third-party embeddings in over 41 million domains. To the best of our knowledge, this constitutes the largest web tracking dataset collected so far, and exceeds related studies by more than an order of magnitude in the number of domains and web pages analyzed. We perform a large-scale study of online tracking, on three levels: (1) On a global level, we give a precise figure for the extent of tracking, give insights into the structure of the `online tracking sphere' and analyse which trackers are used by how many websites. (2) On a country-specific level, we analyse which trackers are used by websites in different countries, and identify the countries in which websites choose significantly different trackers than in the rest of the world. (3) We answer the question whether the content of websites influences the choice of trackers they use, leveraging more than 90 thousand categorized domains. In particular, we analyse whether highly privacy-critical websites make different choices of trackers than other websites. Based on the performed analyses, we confirm that trackers are widespread (as expected), and that a small number of trackers dominates the web (Google, Facebook and Twitter). In particular, the three tracking domains with the highest PageRank are all owned by Google. The only exception to this pattern are a few countries such as China and Russia. Our results suggest that this dominance is strongly associated with country-specific political factors such as freedom of the press. We also confirm that websites with highly privacy-critical content are less likely to contain trackers (60% vs 90% for other websites), even though the majority of them still do contain trackers.
gvnn: Neural Network Library for Geometric Computer Vision
Venue: arXiv cs.CV 2016
Year: 2016

We introduce gvnn, a neural network library in Torch aimed towards bridging the gap between classic geometric computer vision and deep learning. Inspired by the recent success of Spatial Transformer Networks, we propose several new layers which are often used as parametric transformations on the data in geometric computer vision. These layers can be inserted within a neural network much in the spirit of the original spatial transformers and allow backpropagation to enable end-to-end learning of a network involving any domain knowledge in geometric computer vision. This opens up applications in learning invariance to 3D geometric transformation for place recognition, end-to-end visual odometry, depth estimation and unsupervised learning through warping with a parametric transformation for image reconstruction error.
Cascading Node Failure with Continuous States in Random Geometric Networks
Venue: arXiv cs.SI 2016
Year: 2016

The increasing complexity and interdependency of today's networks highlight the importance of studying network robustness to failure and attacks. Many large-scale networks are prone to cascading effects where a limited number of initial failures (due to attacks, natural hazards or resource depletion) propagate through a dependent mechanism, ultimately leading to a global failure scenario where a substantial fraction of the network loses its functionality. These cascading failure scenarios often take place in networks which are embedded in space and constrained by geometry. Building on previous results on cascading failure in random geometric networks, we introduce and analyze a continuous cascading failure model where a node has an initial continuously-valued state, and fails if the aggregate state of its neighbors fall below a threshold. Within this model, we derive analytical conditions for the occurrence and non-occurrence of cascading node failure, respectively.