OpenRaiser/Intern-Atlas huggingface dataset:
A family of fast exact pattern matching algorithms
Venue: arXiv cs.DS 2016
Year: 2016

A family of comparison-based exact pattern matching algorithms is described. They utilize multi-dimensional arrays in order to process more than one adjacent text window in each iteration of the search cycle. This approach leads to a lower average time complexity by the cost of space. The algorithms of this family perform well for short patterns and middle size alphabets. In such case the shift of the window by several pattern lengths at once is quite probable, which is the main factor of algorithm success. Our algorithms outperform the Boyer-Moore-Horspool algorithm, either in the original version or with Sunday's Quick search modification, in a wide area of pattern length - alphabet size plane. In some subareas the proposed algorithms are the fastest among all known exact pattern matching algorithms. Namely, they perform best when alphabet size is about 30-40 and pattern length is about 4-10. Such parameters are typical for search in natural language text databases.
Scalable and Cost Efficient Algorithms for Virtual CDN Migration
Venue: arXiv cs.NI 2016
Year: 2016

Virtual Content Delivery Network (vCDN) migration is necessary to optimize the use of resources and improve the performance of the overall SDN/NFV-based CDN function in terms of network operator cost reduction and high streaming quality. It requires intelligent and enticed joint SDN/NFV migration algorithms due to the evident huge amount of traffic to be delivered to end customers of the network. In this paper, two approaches for finding the optimal and near optimal path placement(s) and vCDN migration(s) are proposed (OPAC and HPAC). Moreover, several scenarios are considered to quantify the OPAC and HPAC behaviors and to compare their efficiency in terms of migration cost, migration time, vCDN replication number, and other cost factors. Then, they are implemented and evaluated under different network scales. Finally, the proposed algorithms are integrated in an SDN/NFV framework. Index Terms: vCDN; SDN/NFV Optimization; Migration Algorithms; Scalability Algorithms.
Motion Representation with Acceleration Images
Venue: arXiv cs.CV 2016
Year: 2016

Information of time differentiation is extremely important cue for a motion representation. We have applied first-order differential velocity from a positional information, moreover we believe that second-order differential acceleration is also a significant feature in a motion representation. However, an acceleration image based on a typical optical flow includes motion noises. We have not employed the acceleration image because the noises are too strong to catch an effective motion feature in an image sequence. On one hand, the recent convolutional neural networks (CNN) are robust against input noises. In this paper, we employ acceleration-stream in addition to the spatial- and temporal-stream based on the two-stream CNN. We clearly show the effectiveness of adding the acceleration stream to the two-stream CNN.
1-bend Upward Planar Drawings of SP-digraphs
Venue: arXiv cs.CG 2016
Year: 2016

It is proved that every series-parallel digraph whose maximum vertex-degree is $Δ$ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of $Δ$ distinct slopes. This is shown to be worst-case optimal in terms of the number of slopes. Furthermore, our construction gives rise to drawings with optimal angular resolution $\fracπΔ$. A variant of the proof technique is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) one-bend planar drawing with $\lceil\fracΔ{2}\rceil$ distinct slopes if biconnected, and with $\lceil\fracΔ{2}\rceil+1$ distinct slopes if connected.
Multi-Label Classification Method Based on Extreme Learning Machines
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, an Extreme Learning Machine (ELM) based technique for Multi-label classification problems is proposed and discussed. In multi-label classification, each of the input data samples belongs to one or more than one class labels. The traditional binary and multi-class classification problems are the subset of the multi-label problem with the number of labels corresponding to each sample limited to one. The proposed ELM based multi-label classification technique is evaluated with six different benchmark multi-label datasets from different domains such as multimedia, text and biology. A detailed comparison of the results is made by comparing the proposed method with the results from nine state of the arts techniques for five different evaluation metrics. The nine methods are chosen from different categories of multi-label methods. The comparative results shows that the proposed Extreme Learning Machine based multi-label classification technique is a better alternative than the existing state of the art methods for multi-label problems.
Economic Analysis of Crowdsourced Wireless Community Networks
Venue: arXiv cs.GT 2016
Year: 2016

Crowdsourced wireless community networks can effectively alleviate the limited coverage issue of Wi-Fi access points (APs), by encouraging individuals (users) to share their private residential Wi-Fi APs with others. In this paper, we provide a comprehensive economic analysis for such a crowdsourced network, with the particular focus on the users' behavior analysis and the community network operator's pricing design. Specifically, we formulate the interactions between the network operator and users as a two-layer Stackelberg model, where the operator determining the pricing scheme in Layer I, and then users determining their Wi-Fi sharing schemes in Layer II. First, we analyze the user behavior in Layer II via a two-stage membership selection and network access game, for both small-scale networks and large-scale networks. Then, we design a partial price differentiation scheme for the operator in Layer I, which generalizes both the complete price differentiation scheme and the single pricing scheme (i.e., no price differentiation). We show that the proposed partial pricing scheme can achieve a good tradeoff between the revenue and the implementation complexity. Numerical results demonstrate that when using the partial pricing scheme with only two prices, we can increase the operator's revenue up to 124.44% comparing with the single pricing scheme, and can achieve an average of 80% of the maximum operator revenue under the complete price differentiation scheme.
A short review and primer on pupillometry in human computer interaction applications
Venue: arXiv cs.HC 2016
Year: 2016

