OpenRaiser/Intern-Atlas huggingface dataset:
Using Multiple Seasonal Holt-Winters Exponential Smoothing to Predict Cloud Resource Provisioning
Venue: arXiv cs.DC 2017
Year: 2017

Elasticity is one of the key features of cloud computing that attracts many SaaS providers to minimize their services' cost. Cost is minimized by automatically provision and release computational resources depend on actual computational needs. However, delay of starting up new virtual resources can cause Service Level Agreement violation. Consequently, predicting cloud resources provisioning gains a lot of attention to scale computational resources in advance. However, most of current approaches do not consider multi-seasonality in cloud workloads. This paper proposes cloud resource provisioning prediction algorithm based on Holt-Winters exponential smoothing method. The proposed algorithm extends Holt-Winters exponential smoothing method to model cloud workload with multi-seasonal cycles. Prediction accuracy of the proposed algorithm has been improved by employing Artificial Bee Colony algorithm to optimize its parameters. Performance of the proposed algorithm has been evaluated and compared with double and triple exponential smoothing methods. Our results have shown that the proposed algorithm outperforms other methods.
An Introduction to Liquid Haskell
Venue: arXiv cs.PL 2017
Year: 2017

This paper is a tutorial introducing the underlying technology and the use of the tool Liquid Haskell, a type-checker for the functional language Haskell that can help programmers to verify non-trivial properties of their programs with a low effort. The first sections introduce the technology of Liquid Types by explaining its principles and summarizing how its type inference algorithm manages to prove properties. The remaining sections present a selection of Haskell examples and show the kind of properties that can be proved with the system.
A Study on Arbitrarily Varying Channels with Causal Side Information at the Encoder
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we study two models of arbitrarily varying channels, when causal side information is available at the encoder in a causal manner. First, we study the arbitrarily varying channel (AVC) with input and state constraints, when the encoder has state information in a causal manner. Lower and upper bounds on the random code capacity are developed. A lower bound on the deterministic code capacity is established in the case of a message-averaged input constraint. In the setting where a state constraint is imposed on the jammer, while the user is under no constraints, the random code bounds coincide, and the random code capacity is determined. Furthermore, for this scenario, a generalized non-symmetrizability condition is stated, under which the deterministic code capacity coincides with the random code capacity. A second model considered in our work is the arbitrarily varying degraded broadcast channel with causal side information at the encoder (without constraints). We establish inner and outer bounds on both the random code capacity region and the deterministic code capacity region. The capacity region is then determined for a class of channels satisfying a condition on the mutual informations between the strategy variables and the channel outputs. As an example, we show that the condition holds for the arbitrarily varying binary symmetric broadcast channel, and we find the corresponding capacity region.
Cloud-Aided State Estimation of A Full-Car Semi-Active Suspension System
Venue: arXiv cs.SY 2017
Year: 2017

In this work, we investigate a state estimation problem for a full-car semi-active suspension system. To account for the complex calculation and optimization problems, a vehicle-to- cloud-to-vehicle (V2C2V) scheme is utilized. Moving horizon estimation is introduced for the state estimation system design. All the optimization problems are solved in a remotely-embedded agent with high computational ability. Measurements and state estimates are transmitted between the vehicle and the remote agent via networked communication channels. The effectiveness of the proposed method is illustrated via a set of simulations.
The Massey's method for sport rating: a network science perspective
Venue: arXiv cs.SI 2017
Year: 2017

We revisit the Massey's method for rating and ranking in sports and contextualize it as a general centrality measure in network science.
Extracting Point of Interest and Classifying Environment for Low Sampling Crowd Sensing Smartphone Sensor Data
Venue: arXiv cs.CY 2017
Year: 2017

The advancement of smartphones with various type of sensors enabled us to harness diverse information with crowd sensing mobile application. However, traditional approaches have suffered drawbacks such as high battery consumption as a trade off to obtain high accuracy data using high sampling rate. To mitigate the battery consumption, we proposed low sampling point of interest (POI) extraction framework, which is built upon validation based stay points detection (VSPD) and sensor fusion based environment classification (SFEC). We studied various of clustering algorithm and showed that density based spatial clustering of application with noise(DBSCAN) algorithms produce most accurate result among existing methods. The SFEC model is utilized for classifying the indoor or outdoor environment of the POI clustered earlier by VSPD. Real world data are collected, bench-marked using existing clustering method to denote effectiveness of low sampling rate model in high noise spatial temporal data.
Polar Codes for Arbitrary Classical-Quantum Channels and Arbitrary cq-MACs
Venue: arXiv cs.IT 2017
Year: 2017

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arıkan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels which project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in $O(N\log N)$ operations, where $N$ is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than $2^{-N^β}$ for any $β<\frac{1}{2}$.
Scaling Binarized Neural Networks on Reconfigurable Logic
Venue: arXiv cs.CV 2017
Year: 2017

