OpenRaiser/Intern-Atlas huggingface dataset:
Structural cost-optimal design of sensor networks for distributed estimation
Venue: arXiv cs.SY 2018
Year: 2018

In this letter we discuss cost optimization of sensor networks monitoring structurally full-rank systems under distributed observability constraint. Using structured systems theory, the problem is relaxed into two subproblems: (i) sensing cost optimization and (ii) networking cost optimization. Both problems are reformulated as combinatorial optimization problems. The sensing cost optimization is shown to have a polynomial order solution. The networking cost optimization is shown to be NP-hard in general, but has a polynomial order solution under specific conditions. A 2-approximation polynomial order relaxation is provided for general networking cost optimization, which is applicable in large-scale system monitoring.
Simple dynamic algorithms for Maximal Independent Set and other problems
Venue: arXiv cs.DS 2018
Year: 2018

Most graphs in real life keep changing with time. These changes can be in the form of insertion or deletion of edges or vertices. Such rapidly changing graphs motivate us to study dynamic graph algorithms. However, three important graph problems that are perhaps not sufficiently addressed in the literature include independent sets, maximum matching (exact) and maximum flows. Maximal Independent Set (MIS) is one of the most prominently studied problems in the distributed setting. Recently, the first dynamic MIS algorithm for distributed networks was given by Censor-Hillel et al. [PODC16], requiring expected $O(1)$ amortized rounds with $O(Δ)$ messages per update, where $Δ$ is the maximum degree of a vertex in the graph. They suggested an open problem to maintain MIS in fully dynamic centralized setting more efficiently. Assadi et al. [STOC18] presented a deterministic centralized fully dynamic MIS algorithm requiring $O(\min\{Δ,m^{3/4}\})$ amortized time per update. This result is quite complex involving an exhaustive case analysis. We report a surprisingly simple deterministic centralized algorithm which improves the amortized update time to $O(\min\{Δ,m^{2/3}\})$. Additionally, we present some other minor results related to dynamic MIS, Maximum Flow, and Maximum Matching. A common trait of all our results is that despite improving state of the art upper bounds or matching state of the art lower bounds, they are surprisingly simple and are analysed using simple amortization arguments. Further, they use no complicated data structures or black box algorithms for their implementation.
Evaluating Hospital Case Cost Prediction Models Using Azure Machine Learning Studio
Venue: arXiv cs.LG 2018
Year: 2018

Ability for accurate hospital case cost modelling and prediction is critical for efficient health care financial management and budgetary planning. A variety of regression machine learning algorithms are known to be effective for health care cost predictions. The purpose of this experiment was to build an Azure Machine Learning Studio tool for rapid assessment of multiple types of regression models. The tool offers environment for comparing 14 types of regression models in a unified experiment: linear regression, Bayesian linear regression, decision forest regression, boosted decision tree regression, neural network regression, Poisson regression, Gaussian processes for regression, gradient boosted machine, nonlinear least squares regression, projection pursuit regression, random forest regression, robust regression, robust regression with mm-type estimators, support vector regression. The tool presents assessment results arranged by model accuracy in a single table using five performance metrics. Evaluation of regression machine learning models for performing hospital case cost prediction demonstrated advantage of robust regression model, boosted decision tree regression and decision forest regression. The operational tool has been published to the web and openly available for experiments and extensions.
Automated Detecting and Repair of Cross-Site Scripting Vulnerabilities
Venue: arXiv cs.CR 2018
Year: 2018

The best practice to prevent Cross Site Scripting (XSS) attacks is to apply encoders to sanitize untrusted data. To balance security and functionality, encoders should be applied to match the web page context, such as HTML body, JavaScript, and style sheets. A common programming error is the use of a wrong type of encoder to sanitize untrusted data, leaving the application vulnerable. We present a security unit testing approach to detect XSS vulnerabilities caused by improper encoding of untrusted data. Unit tests for the XSS vulnerability are constructed out of each web page and then evaluated by a unit test execution framework. A grammar-based attack generator is devised to automatically generate test inputs. We also propose a vulnerability repair technique that can automatically fix detected vulnerabilities in many situations. Evaluation of this approach has been conducted on an open source medical record application with over 200 web pages written in JSP.
Energy-efficiency evaluation of Intel KNL for HPC workloads
Venue: arXiv cs.DC 2018
Year: 2018