The application of psychophysiological signals in human-computer interaction is a growing field with significant potential for future smart personalised systems. Working in this emerging field requires comprehension of an array of physiological signals and analysis techniques. Pupillometry has been studied for over a century, but it has just recently started being used in human-computer interaction setups. Traditionally, pupil size has been used as an indicator of cognitive workload and mental effort. However, pupil size has been linked to other cognitive processes as well, ranging from attention to affective processing. We present a short review on the application of pupillometry in human-computer interaction. This paper aims to serve as a primer for the novice, enabling rapid familiarisation with the latest core concepts. We put special emphasis on everyday human-computer interface applications to distinguish from the more common clinical or sports uses of psychophysiology. This paper is an extract from a comprehensive review of the entire field of ambulatory psychophysiology, including 12 similar chapters, plus application guidelines and systematic review. Thus any citation should be made using the following reference: B. Cowley, M. Filetti, K. Lukander, J. Torniainen, A. Henelius, L. Ahonen, O. Barral, I. Kosunen, T. Valtonen, M. Huotilainen, N. Ravaja, G. Jacucci. The Psychophysiology Primer: a guide to methods and a broad review with a focus on human-computer interaction. Foundations and Trends in Human-Computer Interaction, vol. 9, no. 3-4, pp. 150-307, 2016.
Approximate Capacity of the Two-User Gaussian Interference Channel with Noisy Channel-Output Feedback
Venue: arXiv cs.IT 2016
Year: 2016

In this research report, an achievability region and a converse region for the two-user Gaussian interference channel with noisy channel-output feedback (G-IC-NOF) are presented. The achievability region is obtained using a random coding argument and three well-known techniques: rate splitting, superposition coding and backward decoding. The converse region is obtained using some of the existing perfect-output feedback outer-bounds as well as a set of new outer-bounds that are obtained by using genie-aided models of the original G-IC-NOF. Finally, it is shown that the achievability region and the converse region approximate the capacity region of the G-IC-NOF to within a constant gap in bits per channel use.
The Generalized Smallest Grammar Problem
Venue: arXiv cs.CL 2016
Year: 2016

The Smallest Grammar Problem -- the problem of finding the smallest context-free grammar that generates exactly one given sequence -- has never been successfully applied to grammatical inference. We investigate the reasons and propose an extended formulation that seeks to minimize non-recursive grammars, instead of straight-line programs. In addition, we provide very efficient algorithms that approximate the minimization problem of this class of grammars. Our empirical evaluation shows that we are able to find smaller models than the current best approximations to the Smallest Grammar Problem on standard benchmarks, and that the inferred rules capture much better the syntactic structure of natural language.
Computing NodeTrix Representations of Clustered Graphs
Venue: arXiv cs.CG 2016
Year: 2016

NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and inter-cluster edges as curves connecting the matrix boundaries. We study the complexity of constructing NodeTrix representations focusing on planarity testing problems, and we show several NP-completeness results and some polynomial-time algorithms. Building on such algorithms we develop a JavaScript library for NodeTrix representations aimed at reducing the crossings between edges incident to the same matrix.
Towards Transparent AI Systems: Interpreting Visual Question Answering Models
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks have shown striking progress and obtained state-of-the-art results in many AI research fields in the recent years. However, it is often unsatisfying to not know why they predict what they do. In this paper, we address the problem of interpreting Visual Question Answering (VQA) models. Specifically, we are interested in finding what part of the input (pixels in images or words in questions) the VQA model focuses on while answering the question. To tackle this problem, we use two visualization techniques -- guided backpropagation and occlusion -- to find important words in the question and important regions in the image. We then present qualitative and quantitative analyses of these importance maps. We found that even without explicit attention mechanisms, VQA models may sometimes be implicitly attending to relevant regions in the image, and often to appropriate words in the question.
Learning Syntactic Program Transformations from Examples
Venue: arXiv cs.SE 2016
Year: 2016