Binarized neural networks (BNNs) are gaining interest in the deep learning community due to their significantly lower computational and memory cost. They are particularly well suited to reconfigurable logic devices, which contain an abundance of fine-grained compute resources and can result in smaller, lower power implementations, or conversely in higher classification rates. Towards this end, the Finn framework was recently proposed for building fast and flexible field programmable gate array (FPGA) accelerators for BNNs. Finn utilized a novel set of optimizations that enable efficient mapping of BNNs to hardware and implemented fully connected, non-padded convolutional and pooling layers, with per-layer compute resources being tailored to user-provided throughput requirements. However, FINN was not evaluated on larger topologies due to the size of the chosen FPGA, and exhibited decreased accuracy due to lack of padding. In this paper, we improve upon Finn to show how padding can be employed on BNNs while still maintaining a 1-bit datapath and high accuracy. Based on this technique, we demonstrate numerous experiments to illustrate flexibility and scalability of the approach. In particular, we show that a large BNN requiring 1.2 billion operations per frame running on an ADM-PCIE-8K5 platform can classify images at 12 kFPS with 671 us latency while drawing less than 41 W board power and classifying CIFAR-10 images at 88.7% accuracy. Our implementation of this network achieves 14.8 trillion operations per second. We believe this is the fastest classification rate reported to date on this benchmark at this level of accuracy.
Space-time balancing domain decomposition
Venue: arXiv cs.NA 2017
Year: 2017

In this work, we propose two-level space-time domain decomposition preconditioners for parabolic problems discretized using finite elements. They are motivated as an extension to space-time of balancing domain decomposition by constraints preconditioners. The key ingredients to be defined are the sub-assembled space and operator, the coarse degrees of freedom (DOFs) in which we want to enforce continuity among subdomains at the preconditioner level, and the transfer operator from the sub-assembled to the original finite element space. With regard to the sub-assembled operator, a perturbation of the time derivative is needed to end up with a well-posed preconditioner. The set of coarse DOFs includes the time average (at the space-time subdomain) of classical space constraints plus new constraints between consecutive subdomains in time. Numerical experiments show that the proposed schemes are weakly scalable in time, i.e., we can efficiently exploit increasing computational resources to solve more time steps in the same {total elapsed} time. Further, the scheme is also weakly space-time scalable, since it leads to asymptotically constant iterations when solving larger problems both in space and time. Excellent {wall clock} time weak scalability is achieved for space-time parallel solvers on some thousands of cores.
Comparison of viscoelastic finite element models for laminated glass beams
Venue: arXiv cs.CE 2017
Year: 2017

Laminated glass elements, which consist of stiff elastic glass layers connected with a compliant viscoelastic polymer foil, exhibit geometrically non-linear and time/temperature-sensitive behavior. In computational modeling, the viscoelastic effects are often neglected or a detailed continuum formulation typically based on the volumetric-deviatoric elastic-viscoelastic split is used for the interlayer. Four layerwise beam theories are introduced in this paper, which differ in the non-linear beam formulation at the layer level (von Kármán/Reissner) and in constitutive assumptions for the interlayer (a viscoelastic solid with the time-independent bulk modulus/Poisson ratio). We perform detailed verification and validation studies at different temperatures and compare the accuracy of the selected formulation with simplified elastic solutions used in practice. We show that all the four formulations predict very similar responses. Therefore, our suggestion is to use the most straightforward formulation that combines the von Kármán model with the assumption of time-independent Poisson ratio. The simplified elastic model mostly provides a response in satisfactory agreement with full viscoelastic solutions. However, it can lead to unsafe or inaccurate predictions for rapid changes of loading. These findings provide a suitable basis for extensions towards laminated plates and glass layer fracture, owing to the modular format of layerwise theories.
A survey of location inference techniques on Twitter
Venue: arXiv cs.SI 2017
Year: 2017

The increasing popularity of the social networking service, Twitter, has made it more involved in day-to-day communications, strengthening social relationships and information dissemination. Conversations on Twitter are now being explored as indicators within early warning systems to alert of imminent natural disasters such earthquakes and aid prompt emergency responses to crime. Producers are privileged to have limitless access to market perception from consumer comments on social media and microblogs. Targeted advertising can be made more effective based on user profile information such as demography, interests and location. While these applications have proven beneficial, the ability to effectively infer the location of Twitter users has even more immense value. However, accurately identifying where a message originated from or author's location remains a challenge thus essentially driving research in that regard. In this paper, we survey a range of techniques applied to infer the location of Twitter users from inception to state-of-the-art. We find significant improvements over time in the granularity levels and better accuracy with results driven by refinements to algorithms and inclusion of more spatial features.
Multivariate predictions of local reduced-order-model errors and dimensions
Venue: arXiv cs.NA 2017
Year: 2017

