OpenRaiser/Intern-Atlas huggingface dataset:
Ad Exchange: Envy-Free Auctions with Mediators
Venue: arXiv cs.GT 2016
Year: 2016

Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a "local" auction to resell the obtained ad slots among its advertisers. In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.
On Efficient Decoding and Design of Sparse Random Linear Network Codes
Venue: arXiv cs.IT 2016
Year: 2016

Random linear network coding (RLNC) in theory achieves the max-flow capacity of multicast networks, at the cost of high decoding complexity. To improve the performance-complexity tradeoff, we consider the design of sparse network codes. A generation-based strategy is employed in which source packets are grouped into overlapping subsets called generations. RLNC is performed only amongst packets belonging to the same generation throughout the network so that sparseness can be maintained. In this paper, generation-based network codes with low reception overheads and decoding costs are designed for transmitting of the order of $10^2$-$10^3$ source packets. A low-complexity overhead-optimized decoder is proposed that exploits "overlaps" between generations. The sparseness of the codes is exploited through local processing and multiple rounds of pivoting of the decoding matrix. To demonstrate the efficacy of our approach, codes comprising a binary precode, random overlapping generations, and binary RLNC are designed. The results show that our designs can achieve negligible code overheads at low decoding costs, and outperform existing network codes that use the generation based strategy.
Right whale recognition using convolutional neural networks
Venue: arXiv cs.CV 2016
Year: 2016

We studied the feasibility of recognizing individual right whales (Eubalaena glacialis) using convolutional neural networks. Prior studies have shown that CNNs can be used in wide range of classification and categorization tasks such as automated human face recognition. To test applicability of deep learning to whale recognition we have developed several models based on best practices from literature. Here, we describe the performance of the models. We conclude that machine recognition of whales is feasible and comment on the difficulty of the problem
Resource Allocation in Heterogeneous Networks: eICIC Approach
Venue: arXiv cs.NI 2016
Year: 2016

Heterogeneous Networks (HetNets) are introduced by the 3GPP as an emerging technology to provide high network coverage and capacity. The HetNets are the combination of multilayer networks such as macrocell, small cell (picocell and femtocell) networks. In such networks, users may suffer significant cross-layer interference. To manage the interference the 3GPP has introduced Enhanced Inter-Cell Interference Coordination (eICIC) techniques, Almost Blank SubFrame (ABSF) is one of the time-domain technique in the eICIC solutions. In this thesis, we propose a dynamically optimal ABSF framework to enhance the small cell user downlink performance while maintains the macro user downlink performance. We also study the mechanism to help the small cell base stations cooperate efficiently in order to reduce the mutual interference. Via numerical results, our proposed scheme achieves a significant performance and outperforms the existing ABSF frameworks in terms of user throughput and outage probability.
First Experimental Demonstration of Secure NFV Orchestration over an SDN-Controlled Optical Network with Time-Shared Quantum Key Distribution Resources
Venue: arXiv cs.CR 2016
Year: 2016

We demonstrate, for the first time, a secure optical network architecture that combines NFV orchestration and SDN control with quantum key distribution (QKD) technology. A novel time-shared QKD network design is presented as a cost-effective solution for practical networks.
Distributed Entity Disambiguation with Per-Mention Learning
Venue: arXiv cs.CL 2016
Year: 2016

Entity disambiguation, or mapping a phrase to its canonical representation in a knowledge base, is a fundamental step in many natural language processing applications. Existing techniques based on global ranking models fail to capture the individual peculiarities of the words and hence, either struggle to meet the accuracy requirements of many real-world applications or they are too complex to satisfy real-time constraints of applications. In this paper, we propose a new disambiguation system that learns specialized features and models for disambiguating each ambiguous phrase in the English language. To train and validate the hundreds of thousands of learning models for this purpose, we use a Wikipedia hyperlink dataset with more than 170 million labelled annotations. We provide an extensive experimental evaluation to show that the accuracy of our approach compares favourably with respect to many state-of-the-art disambiguation systems. The training required for our approach can be easily distributed over a cluster. Furthermore, updating our system for new entities or calibrating it for special ones is a computationally fast process, that does not affect the disambiguation of the other entities.
Using Binoculars for Fast Exploration and Map Construction in Chordal Graphs and Extensions
Venue: arXiv cs.DC 2016
Year: 2016