Energy consumption is increasingly becoming a limiting factor to the design of faster large-scale parallel systems, and development of energy-efficient and energy-aware applications is today a relevant issue for HPC code-developer communities. In this work we focus on energy performance of the Knights Landing (KNL) Xeon Phi, the latest many-core architecture processor introduced by Intel into the HPC market. We take into account the 64-core Xeon Phi 7230, and analyze its energy performance using both the on-chip MCDRAM and the regular DDR4 system memory as main storage for the application data-domain. As a benchmark application we use a Lattice Boltzmann code heavily optimized for this architecture and implemented using different memory data layouts to store its lattice. We assessthen the energy consumption using different memory data-layouts, kind of memory (DDR4 or MCDRAM) and number of threads per core.
Scaling Out Acid Applications with Operation Partitioning
Venue: arXiv cs.DC 2018
Year: 2018

OLTP applications with high workloads that cannot be served by a single server need to scale out to multiple servers. Typically, scaling out entails assigning a different partition of the application state to each server. But data partitioning is at odds with preserving the strong consistency guarantees of ACID transactions, a fundamental building block of many OLTP applications. The more we scale out and spread data across multiple servers, the more frequent distributed transactions accessing data at different servers will be. With a large number of servers, the high cost of distributed transactions makes scaling out ineffective or even detrimental. In this paper we propose Operation Partitioning, a novel paradigm to scale out OLTP applications that require ACID guarantees. Operation Partitioning indirectly partitions data across servers by partitioning the application's operations through static analysis. This partitioning of operations yields to a lock-free Conveyor Belt protocol for distributed coordination, which can scale out unmodified applications running on top of unmodified database management systems. We implement the protocol in a system called Elia and use it to scale out two applications, TPC-W and RUBiS. Our experiments show that Elia can increase maximum throughput by up to 4.2x and reduce latency by up to 58.6x compared to MySQL Cluster while at the same time providing a stronger isolation guarantee (serializability instead of read committed).
Testing Scientific Software: A Systematic Literature Review
Venue: arXiv cs.SE 2018
Year: 2018

Context: Scientific software plays an important role in critical decision making, for example making weather predictions based on climate models, and computation of evidence for research publications. Recently, scientists have had to retract publications due to errors caused by software faults. Systematic testing can identify such faults in code. Objective: This study aims to identify specific challenges, proposed solutions, and unsolved problems faced when testing scientific software. Method: We conducted a systematic literature survey to identify and analyze relevant literature. We identified 62 studies that provided relevant information about testing scientific software. Results: We found that challenges faced when testing scientific software fall into two main categories: (1) testing challenges that occur due to characteristics of scientific software such as oracle problems and (2) testing challenges that occur due to cultural differences between scientists and the software engineering community such as viewing the code and the model that it implements as inseparable entities. In addition, we identified methods to potentially overcome these challenges and their limitations. Finally we describe unsolved challenges and how software engineering researchers and practitioners can help to overcome them. Conclusions: Scientific software presents special challenges for testing. Specifically, cultural differences between scientist developers and software engineers, along with the characteristics of the scientific software make testing more difficult. Existing techniques such as code clone detection can help to improve the testing process. Software engineers should consider special challenges posed by scientific software such as oracle problems when developing testing techniques.
Iris Recognition After Death
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a comprehensive study of post-mortem human iris recognition carried out for 1,200 near-infrared and 1,787 visible-light samples collected from 37 deceased individuals kept in the mortuary conditions. We used four independent iris recognition methods (three commercial and one academic) to analyze genuine and impostor comparison scores and check the dynamics of iris quality decay over a period of up to 814 hours after death. This study shows that post-mortem iris recognition may be close-to-perfect approximately 5 to 7 hours after death and occasionally is still viable even 21 days after death. These conclusions contradict the statements present in past literature that the iris is unusable as a biometrics shortly after death, and show that the dynamics of post-mortem changes to the iris that are important for biometric identification are more moderate than previously hypothesized. The paper contains a thorough medical commentary that helps to understand which post-mortem metamorphoses of the eye may impact the performance of automatic iris recognition. We also show that post-mortem iris recognition works equally well for images taken in near-infrared and when the red channel of visible-light sample is used. However, cross-wavelength matching presents significantly worse performance. This paper conforms to reproducible research and the database used in this study is made publicly available to facilitate research of post-mortem iris recognition. To our knowledge, this paper offers the most comprehensive evaluation of post-mortem iris recognition and the largest database of post-mortem iris images.
A Survey of Miss-Ratio Curve Construction Techniques
Venue: arXiv cs.PF 2018
Year: 2018

