OpenRaiser/Intern-Atlas huggingface dataset:
PageRank Approach to Ranking National Football Teams
Venue: arXiv cs.SI 2015
Year: 2015

The Football World Cup as world's favorite sporting event is a source of both entertainment and overwhelming amount of data about the games played. In this paper we analyse the available data on football world championships since 1930 until today. Our goal is to rank the national teams based on all matches during the championships. For this purpose, we apply the PageRank with restarts algorithm to a graph built from the games played during the tournaments. Several statistics such as matches won and goals scored are combined in different metrics that assign weights to the links in the graph. Finally, our results indicate that the Random walk approach with the use of right metrics can indeed produce relevant rankings comparable to the FIFA official all-time ranking board.
BVNS para el problema del bosque generador k-etiquetado
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we propose an efficient solution for the problem of generating k-labeling forest VNS. This problem is an extension of the Minimum Spanning Tree Problem Labelling problem with important applications in telecommunications networks and multimodal transport. It is, given an undirected graph whose links are labeled, and an integer positive number k, find the spanning forest with the lowest number of connected components using at most k different labels. To address the problem a Basic Variable Neighbourhood Search is proposed where the maximum amplitude of the neighbourhood space, n, is a key parameter. Different strategies are studied to establish the value of n. BVNS with the best selected strategy is experimentally compared with other metaheuristics that have appeared in the literature applied to this type of problem.
Saturated simple and 2-simple topological graphs with few edges
Venue: arXiv cs.CG 2015
Year: 2015

A simple topological graph is a topological graph in which any two edges have at most one common point, which is either their common endpoint or a proper crossing. More generally, in a k-simple topological graph, every pair of edges has at most k common points of this kind. We construct saturated simple and 2-simple graphs with few edges. These are k-simple graphs in which no further edge can be added. We improve the previous upper bounds of Kynčl, Pach, Radoičić, and Tóth and show that there are saturated simple graphs on n vertices with only 7n edges and saturated 2-simple graphs on n vertices with 14.5n edges. As a consequence, 14.5n edges is also a new upper bound for k-simple graphs (considering all values of k). We also construct saturated simple and 2-simple graphs that have some vertices with low degree.
Node.DPWS: High performance and scalable Web Services for the IoT
Venue: arXiv cs.NI 2015
Year: 2015

Interconnected computing systems, in various forms, are expected to permeate our lives, realizing the vision of the Internet of Things (IoT) and allowing us to enjoy novel, enhanced services that promise to improve our everyday lives. Nevertheless, this new reality also introduces significant challenges in terms of performance, scaling, usability and interoperability. Leveraging the benefits of Service Oriented Architectures (SOAs) can help alleviate many of the issues that developers, implementers and end-users have to face in the context of the IoT. This work presents Node.DPWS, a novel implementation of the Devices Profile for Web Services (DPWS) based on the Node.js platform. Node.DPWS can be used to deploy lightweight, efficient and scalable Web Services over heterogeneous nodes, including devices with limited resources. The performance of the presented work is evaluated on typical embedded devices, including comparisons with implementations created using alternative DPWS toolkits.
Deterministic construction of sparse binary and ternary matrices from existing binary sensing matrices
Venue: arXiv cs.IT 2015
Year: 2015

In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed.
A Blind Zone Alert System based on Intra-vehicular Wireless Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Due to the increasing number of sensors deployed in modern vehicles, Intra-Vehicular Wireless Sensor Networks (IVWSNs) have recently received a lot of attention in the automotive industry as they can reduce the amount of wiring harness inside a vehicle. By removing the wires, car manufacturers can reduce the weight of a vehicle and improve engine performance, fuel economy, and reliability. In addition to these direct benefits, an IVWSN is a versatile platform that can support other vehicular applications as well. An example application, known as a Side Blind Zone Alert (SBZA) system, which monitors the blind zone of the vehicle and alerts the driver in a timely manner to prevent collisions, is discussed in this paper. The performance of the IVWSN-based SBZA system is evaluated via real experiments conducted on two test vehicles. Our results show that the proposed system can achieve approximately 95% to 99% detection rate with less than 15% false alarm rate. Compared to commercial systems using radars or cameras, the main benefit of the IVWSN-based SBZA is substantially lower cost.
Random Serial Dictatorship versus Probabilistic Serial Rule: A Tale of Two Random Mechanisms
Venue: arXiv cs.GT 2015
Year: 2015

