OpenRaiser/Intern-Atlas huggingface dataset:
Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points
Venue: arXiv cs.CG 2019
Year: 2019

We consider a bichromatic two-center problem for pairs of points. Given a set $S$ of $n$ pairs of points in the plane, for every pair, we want to assign a red color to one point and a blue color to the other, in such a way that the value $\max\{r_1,r_2\}$ is minimized, where $r_1$ (resp., $r_2$) is the radius of the smallest enclosing disk of all red (resp., blue) points. Previously, an exact algorithm of $O(n^3\log^2 n)$ time and a $(1+\varepsilon)$-approximate algorithm of $O(n + (1/\varepsilon)^6 \log^2 (1/\varepsilon))$ time were known. In this paper, we propose a new exact algorithm of $O(n^2\log^2 n)$ time and a new $(1+\varepsilon)$-approximate algorithm of $O(n + (1/\varepsilon)^3 \log^2 (1/\varepsilon))$ time.
The Psychological and Physiological Part of Emotions: Multimodal Approximation for Valence Classification
Venue: arXiv cs.HC 2019
Year: 2019

In order to develop more precise and functional affective applications, it is necessary to achieve a balance between the psychology and the engineering applied to emotions. Signals from the central and peripheral nervous systems have been used for emotion recognition purposes, however, their operation and the relationship between them remains unknown. In this context, in the present work we have tried to approach the study of the psychobiology of both systems in order to generate a computational model for the recognition of emotions in the dimension of valence. To this end, the electroencephalography (EEG) signal, electrocardiography (ECG) signal and skin temperature of 24 subjects have been studied. Each methodology has been evaluated individually, finding characteristic patterns of positive and negative emotions in each of them. After feature selection of each methodology, the results of the classification showed that, although the classification of emotions is possible at both central and peripheral levels, the multimodal approach did not improve the results obtained through the EEG alone. In addition, differences have been observed between cerebral and physiological responses in the processing emotions by separating the sample by sex; though, the differences between men and women were only notable at the physiological level.
On generating network traffic datasets with synthetic attacks for intrusion detection
Venue: arXiv cs.CR 2019
Year: 2019

Most research in the area of intrusion detection requires datasets to develop, evaluate or compare systems in one way or another. In this field, however, finding suitable datasets is a challenge on to itself. Most publicly available datasets have negative qualities that limit their usefulness. In this article, we propose ID2T (Intrusion Detection Dataset Toolkit) to tackle this problem. ID2T facilitates the creation of labeled datasets by injecting synthetic attacks into background traffic. The injected synthetic attacks blend themselves with the background traffic by mimicking the background traffic's properties to eliminate any trace of ID2T's usage. This work has three core contribution areas. First, we present a comprehensive survey on intrusion detection datasets. In the survey, we propose a classification to group the negative qualities we found in the datasets. Second, the architecture of ID2T is revised, improved and expanded. The architectural changes enable ID2T to inject recent and advanced attacks such as the widespread EternalBlue exploit or botnet communication patterns. The toolkit's new functionality provides a set of tests, known as TIDED (Testing Intrusion Detection Datasets), that help identify potential defects in the background traffic into which attacks are injected. Third, we illustrate how ID2T is used in different use-case scenarios to evaluate the performance of anomaly and signature-based intrusion detection systems in a reproducible manner. ID2T is open source software and is made available to the community to expand its arsenal of attacks and capabilities.
High-Performance Support Vector Machines and Its Applications
Venue: arXiv cs.LG 2019
Year: 2019

The support vector machines (SVM) algorithm is a popular classification technique in data mining and machine learning. In this paper, we propose a distributed SVM algorithm and demonstrate its use in a number of applications. The algorithm is named high-performance support vector machines (HPSVM). The major contribution of HPSVM is two-fold. First, HPSVM provides a new way to distribute computations to the machines in the cloud without shuffling the data. Second, HPSVM minimizes the inter-machine communications in order to maximize the performance. We apply HPSVM to some real-world classification problems and compare it with the state-of-the-art SVM technique implemented in R on several public data sets. HPSVM achieves similar or better results.
Gender Classification from Iris Texture Images Using a New Set of Binary Statistical Image Features
Venue: arXiv cs.CV 2019
Year: 2019

