OpenRaiser/Intern-Atlas huggingface dataset:
Counting and Enumerating Crossing-free Geometric Graphs
Venue: arXiv cs.CG 2016
Year: 2016

We describe a framework for counting and enumerating various types of crossing-free geometric graphs on a planar point set. The framework generalizes ideas of Alvarez and Seidel, who used them to count triangulations in time $O(2^nn^2)$ where $n$ is the number of points. The main idea is to reduce the problem of counting geometric graphs to counting source-sink paths in a directed acyclic graph. The following new results will emerge. The number of all crossing-free geometric graphs can be computed in time $O(c^nn^4)$ for some $c < 2.83929$. The number of crossing-free convex partitions can be computed in time $O(2^nn^4)$. The number of crossing-free perfect matchings can be computed in time $O(2^nn^4)$. The number of convex subdivisions can be computed in time $O(2^nn^4)$. The number of crossing-free spanning trees can be computed in time $O(c^nn^4)$ for some $c < 7.04313$. The number of crossing-free spanning cycles can be computed in time $O(c^nn^4)$ for some $c < 5.61804$. With the same bounds on the running time we can construct data structures which allow fast enumeration of the respective classes. For example, after $O(2^nn^4)$ time of preprocessing we can enumerate the set of all crossing-free perfect matchings using polynomial time per enumerated object. For crossing-free perfect matchings and convex partitions we further obtain enumeration algorithms where the time delay for each (in particular, the first) output is bounded by a polynomial in $n$. All described algorithms are comparatively simple, both in terms of their analysis and implementation.
Permutations of context-free, ET0L and indexed languages
Venue: arXiv cs.FL 2016
Year: 2016