We investigate the exploration and mapping of anonymous graphs by a mobile agent. It is long known that, without global information about the graph, it is not possible to make the agent halt after the exploration except if the graph is a tree. We therefore endow the agent with binoculars, a sensing device that can show the local structure of the environment at a constant distance of the agent's current location and investigate networks that can be efficiently explored in this setting. In the case of trees, the exploration without binoculars is fast (i.e. using a DFS traversal of the graph, there is a number of moves linear in the number of nodes). We consider here the family of Weetman graphs that is a generalization of the standard family of chordal graphs and present a new deterministic algorithm that realizes Exploration of any Weetman graph, without knowledge of size or diameter and for any port numbering. The number of moves is linear in the number of nodes, despite the fact that Weetman graphs are not sparse, some having a number of edges that is quadratic in the number of nodes. At the end of the Exploration, the agent has also computed a map of the anonymous graph.
Reconstructing a website's lost past: Methodological issues concerning the history of www.unibo.it
Venue: arXiv cs.DL 2016
Year: 2016

This paper describes how born digital primary sources could be used to reconstruct the recent history of scientific institutions. The case study is an analysis of the first 25 years online of the University of Bologna. The focus of this work is primarily methodological: several different issues are presented, starting with the fact that the University of Bologna website has been excluded for thirteen years from the Internet Archive's Wayback Machine, and possible solutions are proposed and applied. The article is organised in three parts: in the first one, some of the fundamental concepts on web archives and the preservation of born digital sources are introduced. Then the reconstruction of the University of Bologna web's past is presented. Finally the future of this research is described, presenting a specific case study in which the historian's craft will be challenged by a completely different issue, namely the large amount of data available in the university digital library.
Practical combinations of repetition-aware data structures
Venue: arXiv cs.DS 2016
Year: 2016

Highly-repetitive collections of strings are increasingly being amassed by genome sequencing and genetic variation experiments, as well as by storing all versions of human-generated files, like webpages and source code. Existing indexes for locating all the exact occurrences of a pattern in a highly-repetitive string take advantage of a single measure of repetition. However, multiple, distinct measures of repetition all grow sublinearly in the length of a highly-repetitive string. In this paper we explore the practical advantages of combining data structures whose size depends on distinct measures of repetition. The main ingredient of our structures is the run-length encoded BWT (RLBWT), which takes space proportional to the number of runs in the Burrows-Wheeler transform of a string. We describe a range of practical variants that combine RLBWT with the set of boundaries of the Lempel-Ziv 77 factors of a string, which take space proportional to the number of factors. Such variants use, respectively, the RLBWT of a string and the RLBWT of its reverse, or just one RLBWT inside a bidirectional index, or just one RLBWT with support for unidirectional extraction. We also study the practical advantages of combining RLBWT with the compact directed acyclic word graph of a string, a data structure that takes space proportional to the number of one-character extensions of maximal repeats. Our approaches are easy to implement, and provide competitive tradeoffs on significant datasets.
$μ$Kummer: efficient hyperelliptic signatures and key exchange on microcontrollers
Venue: arXiv cs.CR 2016
Year: 2016

We describe the design and implementation of efficient signature and key-exchange schemes for the AVR ATmega and ARM Cortex M0 microcontrollers, targeting the 128-bit security level. Our algorithms are based on an efficient Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and Schost's genus-2 hyperelliptic curve, combined with the Jacobian point recovery technique of Costello, Chung, and Smith. Our results are the first to show the feasibility of software-only hyperelliptic cryptography on constrained platforms, and represent a significant improvement on the elliptic-curve state-of-the-art for both key exchange and signatures on these architectures. Notably, our key-exchange scalar-multiplication software runs in under 9740k cycles on the ATmega, and under 2650k cycles on the Cortex M0.
Nonexistence of a few binary orthogonal arrays
Venue: arXiv cs.IT 2016
Year: 2016

We develop and apply combinatorial algorithms for investigation of the feasible distance distributions of binary orthogonal arrays with respect to a point of the ambient binary Hamming space utilizing constraints imposed from the relations between the distance distributions of connected arrays. This turns out to be strong enough and we prove the nonexistence of binary orthogonal arrays of parameters (length, cardinality, strength)$\ =(9,6.2^4=96,4)$, $(10,6.2^5,5)$, $(10,7.2^4=112,4)$, $(11,7.2^5,5)$, $(11,7.2^4,4)$ and $(12,7.2^5,5)$, resolving the first cases where the existence was undecided so far. For the existing arrays our approach allows substantial reduction of the number of feasible distance distributions which could be helpful for classification results (uniqueness, for example).
Augmented Body: Changing Interactive Body Play
Venue: arXiv cs.HC 2016
Year: 2016