Soft biometric information such as gender can contribute to many applications like as identification and security. This paper explores the use of a Binary Statistical Features (BSIF) algorithm for classifying gender from iris texture images captured with NIR sensors. It uses the same pipeline for iris recognition systems consisting of iris segmentation, normalisation and then classification. Experiments show that applying BSIF is not straightforward since it can create artificial textures causing misclassification. In order to overcome this limitation, a new set of filters was trained from eye images and different sized filters with padding bands were tested on a subject-disjoint database. A Modified-BSIF (MBSIF) method was implemented. The latter achieved better gender classification results (94.6\% and 91.33\% for the left and right eye respectively). These results are competitive with the state of the art in gender classification. In an additional contribution, a novel gender labelled database was created and it will be available upon request.
Time-series Insights into the Process of Passing or Failing Online University Courses using Neural-Induced Interpretable Student States
Venue: arXiv cs.CL 2019
Year: 2019

This paper addresses a key challenge in Educational Data Mining, namely to model student behavioral trajectories in order to provide a means for identifying students most at-risk, with the goal of providing supportive interventions. While many forms of data including clickstream data or data from sensors have been used extensively in time series models for such purposes, in this paper we explore the use of textual data, which is sometimes available in the records of students at large, online universities. We propose a time series model that constructs an evolving student state representation using both clickstream data and a signal extracted from the textual notes recorded by human mentors assigned to each student. We explore how the addition of this textual data improves both the predictive power of student states for the purpose of identifying students at risk for course failure as well as for providing interpretable insights about student course engagement processes.
Full-stack Optimization for Accelerating CNNs with FPGA Validation
Venue: arXiv cs.LG 2019
Year: 2019

We present a full-stack optimization framework for accelerating inference of CNNs (Convolutional Neural Networks) and validate the approach with field-programmable gate arrays (FPGA) implementations. By jointly optimizing CNN models, computing architectures, and hardware implementations, our full-stack approach achieves unprecedented performance in the trade-off space characterized by inference latency, energy efficiency, hardware utilization and inference accuracy. As a validation vehicle, we have implemented a 170MHz FPGA inference chip achieving 2.28ms latency for the ImageNet benchmark. The achieved latency is among the lowest reported in the literature while achieving comparable accuracy. However, our chip shines in that it has 9x higher energy efficiency compared to other implementations achieving comparable latency. A highlight of our full-stack approach which attributes to the achieved high energy efficiency is an efficient Selector-Accumulator (SAC) architecture for implementing the multiplier-accumulator (MAC) operation present in any digital CNN hardware. For instance, compared to a FPGA implementation for a traditional 8-bit MAC, SAC substantially reduces required hardware resources (4.85x fewer Look-up Tables) and power consumption (2.48x).
Caveat emptor: the risks of using big data for human development
Venue: arXiv cs.CY 2019
Year: 2019