For assignment problems where agents, specifying ordinal preferences, are allocated indivisible objects, two widely studied randomized mechanisms are the Random Serial Dictatorship (RSD) and Probabilistic Serial Rule (PS). These two mechanisms both have desirable economic and computational properties, but the outcomes they induce can be incomparable in many instances, thus creating challenges in deciding which mechanism to adopt in practice. In this paper we first look at the space of lexicographic preferences and show that, as opposed to the general preference domain, RSD satisfies envyfreeness. Moreover, we show that although under lexicographic preferences PS is strategyproof when the number of objects is less than or equal agents, it is strictly manipulable when there are more objects than agents. In the space of general preferences, we provide empirical results on the (in)comparability of RSD and PS, analyze economic properties, and provide further insights on the applicability of each mechanism in different application domains.
Space proof complexity for random 3-CNFs
Venue: arXiv cs.CC 2015
Year: 2015

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random $3$-CNF $ϕ$ in $n$ variables requires, with high probability, $Ω(n)$ distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation $ϕ$ requires, with high probability, $Ω(n)$ clauses each of width $Ω(n)$ to be kept at the same time in memory. This gives a $Ω(n^2)$ lower bound for the total space needed in Resolution to refute $ϕ$. These results are best possible (up to a constant factor). The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs $G$ with bipartition $(L,R)$ and left-degree at most 3, $L$ can be covered by certain families of disjoint paths, called VW-matchings, provided that $L$ expands in $R$ by a factor of $(2-ε)$, for $ε< 1/23$.
Studying the Wikipedia Hyperlink Graph for Relatedness and Disambiguation
Venue: arXiv cs.CL 2015
Year: 2015

Hyperlinks and other relations in Wikipedia are a extraordinary resource which is still not fully understood. In this paper we study the different types of links in Wikipedia, and contrast the use of the full graph with respect to just direct links. We apply a well-known random walk algorithm on two tasks, word relatedness and named-entity disambiguation. We show that using the full graph is more effective than just direct links by a large margin, that non-reciprocal links harm performance, and that there is no benefit from categories and infoboxes, with coherent results on both tasks. We set new state-of-the-art figures for systems based on Wikipedia links, comparable to systems exploiting several information sources and/or supervised machine learning. Our approach is open source, with instruction to reproduce results, and amenable to be integrated with complementary text-based methods.
How friends and non-determinism affect opinion dynamics
Venue: arXiv cs.DS 2015
Year: 2015

The Hegselmann-Krause system (HK system for short) is one of the most popular models for the dynamics of opinion formation in multiagent systems. Agents are modeled as points in opinion space, and at every time step, each agent moves to the mass center of all the agents within unit distance. The rate of convergence of HK systems has been the subject of several recent works. In this work, we investigate two natural variations of the HK system and their effect on the dynamics. In the first variation, we only allow pairs of agents who are friends in an underlying social network to communicate with each other. In the second variation, agents may not move exactly to the mass center but somewhere close to it. The dynamics of both variants are qualitatively very different from that of the classical HK system. Nevertheless, we prove that both these systems converge in polynomial number of non-trivial steps, regardless of the social network in the first variant and noise patterns in the second variant.
Optimally Combining Classifiers Using Unlabeled Data
Venue: arXiv cs.LG 2015
Year: 2015

We develop a worst-case analysis of aggregation of classifier ensembles for binary classification. The task of predicting to minimize error is formulated as a game played over a given set of unlabeled data (a transductive setting), where prior label information is encoded as constraints on the game. The minimax solution of this game identifies cases where a weighted combination of the classifiers can perform significantly better than any single classifier.
Latent Hierarchical Model for Activity Recognition
Venue: arXiv cs.RO 2015
Year: 2015

We present a novel hierarchical model for human activity recognition. In contrast to approaches that successively recognize actions and activities, our approach jointly models actions and activities in a unified framework, and their labels are simultaneously predicted. The model is embedded with a latent layer that is able to capture a richer class of contextual information in both state-state and observation-state pairs. Although loops are present in the model, the model has an overall linear-chain structure, where the exact inference is tractable. Therefore, the model is very efficient in both inference and learning. The parameters of the graphical model are learned with a Structured Support Vector Machine (Structured-SVM). A data-driven approach is used to initialize the latent variables; therefore, no manual labeling for the latent states is required. The experimental results from using two benchmark datasets show that our model outperforms the state-of-the-art approach, and our model is computationally more efficient.
Ranking and significance of variable-length similarity-based time series motifs
Venue: arXiv cs.LG 2015
Year: 2015