This paper investigates the player's body as a system capable of unfamiliar interactive movement achieved through digital mediation in a playful environment. Body interactions in both digital and non-digital environments can be considered as a perceptually manipulative exploration of self. This implies a player may alter how they perceive their body and its operations in order to create a new playful and original experience. This paper therefore questions how player interaction can change as their perception of their body changes using augmentative technology.
OCR Error Correction Using Character Correction and Feature-Based Word Classification
Venue: arXiv cs.IR 2016
Year: 2016

This paper explores the use of a learned classifier for post-OCR text correction. Experiments with the Arabic language show that this approach, which integrates a weighted confusion matrix and a shallow language model, improves the vast majority of segmentation and recognition errors, the most frequent types of error on our dataset.
Novelty Detection in MultiClass Scenarios with Incomplete Set of Class Labels
Venue: arXiv cs.CV 2016
Year: 2016

We address the problem of novelty detection in multiclass scenarios where some class labels are missing from the training set. Our method is based on the initial assignment of confidence values, which measure the affinity between a new test point and each known class. We first compare the values of the two top elements in this vector of confidence values. In the heart of our method lies the training of an ensemble of classifiers, each trained to discriminate known from novel classes based on some partition of the training data into presumed-known and presumednovel classes. Our final novelty score is derived from the output of this ensemble of classifiers. We evaluated our method on two datasets of images containing a relatively large number of classes - the Caltech-256 and Cifar-100 datasets. We compared our method to 3 alternative methods which represent commonly used approaches, including the one-class SVM, novelty based on k-NN, novelty based on maximal confidence, and the recent KNFST method. The results show a very clear and marked advantage for our method over all alternative methods, in an experimental setup where class labels are missing during training.
Automatic Inference of Graph Transformation Rules Using the Cyclic Nature of Chemical Reactions
Venue: arXiv cs.DM 2016
Year: 2016

Graph transformation systems have the potential to be realistic models of chemistry, provided a comprehensive collection of reaction rules can be extracted from the body of chemical knowledge. A first key step for rule learning is the computation of atom-atom mappings, i.e., the atom-wise correspondence between products and educts of all published chemical reactions. This can be phrased as a maximum common edge subgraph problem with the constraint that transition states must have cyclic structure. We describe a search tree method well suited for small edit distance and an integer linear program best suited for general instances and demonstrate that it is feasible to compute atom-atom maps at large scales using a manually curated database of biochemical reactions as an example. In this context we address the network completion problem.
On the Capacity of Diffusion-Based Molecular Timing Channels
Venue: arXiv cs.IT 2016
Year: 2016

This work introduces capacity limits for molecular timing (MT) channels, where information is modulated on the release timing of small information particles, and decoded from the time of arrival at the receiver. It is shown that the random time of arrival can be represented as an additive noise channel, and for the diffusion-based MT (DBMT) channel, this noise is distributed according to the Lévy distribution. Lower and upper bounds on the capacity of the DBMT channel are derived for the case where the delay associated with the propagation of information particles in the channel is finite. These bounds are also shown to be tight.
HIRL: Hierarchical Inverse Reinforcement Learning for Long-Horizon Tasks with Delayed Rewards
Venue: arXiv cs.RO 2016
Year: 2016

Reinforcement Learning (RL) struggles in problems with delayed rewards, and one approach is to segment the task into sub-tasks with incremental rewards. We propose a framework called Hierarchical Inverse Reinforcement Learning (HIRL), which is a model for learning sub-task structure from demonstrations. HIRL decomposes the task into sub-tasks based on transitions that are consistent across demonstrations. These transitions are defined as changes in local linearity w.r.t to a kernel function. Then, HIRL uses the inferred structure to learn reward functions local to the sub-tasks but also handle any global dependencies such as sequentiality. We have evaluated HIRL on several standard RL benchmarks: Parallel Parking with noisy dynamics, Two-Link Pendulum, 2D Noisy Motion Planning, and a Pinball environment. In the parallel parking task, we find that rewards constructed with HIRL converge to a policy with an 80% success rate in 32% fewer time-steps than those constructed with Maximum Entropy Inverse RL (MaxEnt IRL), and with partial state observation, the policies learned with IRL fail to achieve this accuracy while HIRL still converges. We further find that that the rewards learned with HIRL are robust to environment noise where they can tolerate 1 stdev. of random perturbation in the poses in the environment obstacles while maintaining roughly the same convergence rate. We find that HIRL rewards can converge up-to 6x faster than rewards constructed with IRL.
A Classifier-guided Approach for Top-down Salient Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