Big data revolution promises to be instrumental in facilitating sustainable development in many sectors of life such as education, health, agriculture, and in combating humanitarian crises and violent conflicts. However, lurking beneath the immense promises of big data are some significant risks such as (1) the potential use of big data for unethical ends; (2) its ability to mislead through reliance on unrepresentative and biased data; and (3) the various privacy and security challenges associated with data (including the danger of an adversary tampering with the data to harm people). These risks can have severe consequences and a better understanding of these risks is the first step towards mitigation of these risks. In this paper, we highlight the potential dangers associated with using big data, particularly for human development.
3D BAT: A Semi-Automatic, Web-based 3D Annotation Toolbox for Full-Surround, Multi-Modal Data Streams
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we focus on obtaining 2D and 3D labels, as well as track IDs for objects on the road with the help of a novel 3D Bounding Box Annotation Toolbox (3D BAT). Our open source, web-based 3D BAT incorporates several smart features to improve usability and efficiency. For instance, this annotation toolbox supports semi-automatic labeling of tracks using interpolation, which is vital for downstream tasks like tracking, motion planning and motion prediction. Moreover, annotations for all camera images are automatically obtained by projecting annotations from 3D space into the image domain. In addition to the raw image and point cloud feeds, a Masterview consisting of the top view (bird's-eye-view), side view and front views is made available to observe objects of interest from different perspectives. Comparisons of our method with other publicly available annotation tools reveal that 3D annotations can be obtained faster and more efficiently by using our toolbox.
Optimal Power Allocation for Minimizing Outage Probability of UAV Relay Communications
Venue: arXiv cs.IT 2019
Year: 2019

Unmanned aerial vehicle (UAV) networks have grown rapidly in recent years and become attractive for various emergence communications scenarios. In this paper, we consider a UAV acting as a relay node to assist wireless transmissions from a base station (BS) to a ground user (GUs). A closed-form expression of outage probability for the BS-GUs transmission via UAV relaying is derived over Rician fading channels. We then formulate an optimization problem to minimize the outage probability of UAV relay communications with a constraint on the total transit power of the BS and GUs. It is proved that our formulated optimization problem is convex and an optimal power allocation solution is found for the outage probability minimization. Simulation results demonstrate that with an increasing power allocation factor, the outage probability initially decreases and then starts to increase, showing the existence of an optimal power allocation solution. Additionally, it is shown that the proposed optimal power allocation scheme significantly outperforms the conventional equal power allocation in terms of the outage probability.
26ms Inference Time for ResNet-50: Towards Real-Time Execution of all DNNs on Smartphone
Venue: arXiv cs.LG 2019
Year: 2019

With the rapid emergence of a spectrum of high-end mobile devices, many applications that required desktop-level computation capability formerly can now run on these devices without any problem. However, without a careful optimization, executing Deep Neural Networks (a key building block of the real-time video stream processing that is the foundation of many popular applications) is still challenging, specifically, if an extremely low latency or high accuracy inference is needed. This work presents CADNN, a programming framework to efficiently execute DNN on mobile devices with the help of advanced model compression (sparsity) and a set of thorough architecture-aware optimization. The evaluation result demonstrates that CADNN outperforms all the state-of-the-art dense DNN execution frameworks like TensorFlow Lite and TVM.
Herding Effect based Attention for Personalized Time-Sync Video Recommendation
Venue: arXiv cs.MM 2019
Year: 2019

Time-sync comment (TSC) is a new form of user-interaction review associated with real-time video contents, which contains a user's preferences for videos and therefore well suited as the data source for video recommendations. However, existing review-based recommendation methods ignore the context-dependent (generated by user-interaction), real-time, and time-sensitive properties of TSC data. To bridge the above gaps, in this paper, we use video images and users' TSCs to design an Image-Text Fusion model with a novel Herding Effect Attention mechanism (called ITF-HEA), which can predict users' favorite videos with model-based collaborative filtering. Specifically, in the HEA mechanism, we weight the context information based on the semantic similarities and time intervals between each TSC and its context, thereby considering influences of the herding effect in the model. Experiments show that ITF-HEA is on average 3.78\% higher than the state-of-the-art method upon F1-score in baselines.
Deterministic Leader Election in Programmable Matter
Venue: arXiv cs.DC 2019
Year: 2019

Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.
Online Circle Packing
Venue: arXiv cs.DS 2019
Year: 2019

We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles and without moving previously packed circles. We present an algorithm that packs any online sequence of circles with a combined area not larger than 0.350389 0.350389 of the square's area, improving the previous best value of π/10 \approx 0.31416; even in an offline setting, there is an upper bound of π/(3 + 2 \sqrt{2}) \approx 0.5390. If only circles with radii of at least 0.026622 are considered, our algorithm achieves the higher value 0.375898. As a byproduct, we give an online algorithm for packing circles into a 1\times b rectangle with b \geq 1. This algorithm is worst case-optimal for b \geq 2.36.
Can the Optimizer Cost be Used to Predict Query Execution Times?
Venue: arXiv cs.DB 2019
Year: 2019

Predicting the execution time of queries is an important problem with applications in scheduling, service level agreements and error detection. During query planning, a cost is associated with the chosen execution plan and used to rank competing plans. It would be convenient to use that cost to predict execution time, but it has been claimed in the literature that this is not possible. In this paper, we thoroughly investigate this claim considering both linear and non-linear models. We find that the accuracy using more complex models with only the optimizer cost is comparable to the reported accuracy in the literature. The most accurate method in the literature is nearest-neighbour regression which does not produce a model. The published results used a large feature set to identify nearest neighbours. We show that it is possible to achieve the same level of accuracy using only the cost to identify nearest neighbours. Using a smaller feature set brings the advantages of reduced overhead in terms of both storage space for the training data and the time to produce a prediction.
Engineering a QoS Provider Mechanism for Edge Computing with Deep Reinforcement Learning
Venue: arXiv cs.NI 2019
Year: 2019

With the development of new system solutions that integrate traditional cloud computing with the edge/fog computing paradigm, dynamic optimization of service execution has become a challenge due to the edge computing resources being more distributed and dynamic. How to optimize the execution to provide Quality of Service (QoS) in edge computing depends on both the system architecture and the resource allocation algorithms in place. We design and develop a QoS provider mechanism, as an integral component of a fog-to-cloud system, to work in dynamic scenarios by using deep reinforcement learning. We choose reinforcement learning since it is particularly well suited for solving problems in dynamic and adaptive environments where the decision process needs to be frequently updated. We specifically use a Deep Q-learning algorithm that optimizes QoS by identifying and blocking devices that potentially cause service disruption due to dynamicity. We compare the reinforcement learning based solution with state-of-the-art heuristics that use telemetry data, and analyze pros and cons.
Minimum Ply Covering of Points with Disks and Squares
Venue: arXiv cs.CG 2019
Year: 2019

Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set $P$ of points and a set $S$ of geometric objects, both in the plane, our goal is to find a subset $S'$ of $S$ that covers all points of $P$ while minimizing the maximum number of objects covering any point in the plane (not only points of $P$). For objects that are unit squares and unit disks, this problem is NP-hard and cannot be approximated by a ratio smaller than 2. We present 2-approximation algorithms for this problem with respect to unit squares and unit disks. Our algorithms run in polynomial time when the optimum objective value is bounded by a constant. Motivated by channel-assignment in wireless networks, we consider a variant of the problem where the selected unit disks must be 3-colorable, i.e., colored by three colors such that all disks of the same color are pairwise disjoint. We present a polynomial-time algorithm that achieves a 2-approximate solution, i.e., a solution that is 6-colorable. We also study the weighted version of the problem in dimension one, where $P$ and $S$ are points and weighted intervals on a line, respectively. We present an algorithm that solves this problem in $O(n + m + M )$-time where $n$ is the number of points, $m$ is the number of intervals, and $M$ is the number of pairs of overlapping intervals. This repairs a solution claimed by Nandy, Pandit, and Roy in CCCG 2017.
Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update
Venue: arXiv cs.DS 2019
Year: 2019

We present an improved $(ε, δ)$-jointly differentially private algorithm for packing problems. Our algorithm gives a feasible output that is approximately optimal up to an $αn$ additive factor as long as the supply of each resource is at least $\tilde{O}(\sqrt{m} / αε)$, where $m$ is the number of resources. This improves the previous result by Hsu et al.~(SODA '16), which requires the total supply to be at least $\tilde{O}(m^2 / αε)$, and only guarantees approximate feasibility in terms of total violation. Further, we complement our algorithm with an almost matching hardness result, showing that $Ω(\sqrt{m \ln(1/δ)} / αε)$ supply is necessary for any $(ε, δ)$-jointly differentially private algorithm to compute an approximately optimal packing solution. Finally, we introduce an alternative approach that runs in linear time, is exactly truthful, can be implemented online, and can be $ε$-jointly differentially private, but requires a larger supply of each resource.
The Price of Gold: Curiosity?
Venue: arXiv cs.DL 2019
Year: 2019

Gold open access as characterised by the payment of an article processing charge (APC) has become one of the dominant models in open access publication. This paper examines an extreme hypothetical case in which the APC model is the only model and the systematic issues that could develop in such a scenario.
What will you do next? A sequence analysis on the student transitions between online platforms in blended courses
Venue: arXiv cs.CY 2019
Year: 2019

Students' interactions with online tools can provide us with insights into their study and work habits. Prior research has shown that these habits, even as simple as the number of actions or the time spent on online platforms can distinguish between the higher performing students and low-performers. These habits are also often used to predict students' performance in classes. One key feature of these actions that is often overlooked is how and when the students transition between different online platforms. In this work, we study sequences of student transitions between online tools in blended courses and identify which habits make the most difference between the higher and lower performing groups. While our results showed that most of the time students focus on a single tool, we were able to find patterns in their transitions to differentiate high and low performing groups. These findings can help instructors to provide procedural guidance to the students, as well as to identify harmful habits and make timely interventions.
Leveraging Deep Learning to Improve the Performance Predictability of Cloud Microservices
Venue: arXiv cs.DC 2019
Year: 2019

Performance unpredictability is a major roadblock towards cloud adoption, and has performance, cost, and revenue ramifications. Predictable performance is even more critical as cloud services transition from monolithic designs to microservices. Detecting QoS violations after they occur in systems with microservices results in long recovery times, as hotspots propagate and amplify across dependent services. We present Seer, an online cloud performance debugging system that leverages deep learning and the massive amount of tracing data cloud systems collect to learn spatial and temporal patterns that translate to QoS violations. Seer combines lightweight distributed RPC-level tracing, with detailed low-level hardware monitoring to signal an upcoming QoS violation, and diagnose the source of unpredictable performance. Once an imminent QoS violation is detected, Seer notifies the cluster manager to take action to avoid performance degradation altogether. We evaluate Seer both in local clusters, and in large-scale deployments of end-to-end applications built with microservices with hundreds of users. We show that Seer correctly anticipates QoS violations 91% of the time, and avoids the QoS violation to begin with in 84% of cases. Finally, we show that Seer can identify application-level design bugs, and provide insights on how to better architect microservices to achieve predictable performance.