The detection of very similar patterns in a time series, commonly called motifs, has received continuous and increasing attention from diverse scientific communities. In particular, recent approaches for discovering similar motifs of different lengths have been proposed. In this work, we show that such variable-length similarity-based motifs cannot be directly compared, and hence ranked, by their normalized dissimilarities. Specifically, we find that length-normalized motif dissimilarities still have intrinsic dependencies on the motif length, and that lowest dissimilarities are particularly affected by this dependency. Moreover, we find that such dependencies are generally non-linear and change with the considered data set and dissimilarity measure. Based on these findings, we propose a solution to rank those motifs and measure their significance. This solution relies on a compact but accurate model of the dissimilarity space, using a beta distribution with three parameters that depend on the motif length in a non-linear way. We believe the incomparability of variable-length dissimilarities could go beyond the field of time series, and that similar modeling strategies as the one used here could be of help in a more broad context.
Natural Notation for the Domestic Internet of Things
Venue: arXiv cs.HC 2015
Year: 2015

This study explores the use of natural language to give instructions that might be interpreted by Internet of Things (IoT) devices in a domestic `smart home' environment. We start from the proposition that reminders can be considered as a type of end-user programming, in which the executed actions might be performed either by an automated agent or by the author of the reminder. We conducted an experiment in which people wrote sticky notes specifying future actions in their home. In different conditions, these notes were addressed to themselves, to others, or to a computer agent.We analyse the linguistic features and strategies that are used to achieve these tasks, including the use of graphical resources as an informal visual language. The findings provide a basis for design guidance related to end-user development for the Internet of Things.
Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata
Venue: arXiv cs.DC 2015
Year: 2015

We consider a solution of automata similar to Population Protocols and Network Constructors. The automata (or nodes) move passively in a well-mixed solution and can cooperate by interacting in pairs. Every such interaction may result in an update of the local states of the nodes. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. We may think of such nodes as the smallest possible programmable pieces of matter. The model that we introduce here is a more applied version of Network Constructors, imposing physical (or geometrical) constraints on the connections. Each node can connect to other nodes only via a very limited number of local ports, therefore at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. We show that this restricted model is still capable of forming very practical 2D or 3D shapes. We provide direct constructors for some basic shape construction problems. We then develop new techniques for determining the constructive capabilities of our model. One of the main novelties of our approach, concerns our attempt to overcome the inability of such systems to detect termination. In particular, we exploit the assumptions that the system is well-mixed and has a unique leader, in order to give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size $n$ of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that the nodes can self-organize w.h.p. into arbitrarily complex shapes while still detecting termination of the construction.
Reliable SVD based Semi-blind and Invisible Watermarking Schemes
Venue: arXiv cs.MM 2015
Year: 2015

A semi-blind watermarking scheme is presented based on Singular Value Decomposition (SVD), which makes essential use of the fact that, the SVD subspace preserves significant amount of information of an image and is a one way decomposition. The principal components are used, along with the corresponding singular vectors of the watermark image to watermark the target image. For further security, the semi-blind scheme is extended to an invisible hash based watermarking scheme. The hash based scheme commits a watermark with a key such that, it is incoherent with the actual watermark, and can only be extracted using the key. Its security is analyzed in the random oracle model and shown to be unforgeable, invisible and satisfying the property of non-repudiation.
A Uniform Substitution Calculus for Differential Dynamic Logic
Venue: arXiv cs.LO 2015
Year: 2015

This paper introduces a new proof calculus for differential dynamic logic (dL) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a predicate symbol everywhere. Uniform substitutions make it possible to rely on axioms rather than axiom schemata, substantially simplifying implementations. Instead of nontrivial schema variables and soundness-critical side conditions on the occurrence patterns of variables, the resulting calculus adopts only a finite number of ordinary dL formulas as axioms. The static semantics of differential dynamic logic is captured exclusively in uniform substitutions and bound variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this paper introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivations as first-class axioms in dL.
An Improved Image Mosaicing Algorithm for Damaged Documents
Venue: arXiv cs.CV 2015
Year: 2015

It is a common phenomenon in day to day life; where in some of the document gets damaged. Out of several reasons, the main reason for documents getting damaged is shredding by hands. Recovery of such documents is essential. Manual recovery of such damaged document is tedious and time consuming task. In this paper, we are describing an algorithm which recovers the original document from such shredded pieces of the same. In order to implement this, we are using a simple technique called Image Mosaicing. In this technique a complete new image is developed using two or more torn fragments. For simplicity of implementation, we are considering only two torn pieces of a document that will be mosaiced together. The successful implementation of this algorithm would lead to recovery of important information which in turn would be beneficial in various fields such as forensic sciences, archival study, etc
A Nonconvex Approach for Structured Sparse Learning
Venue: arXiv cs.IT 2015
Year: 2015

Sparse learning is an important topic in many areas such as machine learning, statistical estimation, signal processing, etc. Recently, there emerges a growing interest on structured sparse learning. In this paper we focus on the $\ell_q$-analysis optimization problem for structured sparse learning ($0< q \leq 1$). Compared to previous work, we establish weaker conditions for exact recovery in noiseless case and a tighter non-asymptotic upper bound of estimate error in noisy case. We further prove that the nonconvex $\ell_q$-analysis optimization can do recovery with a lower sample complexity and in a wider range of cosparsity than its convex counterpart. In addition, we develop an iteratively reweighted method to solve the optimization problem under the variational framework. Theoretical analysis shows that our method is capable of pursuing a local minima close to the global minima. Also, empirical results of preliminary computational experiments illustrate that our nonconvex method outperforms both its convex counterpart and other state-of-the-art methods.
Uplink Performance Evaluation of Massive MU-MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

The present paper deals with an OFDM-based uplink within a multi-user MIMO (MU-MIMO) system where a massive MIMO approach is employed. In this context, the linear detectors Minimum Mean-Squared Error (MMSE), Zero Forcing (ZF) and Maximum Ratio Combining (MRC) are considered and assessed. This papers includes Bit Error Rate (BER) results for uncoded QPSK/OFDM transmissions through a flat Rayleigh fading channel under the assumption of perfect power control and channel estimation. BER results are obtained through Monte Carlo simulations. Performance results are discussed in detail and we confirm the achievable "massive MIMO" effects, even for a reduced complexity detection technique, when the number of receive antennas at BS is much larger than the number of transmit antennas.
Player Behavior and Optimal Team Composition for Online Multiplayer Games
Venue: arXiv cs.SI 2015
Year: 2015

We consider clustering player behavior and learning the optimal team composition for multiplayer online games. The goal is to determine a set of descriptive play style groupings and learn a predictor for win/loss outcomes. The predictor takes in as input the play styles of the participants in each team; i.e., the various team compositions in a game. Our framework uses unsupervised learning to find behavior clusters, which are, in turn, used with classification algorithms to learn the outcome predictor. For our numerical experiments, we consider League of Legends, a popular team-based role-playing game developed by Riot Games. We observe the learned clusters to not only corroborate well with game knowledge, but also provide insights surprising to expert players. We also demonstrate that game outcomes can be predicted with fairly high accuracy given team composition-based features.
Exploiting Device-to-Device Communications in Joint Scheduling of Access and Backhaul for mmWave Small Cells
Venue: arXiv cs.NI 2015
Year: 2015

With the explosive growth of mobile data demand, there has been an increasing interest in deploying small cells of higher frequency bands underlying the conventional homogeneous macrocell network, which is usually referred to as heterogeneous cellular networks, to significantly boost the overall network capacity. With vast amounts of spectrum available in the millimeter wave (mmWave) band, small cells at mmWave frequencies are able to provide multi-gigabit access data rates, while the wireless backhaul in the mmWave band is emerging as a cost-effective solution to provide high backhaul capacity to connect access points (APs) of the small cells. In order to operate the mobile network optimally, it is necessary to jointly design the radio access and backhaul networks. Meanwhile, direct transmissions between devices should also be considered to improve system performance and enhance the user experience. In this paper, we propose a joint transmission scheduling scheme for the radio access and backhaul of small cells in the mmWave band, termed D2DMAC, where a path selection criterion is designed to enable device-to-device transmissions for performance improvement. In D2DMAC, a concurrent transmission scheduling algorithm is proposed to fully exploit spatial reuse in mmWave networks. Through extensive simulations under various traffic patterns and user deployments, we demonstrate D2DMAC achieves near-optimal performance in some cases, and outperforms other protocols significantly in terms of delay and throughput. Furthermore, we also analyze the impact of path selection on the performance improvement of D2DMAC under different selected parameters.