IDEs, such as Visual Studio, automate common transformations, such as Rename and Extract Method refactorings. However, extending these catalogs of transformations is complex and time-consuming. A similar phenomenon appears in intelligent tutoring systems where instructors have to write cumbersome code transformations that describe "common faults" to fix similar student submissions to programming assignments. We present REFAZER, a technique for automatically generating program transformations. REFAZER builds on the observation that code edits performed by developers can be used as examples for learning transformations. Example edits may share the same structure but involve different variables and subexpressions, which must be generalized in a transformation at the right level of abstraction. To learn transformations, REFAZER leverages state-of-the-art programming-by-example methodology using the following key components: (a) a novel domain-specific language (DSL) for describing program transformations, (b) domain-specific deductive algorithms for synthesizing transformations in the DSL, and (c) functions for ranking the synthesized transformations. We instantiate and evaluate REFAZER in two domains. First, given examples of edits used by students to fix incorrect programming assignment submissions, we learn transformations that can fix other students' submissions with similar faults. In our evaluation conducted on 4 programming tasks performed by 720 students, our technique helped to fix incorrect submissions for 87% of the students. In the second domain, we use repetitive edits applied by developers to the same project to synthesize a program transformation that applies these edits to other locations in the code. In our evaluation conducted on 59 scenarios of repetitive edits taken from 3 C# open-source projects, REFAZER learns the intended program transformation in 83% of the cases.
Mining Half a Billion Topical Experts Across Multiple Social Networks
Venue: arXiv cs.IR 2016
Year: 2016

Mining topical experts on social media is a problem that has gained significant attention due to its wide-ranging applications. Here we present the first study that combines data from four major social networks -- Twitter, Facebook, Google+ and LinkedIn, along with the Wikipedia graph and internet webpage text and metadata, to rank topical experts across the global population of users. We perform an in-depth analysis of 37 features derived from various data sources such as message text, user lists, webpages, social graphs and wikipedia. This large-scale study includes more than 12 billion messages over a 90-day sliding window and 58 billion social graph edges. Comparison reveals that features derived from Twitter Lists, Wikipedia, internet webpages and Twitter Followers are especially good indicators of expertise. We train an expertise ranking model using these features on a large ground truth dataset containing almost 90,000 labels. This model is applied within a production system that ranks over 650 million experts in more than 9,000 topical domains on a daily basis. We provide results and examples on the effectiveness of our expert ranking system, along with empirical validation. Finally, we make the topical expertise data available through open REST APIs for wider use.
Measuring the Quality of Exercises
Venue: arXiv cs.CV 2016
Year: 2016

This work explores the problem of exercise quality measurement since it is essential for effective management of diseases like cerebral palsy (CP). This work examines the assessment of quality of large amplitude movement (LAM) exercises designed to treat CP in an automated fashion. Exercise data was collected by trained participants to generate ideal examples to use as a positive samples for machine learning. Following that, subjects were asked to deliberately make subtle errors during the exercise, such as restricting movements, as is commonly seen in cases of patients suffering from CP. The quality measurement problem was then posed as a classification to determine whether an example exercise was either "good" or "bad". Popular machine learning techniques for classification, including support vector machines (SVM), single and doublelayered neural networks (NN), boosted decision trees, and dynamic time warping (DTW), were compared. The AdaBoosted tree performed best with an accuracy of 94.68% demonstrating the feasibility of assessing exercise quality.
Towards Hybrid Cloud-assisted Crowdsourced Live Streaming: Measurement and Analysis
Venue: arXiv cs.MM 2016
Year: 2016

Crowdsourced Live Streaming (CLS), most notably Twitch.tv, has seen explosive growth in its popularity in the past few years. In such systems, any user can lively broadcast video content of interest to others, e.g., from a game player to many online viewers. To fulfill the demands from both massive and heterogeneous broadcasters and viewers, expensive server clusters have been deployed to provide video ingesting and transcoding services. Despite the existence of highly popular channels, a significant portion of the channels is indeed unpopular. Yet as our measurement shows, these broadcasters are consuming considerable system resources; in particular, 25% (resp. 30%) of bandwidth (resp. computation) resources are used by the broadcasters who do not have any viewers at all. In this paper, we closely examine the challenge of handling unpopular live-broadcasting channels in CLS systems and present a comprehensive solution for service partitioning on hybrid cloud. The trace-driven evaluation shows that our hybrid cloud-assisted design can smartly assign ingesting and transcoding tasks to the elastic cloud virtual machines, providing flexible system deployment cost-effectively.
Estimation and Control of Quality of Service in Demand Dispatch
Venue: arXiv cs.SY 2016
Year: 2016