This paper introduces multivariate input-output models to predict the errors and bases dimensions of local parametric Proper Orthogonal Decomposition reduced-order models. We refer to these multivariate mappings as the MP-LROM models. We employ Gaussian Processes and Artificial Neural Networks to construct approximations of these multivariate mappings. Numerical results with a viscous Burgers model illustrate the performance and potential of the machine learning based regression MP-LROM models to approximate the characteristics of parametric local reduced-order models. The predicted reduced-order models errors are compared against the multi-fidelity correction and reduced order model error surrogates methods predictions, whereas the predicted reduced-order dimensions are tested against the standard method based on the spectrum of snapshots matrix. Since the MP-LROM models incorporate more features and elements to construct the probabilistic mappings they achieve more accurate results. However, for high-dimensional parametric spaces, the MP-LROM models might suffer from the curse of dimensionality. Scalability challenges of MP-LROM models and the feasible ways of addressing them are also discussed in this study.
The Velocity of the Decoding Wave for Spatially Coupled Codes on BMS Channels
Venue: arXiv cs.IT 2017
Year: 2017

We consider the dynamics of belief propagation decoding of spatially coupled Low-Density Parity-Check codes. It has been conjectured that after a short transient phase, the profile of "error probabilities" along the spatial direction of a spatially coupled code develops a uniquely-shaped wave-like solution that propagates with constant velocity v. Under this assumption, and for transmission over general Binary Memoryless Symmetric channels, we derive a formula for v. We also propose approximations that are simpler to compute and support our findings using numerical data.
Tumour Ellipsification in Ultrasound Images for Treatment Prediction in Breast Cancer
Venue: arXiv cs.CV 2017
Year: 2017

Recent advances in using quantitative ultrasound (QUS) methods have provided a promising framework to non-invasively and inexpensively monitor or predict the effectiveness of therapeutic cancer responses. One of the earliest steps in using QUS methods is contouring a region of interest (ROI) inside the tumour in ultrasound B-mode images. While manual segmentation is a very time-consuming and tedious task for human experts, auto-contouring is also an extremely difficult task for computers due to the poor quality of ultrasound B-mode images. However, for the purpose of cancer response prediction, a rough boundary of the tumour as an ROI is only needed. In this research, a semi-automated tumour localization approach is proposed for ROI estimation in ultrasound B-mode images acquired from patients with locally advanced breast cancer (LABC). The proposed approach comprised several modules, including 1) feature extraction using keypoint descriptors, 2) augmenting the feature descriptors with the distance of the keypoints to the user-input pixel as the centre of the tumour, 3) supervised learning using a support vector machine (SVM) to classify keypoints as "tumour" or "non-tumour", and 4) computation of an ellipse as an outline of the ROI representing the tumour. Experiments with 33 B-mode images from 10 LABC patients yielded promising results with an accuracy of 76.7% based on the Dice coefficient performance measure. The results demonstrated that the proposed method can potentially be used as the first stage in a computer-assisted cancer response prediction system for semi-automated contouring of breast tumours.
Scalable and Incremental Learning of Gaussian Mixture Models
Venue: arXiv cs.LG 2017
Year: 2017

This work presents a fast and scalable algorithm for incremental learning of Gaussian mixture models. By performing rank-one updates on its precision matrices and determinants, its asymptotic time complexity is of \BigO{NKD^2} for $N$ data points, $K$ Gaussian components and $D$ dimensions. The resulting algorithm can be applied to high dimensional tasks, and this is confirmed by applying it to the classification datasets MNIST and CIFAR-10. Additionally, in order to show the algorithm's applicability to function approximation and control tasks, it is applied to three reinforcement learning tasks and its data-efficiency is evaluated.
Can We Find Documents in Web Archives without Knowing their Contents?
Venue: arXiv cs.IR 2017
Year: 2017

Recent advances of preservation technologies have led to an increasing number of Web archive systems and collections. These collections are valuable to explore the past of the Web, but their value can only be uncovered with effective access and exploration mechanisms. Ideal search and rank- ing methods must be robust to the high redundancy and the temporal noise of contents, as well as scalable to the huge amount of data archived. Despite several attempts in Web archive search, facilitating access to Web archive still remains a challenging problem. In this work, we conduct a first analysis on different ranking strategies that exploit evidences from metadata instead of the full content of documents. We perform a first study to compare the usefulness of non-content evidences to Web archive search, where the evidences are mined from the metadata of file headers, links and URL strings only. Based on these findings, we propose a simple yet surprisingly effective learning model that combines multiple evidences to distinguish "good" from "bad" search results. We conduct empirical experiments quantitatively as well as qualitatively to confirm the validity of our proposed method, as a first step towards better ranking in Web archives taking meta- data into account.
Attention Allocation Aid for Visual Search
Venue: arXiv cs.HC 2017
Year: 2017