Miss-ratio curve (MRC), or equivalently hit-ratio curve (HRC), construction techniques have recently gathered the attention of many researchers. Recent advancements have allowed for approximating these curves in constant time, allowing for online working-set-size (WSS) measurement. Techniques span the algorithmic design paradigm from classic dynamic programming to artificial intelligence inspired techniques. Our survey produces broad classification of the current techniques primarily based on \emph{what} locality metric is being recorded and \emph{how} that metric is stored for processing. Applications of theses curves span from dynamic cache partitioning in the processor, to improving block allocation at the operating system level. Our survey will give an overview of the historical, exact MRC construction methods, and compare them with the state-of-the-art methods present in today's literature. In addition, we will show where there are still open areas of research and remain excited to see what this domain can produce with a strong theoretical background.
A Computation Offloading Incentive Mechanism with Delay and Cost Constraints under 5G Satellite-ground IoV architecture
Venue: arXiv cs.NI 2018
Year: 2018

The 5G Internet of Vehicles has become a new paradigm alongside the growing popularity and variety of computation-intensive applications with high requirements for computational resources and analysis capabilities. Existing network architectures and resource management mechanisms may not sufficiently guarantee satisfactory Quality of Experience and network efficiency, mainly suffering from coverage limitation of Road Side Units, insufficient resources, and unsatisfactory computational capabilities of onboard equipment, frequently changing network topology, and ineffective resource management schemes. To meet the demands of such applications, in this article, we first propose a novel architecture by integrating the satellite network with 5G cloud-enabled Internet of Vehicles to efficiently support seamless coverage and global resource management. A incentive mechanism based joint optimization problem of opportunistic computation offloading under delay and cost constraints is established under the aforementioned framework, in which a vehicular user can either significantly reduce the application completion time by offloading workloads to several nearby vehicles through opportunistic vehicle-to-vehicle channels while effectively controlling the cost or protect its own profit by providing compensated computing service. As the optimization problem is non-convex and NP-hard, simulated annealing based on the Markov Chain Monte Carlo as well as the metropolis algorithm is applied to solve the optimization problem, which can efficaciously obtain both high-quality and cost-effective approximations of global optimal solutions. The effectiveness of the proposed mechanism is corroborated through simulation results.
ETH-DS3Lab at SemEval-2018 Task 7: Effectively Combining Recurrent and Convolutional Neural Networks for Relation Classification and Extraction
Venue: arXiv cs.CL 2018
Year: 2018

Reliably detecting relevant relations between entities in unstructured text is a valuable resource for knowledge extraction, which is why it has awaken significant interest in the field of Natural Language Processing. In this paper, we present a system for relation classification and extraction based on an ensemble of convolutional and recurrent neural networks that ranked first in 3 out of the 4 subtasks at SemEval 2018 Task 7. We provide detailed explanations and grounds for the design choices behind the most relevant features and analyze their importance.
Towards Identifying Paid Open Source Developers - A Case Study with Mozilla Developers
Venue: arXiv cs.SE 2018
Year: 2018

Open source development contains contributions from both hired and volunteer software developers. Identification of this status is important when we consider the transferability of research results to the closed source software industry, as they include no volunteer developers. While many studies have taken the employment status of developers into account, this information is often gathered manually due to the lack of accurate automatic methods. In this paper, we present an initial step towards predicting paid and unpaid open source development using machine learning and compare our results with automatic techniques used in prior work. By relying on code source repository meta-data from Mozilla, and manually collected employment status, we built a dataset of the most active developers, both volunteer and hired by Mozilla. We define a set of metrics based on developers' usual commit time pattern and use different classification methods (logistic regression, classification tree, and random forest). The results show that our proposed method identify paid and unpaid commits with an AUC of 0.75 using random forest, which is higher than the AUC of 0.64 obtained with the best of the previously used automatic methods.
MAP moving horizon state estimation with binary measurements
Venue: arXiv cs.SY 2018
Year: 2018

The paper addresses state estimation for discrete-time systems with binary (threshold) measurements by following a Maximum A posteriori Probability (MAP) approach and exploiting a Moving Horizon (MH) approximation of the MAP cost-function. It is shown that, for a linear system and noise distributions with log-concave probability density function, the proposed MH-MAP state estimator involves the solution, at each sampling interval, of a convex optimization problem. Application of the MH-MAP estimator to dynamic estimation of a diffusion field given pointwise-in-time-and-space binary measurements of the field is also illustrated and, finally, simulation results relative to this application are shown to demonstrate the effectiveness of the proposed approach.
Sequence Training of DNN Acoustic Models With Natural Gradient
Venue: arXiv cs.CL 2018
Year: 2018