It is now well known that flexibility of energy consumption can be harnessed for the purposes of grid-level ancillary services. In particular, through distributed control of a collection of loads, a balancing authority regulation signal can be tracked accurately, while ensuring that the quality of service (QoS) for each load is acceptable {\it on average}. In this paper it is argued that a histogram of QoS is approximately Gaussian, and consequently each load will eventually receive poor service. Statistical techniques are developed to estimate the mean and variance of QoS as a function of the power spectral density of the regulation signal. It is also shown that additional local control can eliminate risk: The histogram of QoS is {\it truncated} through this local control, so that strict bounds on service quality are guaranteed. While there is a tradeoff between the grid-level tracking performance (capacity and accuracy) and the bounds imposed on QoS, it is found that the loss of capacity is minor in typical cases.
Attentional Push: Augmenting Salience with Shared Attention Modeling
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel visual attention tracking technique based on Shared Attention modeling. Our proposed method models the viewer as a participant in the activity occurring in the scene. We go beyond image salience and instead of only computing the power of an image region to pull attention to it, we also consider the strength with which other regions of the image push attention to the region in question. We use the term Attentional Push to refer to the power of image regions to direct and manipulate the attention allocation of the viewer. An attention model is presented that incorporates the Attentional Push cues with standard image salience-based attention modeling algorithms to improve the ability to predict where viewers will fixate. Experimental evaluation validates significant improvements in predicting viewers' fixations using the proposed methodology in both static and dynamic imagery.
Group Rotation Type Crowdsourcing
Venue: arXiv cs.DB 2016
Year: 2016

A common workflow to perform a continuous human task stream is to divide workers into groups, have one group perform the newly-arrived task, and rotate the groups. We call this type of workflow the group rotation. This paper addresses the problem of how to manage Group Rotation Type Crowdsourcing, the group rotation in a crowdsourcing setting. In the group-rotation type crowdsourcing, we must change the group structure dynamically because workers come in and leave frequently. This paper proposes an approach to explore a design space of methods for group restructuring in the group rotation type crowdsourcing.
On the Performance of Multihop-Intervehicular Communications Systems over n*Rayleigh Fading Channels
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the performance of multihop-intervehicular communication systems with regenerative and nonregenerative relaying. We consider the so-called "n*Rayleigh distribution" as an adequate multipath fading channel model for vehicle-to-vehicle communication scenarios. We derive a novel approximation for the outage probability of maximum ratio combining (MRC) diversity reception. In addition, we analyze the amount of fading and optimize the power allocation for the investigated scenario. Numerical results show that regenerative systems are more efficient than nonregenerative systems when the cascading order (n) is small; however, for large n, our results demonstrate that the performance of both relaying techniques is rather similar.
Equivalence Checking a Floating-point Unit against a High-level C Model (Extended Version)
Venue: arXiv cs.SE 2016
Year: 2016

Semiconductor companies have increasingly adopted a methodology that starts with a system-level design specification in C/C++/SystemC. This model is extensively simulated to ensure correct functionality and performance. Later, a Register Transfer Level (RTL) implementation is created in Verilog, either manually by a designer or automatically by a high-level synthesis tool. It is essential to check that the C and Verilog programs are consistent. In this paper, we present a two-step approach, embodied in two equivalence checking tools, VERIFOX and HW-CBMC, to validate designs at the software and RTL levels, respectively. VERIFOX is used for equivalence checking of an untimed software model in C against a high-level reference model in C. HW-CBMC verifies the equivalence of a Verilog RTL implementation against an untimed software model in C. To evaluate our tools, we applied them to a commercial floating-point arithmetic unit (FPU) from ARM and an open-source dual-path floating-point adder.
Dual Capacity Upper Bounds for Noisy Runlength Constrained Channels
Venue: arXiv cs.IT 2016
Year: 2016

Binary-input memoryless channels with a runlength constrained input are considered. Upper bounds to the capacity of such noisy runlength constrained channels are derived using the dual capacity method with Markov test distributions satisfying the Karush-Kuhn-Tucker (KKT) conditions for the capacity-achieving output distribution. Simplified algebraic characterizations of the bounds are presented for the binary erasure channel (BEC) and the binary symmetric channel (BSC). These upper bounds are very close to achievable rates, and improve upon previously known feedback-based bounds for a large range of channel parameters. For the binary-input Additive White Gaussian Noise (AWGN) channel, the upper bound is simplified to a small-scale numerical optimization problem. These results provide some of the simplest upper bounds for an open capacity problem that has theoretical and practical relevance.
Separability of Reachability Sets of Vector Addition Systems
Venue: arXiv cs.FL 2016
Year: 2016

Given two families of sets $\mathcal{F}$ and $\mathcal{G}$, the $\mathcal{F}$ separability problem for $\mathcal{G}$ asks whether for two given sets $U, V \in \mathcal{G}$ there exists a set $S \in \mathcal{F}$, such that $U$ is included in $S$ and $V$ is disjoint with $S$. We consider two families of sets $\mathcal{F}$: modular sets $S \subseteq \mathbb{N}^d$, defined as unions of equivalence classes modulo some natural number $n \in \mathbb{N}$, and unary sets. Our main result is decidability of modular and unary separability for the class $\mathcal{G}$ of reachability sets of Vector Addition Systems, Petri Nets, Vector Addition Systems with States, and for sections thereof.