This paper outlines the development and testing of a novel, feedback-enabled attention allocation aid (AAAD), which uses real-time physiological data to improve human performance in a realistic sequential visual search task. Indeed, by optimizing over search duration, the aid improves efficiency, while preserving decision accuracy, as the operator identifies and classifies targets within simulated aerial imagery. Specifically, using experimental eye-tracking data and measurements about target detectability across the human visual field, we develop functional models of detection accuracy as a function of search time, number of eye movements, scan path, and image clutter. These models are then used by the AAAD in conjunction with real time eye position data to make probabilistic estimations of attained search accuracy and to recommend that the observer either move on to the next image or continue exploring the present image. An experimental evaluation in a scenario motivated from human supervisory control in surveillance missions confirms the benefits of the AAAD.
An Explanation of Nakamoto's Analysis of Double-spend Attacks
Venue: arXiv cs.CR 2017
Year: 2017

The fundamental attack against blockchain systems is the double-spend attack. In this tutorial, we provide a very detailed explanation of just one section of Satoshi Nakamoto's original paper where the attack's probability of success is stated. We show the derivation of the mathematics relied upon by Nakamoto to create a model of the attack. We also validate the model with a Monte Carlo simulation, and we determine which model component is not perfect.
Throughput-Optimal Scheduling for Multi-Hop Networked Transportation Systems With Switch-Over Delay
Venue: arXiv cs.NI 2017
Year: 2017

The emerging connected-vehicle technology provides a new dimension in developing more intelligent traffic control algorithms for signalized intersections in networked transportation systems. An important challenge for the scheduling problem in networked transportation systems is the switch-over delay caused by the guard time before any traffic signal change. The switch-over delay can result in significant loss of system capacity and hence needs to be accommodated in the scheduling design. To tackle this challenge, we propose a distributed online scheduling policy that extends the well-known Max-Pressure policy to address switch-over delay by introducing a bias factor toward the current schedule. We prove that the proposed policy is throughput-optimal with switch-over delay. Furthermore, the proposed policy remains optimal when there are both connected signalized intersections and conventional fixed-time ones in the system. With connected-vehicle technology, the proposed policy can be easily incorporated into the current transportation systems without additional infrastructure. Through extensive simulation in VISSIM, we show that our policy indeed outperforms the existing popular policies.
Optimal Elephant Flow Detection
Venue: arXiv cs.DS 2017
Year: 2017

Monitoring the traffic volumes of elephant flows, including the total byte count per flow, is a fundamental capability for online network measurements. We present an asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves on previous approaches, which can only count the number of packets in constant time. We evaluate our work on real packet traces, demonstrating an up to X2.5 speedup compared to the best alternative.
The Birth of Collective Memories: Analyzing Emerging Entities in Text Streams
Venue: arXiv cs.IR 2017
Year: 2017

We study how collective memories are formed online. We do so by tracking entities that emerge in public discourse, that is, in online text streams such as social media and news streams, before they are incorporated into Wikipedia, which, we argue, can be viewed as an online place for collective memory. By tracking how entities emerge in public discourse, i.e., the temporal patterns between their first mention in online text streams and subsequent incorporation into collective memory, we gain insights into how the collective remembrance process happens online. Specifically, we analyze nearly 80,000 entities as they emerge in online text streams before they are incorporated into Wikipedia. The online text streams we use for our analysis comprise of social media and news streams, and span over 579 million documents in a timespan of 18 months. We discover two main emergence patterns: entities that emerge in a "bursty" fashion, i.e., that appear in public discourse without a precedent, blast into activity and transition into collective memory. Other entities display a "delayed" pattern, where they appear in public discourse, experience a period of inactivity, and then resurface before transitioning into our cultural collective memory.
Light Source Estimation with Analytical Path-tracing
Venue: arXiv cs.CV 2017
Year: 2017

We present a novel algorithm for light source estimation in scenes reconstructed with a RGB-D camera based on an analytically-derived formulation of path-tracing. Our algorithm traces the reconstructed scene with a custom path-tracer and computes the analytical derivatives of the light transport equation from principles in optics. These derivatives are then used to perform gradient descent, minimizing the photometric error between one or more captured reference images and renders of our current lighting estimation using an environment map parameterization for light sources. We show that our approach of modeling all light sources as points at infinity approximates lights located near the scene with surprising accuracy. Due to the analytical formulation of derivatives, optimization to the solution is considerably accelerated. We verify our algorithm using both real and synthetic data.