For a language $L$, we consider its cyclic closure, and more generally the language $C^k(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^k(L)$ is context-sensitive and not context-free in general for $k\geq 3$. We also show that the cyclic closure of an indexed language is indexed.
An Online Structural Plasticity Rule for Generating Better Reservoirs
Venue: arXiv cs.NE 2016
Year: 2016

In this article, a novel neuro-inspired low-resolution online unsupervised learning rule is proposed to train the reservoir or liquid of Liquid State Machine. The liquid is a sparsely interconnected huge recurrent network of spiking neurons. The proposed learning rule is inspired from structural plasticity and trains the liquid through formation and elimination of synaptic connections. Hence, the learning involves rewiring of the reservoir connections similar to structural plasticity observed in biological neural networks. The network connections can be stored as a connection matrix and updated in memory by using Address Event Representation (AER) protocols which are generally employed in neuromorphic systems. On investigating the 'pairwise separation property' we find that trained liquids provide 1.36 $\pm$ 0.18 times more inter-class separation while retaining similar intra-class separation as compared to random liquids. Moreover, analysis of the 'linear separation property' reveals that trained liquids are 2.05 $\pm$ 0.27 times better than random liquids. Furthermore, we show that our liquids are able to retain the 'generalization' ability and 'generality' of random liquids. A memory analysis shows that trained liquids have 83.67 $\pm$ 5.79 ms longer fading memory than random liquids which have shown 92.8 $\pm$ 5.03 ms fading memory for a particular type of spike train inputs. We also throw some light on the dynamics of the evolution of recurrent connections within the liquid. Moreover, compared to 'Separation Driven Synaptic Modification' - a recently proposed algorithm for iteratively refining reservoirs, our learning rule provides 9.30%, 15.21% and 12.52% more liquid separations and 2.8%, 9.1% and 7.9% better classification accuracies for four, eight and twelve class pattern recognition tasks respectively.
A wearable haptic game controller
Venue: arXiv cs.HC 2016
Year: 2016

This paper outlines the development of a wearable game controller incorporating vibrotacticle haptic feedback that provides a low cost, versatile and intuitive interface for controlling digital games. The device differs from many traditional haptic feedback implementation in that it combines vibrotactile based haptic feedback with gesture based input, thus becoming a two way conduit between the user and the virtual environment. The device is intended to challenge what is considered an "interface" and draws on work in the area of Actor-Network theory to purposefully blur the boundary between man and machine. This allows for a more immersive experience, so rather than making the user feel like they are controlling an aircraft the intuitive interface allows the user to become the aircraft that is controlled by the movements of the user's hand. This device invites playful action and thrill. It bridges new territory on portable and low cost solutions for haptic controllers in a gaming context.
Does Anonymity Increase the Chance to Get Feedback?
Venue: arXiv cs.HC 2016
Year: 2016

To generate a hypothesis about the effects of anonymity on user participation in online communities, comments on Youtube were analysed for effects of the change from allowing pseudonyms to Google+ with its real name policy. Small differences were detected, leading to the hypothesis that the option to remain anonymous leads to a less active environment for getting feedback, with less polite and less rude comments on the expense of neutral ones.
Understanding Noise and Interference Regimes in 5G Millimeter-Wave Cellular Networks
Venue: arXiv cs.NI 2016
Year: 2016

With the severe spectrum shortage in conventional cellular bands, millimeter-wave (mmWave) frequencies have been attracting growing attention for next-generation micro- and picocellular wireless networks. A fundamental and open question is whether mmWave cellular networks are likely to be noise- or interference-limited. Identifying in which regime a network is operating is critical for the design of MAC and physical-layer procedures and to provide insights on how transmissions across cells should be coordinated to cope with interference. This work uses the latest measurement-based statistical channel models to accurately assess the Interference-to-Noise Ratio (INR) in a wide range of deployment scenarios. In addition to cell density, we also study antenna array size and antenna patterns, whose effects are critical in the mmWave regime. The channel models also account for blockage, line-of-sight and non-line-of-sight regimes as well as local scattering, that significantly affect the level of spatial isolation.
Scientific Computing, High-Performance Computing and Data Science in Higher Education
Venue: arXiv cs.CY 2016
Year: 2016

We present an overview of current academic curricula for Scientific Computing, High-Performance Computing and Data Science. After a survey of current academic and non-academic programs across the globe, we focus on Canadian programs and specifically on the education program of the SciNet HPC Consortium, using its detailed enrollment and course statistics for the past four to five years. Not only do these data display a steady and rapid increase in the demand for research-computing instruction, they also show a clear shift from traditional (high performance) computing to data-oriented methods. It is argued that this growing demand warrants specialized research computing degrees. The possible curricula of such degrees are described next, taking existing programs as an example, and adding SciNet's experiences of student desires as well as trends in advanced research computing.
Accurate Online Full Charge Capacity Modeling of Smartphone Batteries
Venue: arXiv cs.SY 2016
Year: 2016

Full charge capacity (FCC) refers to the amount of energy a battery can hold. It is the fundamental property of smartphone batteries that diminishes as the battery ages and is charged/discharged. We investigate the behavior of smartphone batteries while charging and demonstrate that the battery voltage and charging rate information can together characterize the FCC of a battery. We propose a new method for accurately estimating FCC without exposing low-level system details or introducing new hardware or system modules. We also propose and implement a collaborative FCC estimation technique that builds on crowdsourced battery data. The method finds the reference voltage curve and charging rate of a particular smartphone model from the data and then compares the curve and rate of an individual user with the model reference curve. After analyzing a large data set, we report that 55% of all devices and at least one device in 330 out of 357 unique device models lost some of their FCC. For some models, the median capacity loss exceeded 20% with the inter-quartile range being over 20 pp. The models enable debugging the performance of smartphone batteries, more accurate power modeling, and energy-aware system or application optimization.
Downlink Transmit Power Setting in LTE HetNets with Carrier Aggregation
Venue: arXiv cs.NI 2016
Year: 2016

Carrier aggregation, which allows users to aggregate several component carriers to obtain up to 100 MHz of band- width, is one of the central features envisioned for next generation cellular networks. While this feature will enable support for higher data rates and improve quality of service, it may also be employed as an effective interference mitigation technique, especially in multi-tier heterogeneous networks. Having in mind that the aggregated component carriers may belong to different frequency bands and, hence, have varying propagation profiles, we argue that it is not necessary, indeed even harmful, to transmit at maximum power at all carriers, at all times. Rather, by using game theory, we design a distributed algorithm that lets eNodeBs and micro base stations dynamically adjust the downlink transmit power for the different component carriers. We compare our scheme to different power strategies combined with popular interference mitigation techniques, in a typical large-scale scenario, and show that our solution significantly outperforms the other strategies in terms of global network utility, power consumption and user throughput.
Syntactic and semantic classification of verb arguments using dependency-based and rich semantic features
Venue: arXiv cs.CL 2016
Year: 2016

Corpus Pattern Analysis (CPA) has been the topic of Semeval 2015 Task 15, aimed at producing a system that can aid lexicographers in their efforts to build a dictionary of meanings for English verbs using the CPA annotation process. CPA parsing is one of the subtasks which this annotation process is made of and it is the focus of this report. A supervised machine-learning approach has been implemented, in which syntactic features derived from parse trees and semantic features derived from WordNet and word embeddings are used. It is shown that this approach performs well, even with the data sparsity issues that characterize the dataset, and can obtain better results than other system by a margin of about 4% f-score.
Sleeping Beauties Cited in Patents: Is there also a Dormitory of Inventions?
Venue: arXiv cs.DL 2016
Year: 2016

A Sleeping Beauty in Science is a publication that goes unnoticed (sleeps) for a long time and then, almost suddenly, attracts a lot of attention (is awakened by a prince). In our foregoing study we found that roughly half of the Sleeping Beauties are application-oriented and thus are potential Sleeping Innovations. In this paper we investigate a new topic: Sleeping Beauties that are cited in patents. In this way we explore the existence of a dormitory of inventions. We find that patent citation may occur before or after the awakening and that the depth of the sleep, i.e., citation rate during the sleeping period, is no predictor for later scientific or technological impact of the Sleeping Beauty. Inventor-author self-citations occur only in a small minority of the Sleeping Beauties that are cited in patents, but other types of inventor-author links occur more frequently. We analyze whether they deal with new topics by measuring the time-dependent evolution in the entire scientific literature of the number of papers related to both the precisely defined topics as well as the broader research theme of the Sleeping Beauty during and after the sleeping time. We focus on the awakening by analyzing the first group of papers that cites the Sleeping Beauty. Next, we create concept maps of the topic-related and the citing papers for a time period immediately following the awakening and for the most recent period. Finally, we make an extensive assessment of the cited and citing relations of the Sleeping Beauty. We find that tunable co-citation analysis is a powerful tool to discover the prince and other important application-oriented work directly related to the Sleeping Beauty, for instance papers written by authors who cite Sleeping Beauties in both the patents of which they are the inventors, as well as in their scientific papers.
What we write about when we write about causality: Features of causal statements across large-scale social discourse
Venue: arXiv cs.CY 2016
Year: 2016

Identifying and communicating relationships between causes and effects is important for understanding our world, but is affected by language structure, cognitive and emotional biases, and the properties of the communication medium. Despite the increasing importance of social media, much remains unknown about causal statements made online. To study real-world causal attribution, we extract a large-scale corpus of causal statements made on the Twitter social network platform as well as a comparable random control corpus. We compare causal and control statements using statistical language and sentiment analysis tools. We find that causal statements have a number of significant lexical and grammatical differences compared with controls and tend to be more negative in sentiment than controls. Causal statements made online tend to focus on news and current events, medicine and health, or interpersonal relationships, as shown by topic models. By quantifying the features and potential biases of causality communication, this study improves our understanding of the accuracy of information and opinions found online.
Position Prediction of Ball and Fuzzy Controller for Shooting Action in A Soccer Robot System
Venue: arXiv cs.RO 2016
Year: 2016

The robot soccer game based complex motion control has been widely studied for the moving object capture and shooting. A position prediction algorithm based on global vision is introduced in order to improve the accuracy and robustness of the vision system for tracking moving objects, including a Kalmanfiter, a dynamic window and an obstacle avoidance strategy. This paper deals with the positon prediction for moving ball by using Kalmanfiter and the Fuzzy Controller for shooting action in a dynamic environment.
Towards the Holodeck: Fully Immersive Virtual Reality Visualisation of Scientific and Engineering Data
Venue: arXiv cs.HC 2016
Year: 2016

In this paper, we describe the development and operating principles of an immersive virtual reality (VR) visualisation environment that is designed around the use of consumer VR headsets in an existing wide area motion capture suite. We present two case studies in the application areas of visualisation of scientific and engineering data. Each of these case studies utilise a different render engine, namely a custom engine for one case and a commercial game engine for the other. The advantages and appropriateness of each approach are discussed along with suggestions for future work.
Mainstreaming video annotation software for critical video analysis
Venue: arXiv cs.MM 2016
Year: 2016

The range of video annotation software currently available is set within commercially specialized professions, distributed via outdated sources or through online video hosting services. As video content becomes an increasingly significant tool for analysis, there is a demand for appropriate digital annotation techniques that offer equivalent functionality to tools used for annotation of text based literature sources. This paper argues for the importance of video annotating as an effective method for research that is as accessible as literature annotation is. Video annotation has been shown to trigger higher learning and engagement but research struggles to explain the absence of video annotation in contemporary structures of education practice. In both academic and informal settings the use of video playback as a meaningful tool of analysis is apparent, yet the availability of supplementary annotation software is not within obvious grasp or even prevalent in standardized computer software. Practical software tools produced by the researcher have demonstrated effective video annotation in a short development time. With software design programs available for rapid application creation, this paper also highlights the absence of a development community. This paper argues that video annotation is an accessible tool, not just for academic contexts, but also for wider practical video analysis applications, potentially becoming a mainstream learning tool. This paper thus presents a practical multimodal public approach to video research that potentially affords a deeper analysis of media content. This is supported by an in-depth consideration of the motivation for undertaking video annotation and a critical analysis of currently available tools.
Optimal Caching and User Association in Cache-enabled Heterogeneous Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Heterogenous wireless networks (Hetnets) provide a powerful approach to meet the massive growth in traffic demands, but also impose a significant challenge on backhaul. Caching at small base stations (BSs) and wireless small cell backhaul have been proposed as attractive solutions to address this new challenge. In this paper, we consider the optimal caching and user association to minimize the total time to satisfy the average demands in cached-enabled Hetnets with wireless backhaul. We formulate this problem as a mixed discrete-continuous optimization for given bandwidth and cache resources. First, we characterize the structure of the optimal solution. Specifically, we show that the optimal caching is to store the most popular files at each pico BS, and the optimal user association has a threshold form. We also obtain the closed-form optimal solution in the homogenous scenario of pico cells. Then, we analyze the impact of bandwidth and cache resources on the minimum total time to satisfy the average demands. Finally, using numerical simulations, we verify the analytical results.
Order-Invariance of Two-Variable Logic is Decidable
Venue: arXiv cs.LO 2016
Year: 2016

It is shown that order-invariance of two-variable first-logic is decidable in the finite. This is an immediate consequence of a decision procedure obtained for the finite satisfiability problem for existential second-order logic with two first-order variables ($\mathrm{ESO}^2$) on structures with two linear orders and one induced successor. We also show that finite satisfiability is decidable on structures with two successors and one induced linear order. In both cases, so far only decidability for monadic $\mathrm{ESO}^2$ has been known. In addition, the finite satisfiability problem for $\mathrm{ESO}^2$ on structures with one linear order and its induced successor relation is shown to be decidable in non-deterministic exponential time.
Accuracy of Discrete Markov Approximation in the Problems of Estimation of Random Field Characteristics
Venue: arXiv cs.IT 2016
Year: 2016

The covariance matrix of measurements of Markov random fields (processes) has useful properties that allow to develop effective computational algorithms for many problems in the study of Markov fields on the basis of field observations (parametric identification problems, filtering problems, interpolation problems and others). Therefore, approximation of arbitrary random fields by Markov fields is of great interest, as it gives an opportunity to use computationally efficient algorithms of Markov fields analysis to study them. The paper deals with approximation of the covariance matrix of the field being observed with the help of covariance matrix of a multiply connected (m-connected) Markov field. Using computer simulation, the accuracy of such replacements at different values of the connectivity coefficient m for the problem of parametric identification of deterministic component of the field has been studied. Various models of deterministic polynomial component of the field and a number of covariance functions that are often used as a mathematical model of real random noise and measurements noise have been reviewed. It has been shown that for many problems such approximation, even at small connectivity m values of approximating Markov field, provides necessary accuracy. This allows to achieve good compromise between accuracy of the estimates and complexity of calculating them.
A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in Firedrake
Venue: arXiv cs.MS 2016
Year: 2016

We present a generic algorithm for numbering and then efficiently iterating over the data values attached to an extruded mesh. An extruded mesh is formed by replicating an existing mesh, assumed to be unstructured, to form layers of prismatic cells. Applications of extruded meshes include, but are not limited to, the representation of 3D high aspect ratio domains employed by geophysical finite element simulations. These meshes are structured in the extruded direction. The algorithm presented here exploits this structure to avoid the performance penalty traditionally associated with unstructured meshes. We evaluate the implementation of this algorithm in the Firedrake finite element system on a range of low compute intensity operations which constitute worst cases for data layout performance exploration. The experiments show that having structure along the extruded direction enables the cost of the indirect data accesses to be amortized after 10-20 layers as long as the underlying mesh is well-ordered. We characterise the resulting spatial and temporal reuse in a representative set of both continuous-Galerkin and discontinuous-Galerkin discretisations. On meshes with realistic numbers of layers the performance achieved is between 70% and 90% of a theoretical hardware-specific limit.
FRAPPE: Fast Replication Platform for Elastic Services
Venue: arXiv cs.DC 2016
Year: 2016

Elasticity is critical for today's cloud services, which must be able to quickly adapt to dynamically changing load conditions and resource availability. We introduce FRAPPE, a new consistent replication platform aiming at improving elasticity of the replicated services hosted in clouds or large data centers. In the core of FRAPPE is a novel replicated state machine protocol, which employs speculative executions to ensure continuous operation during the reconfiguration periods as well as in situations where failures prevent the agreement on the next stable configuration from being reached in a timely fashion. We present the FRAPPE's architecture and describe the basic techniques underlying the implementation of our speculative state machine protocol.