We propose a framework for top-down salient object detection that incorporates a tightly coupled image classification module. The classifier is trained on novel category-aware sparse codes computed on object dictionaries used for saliency modeling. A misclassification indicates that the corresponding saliency model is inaccurate. Hence, the classifier selects images for which the saliency models need to be updated. The category-aware sparse coding produces better image classification accuracy as compared to conventional sparse coding with a reduced computational complexity. A saliency-weighted max-pooling is proposed to improve image classification, which is further used to refine the saliency maps. Experimental results on Graz-02 and PASCAL VOC-07 datasets demonstrate the effectiveness of salient object detection. Although the role of the classifier is to support salient object detection, we evaluate its performance in image classification and also illustrate the utility of thresholded saliency maps for image segmentation.
CT-Mapper: Mapping Sparse Multimodal Cellular Trajectories using a Multilayer Transportation Network
Venue: arXiv cs.SI 2016
Year: 2016

Mobile phone data have recently become an attractive source of information about mobility behavior. Since cell phone data can be captured in a passive way for a large user population, they can be harnessed to collect well-sampled mobility information. In this paper, we propose CT-Mapper, an unsupervised algorithm that enables the mapping of mobile phone traces over a multimodal transport network. One of the main strengths of CT-Mapper is its capability to map noisy sparse cellular multimodal trajectories over a multilayer transportation network where the layers have different physical properties and not only to map trajectories associated with a single layer. Such a network is modeled by a large multilayer graph in which the nodes correspond to metro/train stations or road intersections and edges correspond to connections between them. The mapping problem is modeled by an unsupervised HMM where the observations correspond to sparse user mobile trajectories and the hidden states to the multilayer graph nodes. The HMM is unsupervised as the transition and emission probabilities are inferred using respectively the physical transportation properties and the information on the spatial coverage of antenna base stations. To evaluate CT-Mapper we collected cellular traces with their corresponding GPS trajectories for a group of volunteer users in Paris and vicinity (France). We show that CT-Mapper is able to accurately retrieve the real cell phone user paths despite the sparsity of the observed trace trajectories. Furthermore our transition probability model is up to 20% more accurate than other naive models.
DISSECT-CF: a simulator to foster energy-aware scheduling in infrastructure clouds
Venue: arXiv cs.DC 2016
Year: 2016

Infrastructure as a service (IaaS) systems offer on demand virtual infrastructures so reliably and flexibly that users expect a high service level. Therefore, even with regards to internal IaaS behaviour, production clouds only adopt novel ideas that are proven not to hinder established service levels. To analyse their expected behaviour, new ideas are often evaluated with simulators in production IaaS system-like scenarios. For instance, new research could enable collaboration amongst several layers of schedulers or could consider new optimisation objectives such as energy consumption. Unfortunately, current cloud simulators are hard to employ and they often have performance issues when several layers of schedulers interact in them. To target these issues, a new IaaS simulation framework (called DISSECT-CF) was designed. The new simulator's foundation has the following goals: easy extensibility, support energy evaluation of IaaSs and to enable fast evaluation of many scheduling and IaaS internal behaviour related scenarios. In response to the requirements of such scenarios, the new simulator introduces concepts such as: a unified model for resource sharing and a new energy metering framework with hierarchical and indirect metering options. Then, the comparison of several simulated situations to real-life IaaS behaviour is used to validate the simulator's functionality. Finally, a performance comparison is presented between DISSECT-CF and some currently available simulators.
Descriptive Complexity of $\#\textrm{AC}^0$ Functions
Venue: arXiv cs.CC 2016
Year: 2016

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.
Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we describe Compact-Table (CT), a bitwise algorithm to enforce Generalized Arc Consistency (GAC) on table con- straints. Although this algorithm is the default propagator for table constraints in or-tools and OscaR, two publicly available CP solvers, it has never been described so far. Importantly, CT has been recently improved further with the introduction of residues, resetting operations and a data-structure called reversible sparse bit-set, used to maintain tables of supports (following the idea of tabular reduction): tuples are invalidated incrementally on value removals by means of bit-set operations. The experimentation that we have conducted with OscaR shows that CT outperforms state-of-the-art algorithms STR2, STR3, GAC4R, MDD4R and AC5-TC on standard benchmarks.