Deep Neural Network (DNN) acoustic models often use discriminative sequence training that optimises an objective function that better approximates the word error rate (WER) than frame-based training. Sequence training is normally implemented using Stochastic Gradient Descent (SGD) or Hessian Free (HF) training. This paper proposes an alternative batch style optimisation framework that employs a Natural Gradient (NG) approach to traverse through the parameter space. By correcting the gradient according to the local curvature of the KL-divergence, the NG optimisation process converges more quickly than HF. Furthermore, the proposed NG approach can be applied to any sequence discriminative training criterion. The efficacy of the NG method is shown using experiments on a Multi-Genre Broadcast (MGB) transcription task that demonstrates both the computational efficiency and the accuracy of the resulting DNN models.
Forex trading and Twitter: Spam, bots, and reputation manipulation
Venue: arXiv cs.SI 2018
Year: 2018

Currency trading (Forex) is the largest world market in terms of volume. We analyze trading and tweeting about the EUR-USD currency pair over a period of three years. First, a large number of tweets were manually labeled, and a Twitter stance classification model is constructed. The model then classifies all the tweets by the trading stance signal: buy, hold, or sell (EUR vs. USD). The Twitter stance is compared to the actual currency rates by applying the event study methodology, well-known in financial economics. It turns out that there are large differences in Twitter stance distribution and potential trading returns between the four groups of Twitter users: trading robots, spammers, trading companies, and individual traders. Additionally, we observe attempts of reputation manipulation by post festum removal of tweets with poor predictions, and deleting/reposting of identical tweets to increase the visibility without tainting one's Twitter timeline.
Improved Approximation for Tree Augmentation: Saving by Rewiring
Venue: arXiv cs.DS 2018
Year: 2018

The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called \emph{links}. The task is to find a set of links, of minimum size, whose addition to the tree leads to a $2$-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of $1.5$ achieved by a combinatorial approach due to Kortsarz and Nutov [ACM Transactions on Algorithms 2016], and also by an SDP-based approach by Cheriyan and Gao [Algorithmica 2017]. Moreover, an elegant LP-based $(1.5+ε)$-approximation has also been found very recently by Fiorini, Groß, Könemann, and Sanitá [SODA 2018]. In this paper, we show that an approximation factor below $1.5$ can be achieved, by presenting a $1.458$-approximation that is based on several new techniques.
How Constraints Affect Content: The Case of Twitter's Switch from 140 to 280 Characters
Venue: arXiv cs.SI 2018
Year: 2018

It is often said that constraints affect creative production, both in terms of form and quality. Online social media platforms frequently impose constraints on the content that users can produce, limiting the range of possible contributions. Do these restrictions tend to push creators towards producing more or less successful content? How do creators adapt their contributions to fit the limits imposed by social media platforms? To answer these questions, we conduct an observational study of a recent event: on November 7, 2017, Twitter changed the maximum allowable length of a tweet from 140 to 280 characters, thereby significantly altering its signature constraint. In the first study of this switch, we compare tweets with nearly or exactly 140 characters before the change to tweets of the same length posted after the change. This setup enables us to characterize how users alter their tweets to fit the constraint and how this affects their tweets' success. We find that in response to a length constraint, users write more tersely, use more abbreviations and contracted forms, and use fewer definite articles. Also, although in general tweet success increases with length, we find initial evidence that tweets made to fit the 140-character constraint tend to be more successful than similar-length tweets written when the constraint was removed, suggesting that the length constraint improved tweet quality.
Cross-cultural Usability Issues in E/M-Learning
Venue: arXiv cs.HC 2018
Year: 2018

This paper gives an overview of electronic learning (E-Learning) and mobile learning (M-Learning) adoption and diffusion trends, as well as their particular traits, characteristics and issues, especially in terms of cross-cultural and universal usability. E-Learning and M-Learning models using web services and cloud computing, as well as associated security concerns are all addressed. The benefits and enhancements that accrue from using mobile and other internet devices for the purposes of learning in academia are discussed. The differences between traditional classroom-based learning, distance learning, E-Learning and M-Learning models are compared and some conclusions are drawn.
Minimal Support Vector Machine
Venue: arXiv cs.LG 2018
Year: 2018

Support Vector Machine (SVM) is an efficient classification approach, which finds a hyperplane to separate data from different classes. This hyperplane is determined by support vectors. In existing SVM formulations, the objective function uses L2 norm or L1 norm on slack variables. The number of support vectors is a measure of generalization errors. In this work, we propose a Minimal SVM, which uses L0.5 norm on slack variables. The result model further reduces the number of support vectors and increases the classification performance.