OpenRaiser/Intern-Atlas huggingface dataset:
Techniques and tools for measuring energy efficiency of scientific software applications
Venue: arXiv cs.DC 2014
Year: 2014

The scale of scientific High Performance Computing (HPC) and High Throughput Computing (HTC) has increased significantly in recent years, and is becoming sensitive to total energy use and cost. Energy-efficiency has thus become an important concern in scientific fields such as High Energy Physics (HEP). There has been a growing interest in utilizing alternate architectures, such as low power ARM processors, to replace traditional Intel x86 architectures. Nevertheless, even though such solutions have been successfully used in mobile applications with low I/O and memory demands, it is unclear if they are suitable and more energy-efficient in the scientific computing environment. Furthermore, there is a lack of tools and experience to derive and compare power consumption between the architectures for various workloads, and eventually to support software optimizations for energy efficiency. To that end, we have performed several physical and software-based measurements of workloads from HEP applications running on ARM and Intel architectures, and compare their power consumption and performance. We leverage several profiling tools (both in hardware and software) to extract different characteristics of the power use. We report the results of these measurements and the experience gained in developing a set of measurement techniques and profiling tools to accurately assess the power consumption for scientific workloads.
Sentiment Analysis based on User Tag for Traditional Chinese Medicine in Weibo
Venue: arXiv cs.CL 2014
Year: 2014

With the acceptance of Western culture and science, Traditional Chinese Medicine (TCM) has become a controversial issue in China. So, it's important to study the public's sentiment and opinion on TCM. The rapid development of online social network, such as twitter, make it convenient and efficient to sample hundreds of millions of people for the aforementioned sentiment study. To the best of our knowledge, the present work is the first attempt that applies sentiment analysis to the domain of TCM on Sina Weibo (a twitter-like microblogging service in China). In our work, firstly we collect tweets topic about TCM from Sina Weibo, and label the tweets as supporting TCM and opposing TCM automatically based on user tag. Then, a support vector machine classifier has been built to predict the sentiment of TCM tweets without labels. Finally, we present a method to adjust the classifier result. The performance of F-measure attained with our method is 97%.
Cascading Failures in Finite-Size Random Geometric Networks
Venue: arXiv cs.SI 2014
Year: 2014

The problem of cascading failures in cyber-physical systems is drawing much attention in lieu of different network models for a diverse range of applications. While many analytic results have been reported for the case of large networks, very few of them are readily applicable to finite-size networks. This paper studies cascading failures in finite-size geometric networks where the number of nodes is on the order of tens or hundreds as in many real-life networks. First, the impact of the tolerance parameter on network resiliency is investigated. We quantify the network reaction to initial disturbances of different sizes by measuring the damage imposed on the network. Lower and upper bounds on the number of failures are derived to characterize such damages. Such finite-size analysis reveals the decisiveness and criticality of taking action within the first few stages of failure propagation in preventing a cascade. By studying the trend of the bounds as the number of nodes increases, we observe a phase transition phenomenon in terms of the tolerance parameter. The critical value of the tolerance parameter, known as the threshold, is further derived. The findings of this paper, in particular, shed light on how to choose the tolerance parameter appropriately such that a cascade of failures could be avoided.
Optimizing Multi-Cell Massive MIMO for Spectral Efficiency: How Many Users Should Be Scheduled?
Venue: arXiv cs.IT 2014
Year: 2014

Massive MIMO is a promising technique to increase the spectral efficiency of cellular networks, by deploying antenna arrays with hundreds or thousands of active elements at the base stations and performing coherent beamforming. A common rule-of-thumb is that these systems should have an order of magnitude more antennas, $N$, than scheduled users, $K$, because the users' channels are then likely to be quasi-orthogonal. However, it has not been proved that this rule-of-thumb actually maximizes the spectral efficiency. In this paper, we analyze how the optimal number of scheduled users, $K^\star$, depends on $N$ and other system parameters. The value of $K^\star$ in the large-$N$ regime is derived in closed form, while simulations are used to show what happens at finite $N$, in different interference scenarios, and for different beamforming.
Randomized Triangle Algorithms for Convex Hull Membership
Venue: arXiv cs.CG 2014
Year: 2014

We present randomized versions of the {\it triangle algorithm} introduced in \cite{kal14}. The triangle algorithm tests membership of a distinguished point $p \in \mathbb{R} ^m$ in the convex hull of a given set $S$ of $n$ points in $\mathbb{R}^m$. Given any {\it iterate} $p' \in conv(S)$, it searches for a {\it pivot}, a point $v \in S$ so that $d(p',v) \geq d(p,v)$. It replaces $p'$ with the point on the line segment $p'v$ closest to $p$ and repeats this process. If a pivot does not exist, $p'$ certifies that $p \not \in conv(S)$. Here we propose two random variations of the triangle algorithm that allow relaxed steps so as to take more effective steps possible in subsequent iterations. One is inspired by the {\it chaos game} known to result in the Sierpinski triangle. The incentive is that randomized iterates together with a property of Sierpinski triangle would result in effective pivots. Bounds on their expected complexity coincides with those of the deterministic version derived in \cite{kal14}.
A stochastic behavior analysis of stochastic restricted-gradient descent algorithm in reproducing kernel Hilbert spaces
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents a stochastic behavior analysis of a kernel-based stochastic restricted-gradient descent method. The restricted gradient gives a steepest ascent direction within the so-called dictionary subspace. The analysis provides the transient and steady state performance in the mean squared error criterion. It also includes stability conditions in the mean and mean-square sense. The present study is based on the analysis of the kernel normalized least mean square (KNLMS) algorithm initially proposed by Chen et al. Simulation results validate the analysis.
Greedy Sparsity-Promoting Algorithms for Distributed Learning
Venue: arXiv cs.IT 2014
Year: 2014

This paper focuses on the development of novel greedy techniques for distributed learning under sparsity constraints. Greedy techniques have widely been used in centralized systems due to their low computational requirements and at the same time their relatively good performance in estimating sparse parameter vectors/signals. The paper reports two new algorithms in the context of sparsity--aware learning. In both cases, the goal is first to identify the support set of the unknown signal and then to estimate the non--zero values restricted to the active support set. First, an iterative greedy multi--step procedure is developed, based on a neighborhood cooperation strategy, using batch processing on the observed data. Next, an extension of the algorithm to the online setting, based on the diffusion LMS rationale for adaptivity, is derived. Theoretical analysis of the algorithms is provided, where it is shown that the batch algorithm converges to the unknown vector if a Restricted Isometry Property (RIP) holds. Moreover, the online version converges in the mean to the solution vector under some general assumptions. Finally, the proposed schemes are tested against recently developed sparsity--promoting algorithms and their enhanced performance is verified via simulation examples.
Joint Multi-Cell Resource Allocation Using Pure Binary-Integer Programming for LTE Uplink
Venue: arXiv cs.IT 2014
Year: 2014

Due to high system capacity requirement, 3GPP Long Term Evolution (LTE) is likely to adopt frequency reuse factor 1 at the cost of suffering severe inter-cell interference (ICI). One of combating ICI strategies is network cooperation of resource allocation (RA). For LTE uplink RA, requiring all the subcarriers to be allocated adjacently complicates the RA problem greatly. This paper investigates the joint multi-cell RA problem for LTE uplink. We model the uplink RA and ICI mitigation problem using pure binary-integer programming (BIP), with integrative consideration of all users' channel state information (CSI). The advantage of the pure BIP model is that it can be solved by branch-and-bound search (BBS) algorithm or other BIP solving algorithms, rather than resorting to exhaustive search. The system-level simulation results show that it yields 14.83% and 22.13% gains over single-cell optimal RA in average spectrum efficiency and 5th percentile of user throughput, respectively.
Scene Image is Non-Mutually Exclusive - A Fuzzy Qualitative Scene Understanding
Venue: arXiv cs.CV 2014
Year: 2014

Ambiguity or uncertainty is a pervasive element of many real world decision making processes. Variation in decisions is a norm in this situation when the same problem is posed to different subjects. Psychological and metaphysical research had proven that decision making by human is subjective. It is influenced by many factors such as experience, age, background, etc. Scene understanding is one of the computer vision problems that fall into this category. Conventional methods relax this problem by assuming scene images are mutually exclusive; and therefore, focus on developing different approaches to perform the binary classification tasks. In this paper, we show that scene images are non-mutually exclusive, and propose the Fuzzy Qualitative Rank Classifier (FQRC) to tackle the aforementioned problems. The proposed FQRC provides a ranking interpretation instead of binary decision. Evaluations in term of qualitative and quantitative using large numbers and challenging public scene datasets have shown the effectiveness of our proposed method in modeling the non-mutually exclusive scene images.
Performance Analysis of Asynchronous Multicarrier Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper develops a novel analytical framework for asynchronous wireless networks deploying multicarrier transmission. Nodes in the network have different notions of timing, so from the viewpoint of a typical receiver, the received signals from different transmitters are asynchronous, leading to a loss of orthogonality between subcarriers. We first develop a detailed link-level analysis based on OFDM, based on which we propose a tractable system-level signal-to-interference-plus-noise ratio (SINR) model for asynchronous OFDM networks. The proposed model is used to analytically characterize several important statistics in asynchronous networks with spatially distributed transmitters, including (i) the number of decodable transmitters, (ii) the decoding probability of the nearest transmitter, and (iii) the system throughput. The system-level loss from lack of synchronization is quantified, and to mitigate the loss, we compare and discuss four possible solutions including extended cyclic prefix, advanced receiver timing, dynamic receiver timing positioning, and semi-static receiver timing positioning with multiple timing hypotheses. The model and results are general, and apply to ad hoc networks, cellular systems, and neighbor discovery in device-to-device (D2D) networks.
Presence-absence reasoning for evolutionary phenotypes
Venue: arXiv cs.AI 2014
Year: 2014

Nearly invariably, phenotypes are reported in the scientific literature in meticulous detail, utilizing the full expressivity of natural language. Often it is particularly these detailed observations (facts) that are of interest, and thus specific to the research questions that motivated observing and reporting them. However, research aiming to synthesize or integrate phenotype data across many studies or even fields is often faced with the need to abstract from detailed observations so as to construct phenotypic concepts that are common across many datasets rather than specific to a few. Yet, observations or facts that would fall under such abstracted concepts are typically not directly asserted by the original authors, usually because they are "obvious" according to common domain knowledge, and thus asserting them would be deemed redundant by anyone with sufficient domain knowledge. For example, a phenotype describing the length of a manual digit for an organism implicitly means that the organism must have had a hand, and thus a forelimb; the presence or absence of a forelimb may have supporting data across a far wider range of taxa than the length of a particular manual digit. Here we describe how within the Phenoscape project we use a pipeline of OWL axiom generation and reasoning steps to infer taxon-specific presence/absence of anatomical entities from anatomical phenotypes. Although presence/absence is all but one, and a seemingly simple way to abstract phenotypes across data sources, it can nonetheless be powerful for linking genotype to phenotype, and it is particularly relevant for constructing synthetic morphological supermatrices for comparative analysis; in fact presence/absence is one of the prevailing character observation types in published character matrices.
A new upper bound for Achlioptas processes
Venue: arXiv cs.DM 2014
Year: 2014

We consider here on-line algorithms for Achlioptas processes. Given a initially empty graph $G$ on $n$ vertices, a random process that at each step selects independently and uniformly at random two edges from the set of non-edges is launched. We must choose one of the two edges and add it to the graph while discarding the other. The goal is to avoid the appearance of a connected component spanning $Ω(n)$ vertices (called a giant component) for as many steps as possible. Bohman and Frieze proved in 2001 that on-line Achlioptas processes cannot postpone the appearance of the giant for more that roughly $n$ steps whp. This upper bound got even lower in 2003 when the two above mentioned authors and Wormald proved that each on-line Achlioptas process creates a giant before step $0.964446n$ whp. The purpose of this work is to determine a new upper bound. By using essentially the same methods used by Bohman, Frieze and Wormald in 2003 and some results of Spencer and Wormald on size algorithms we prove here that Achlioptas processes cannot postpone the appearance of the giant for more than $0.9455n$ steps whp.
Detection of Salient Regions in Crowded Scenes
Venue: arXiv cs.CV 2014
Year: 2014

The increasing number of cameras and a handful of human operators to monitor the video inputs from hundreds of cameras leave the system ill equipped to fulfil the task of detecting anomalies. Thus, there is a dire need to automatically detect regions that require immediate attention for a more effective and proactive surveillance. We propose a framework that utilises the temporal variations in the flow field of a crowd scene to automatically detect salient regions, while eliminating the need to have prior knowledge of the scene or training. We deem the flow fields to be a dynamic system and adopt the stability theory of dynamical systems, to determine the motion dynamics within a given area. In the context of this work, salient regions refer to areas with high motion dynamics, where points in a particular region are unstable. Experimental results on public, crowd scenes have shown the effectiveness of the proposed method in detecting salient regions which correspond to unstable flow, occlusions, bottlenecks, entries and exits.
XSS Peeker: A Systematic Analysis of Cross-site Scripting Vulnerability Scanners
Venue: arXiv cs.CR 2014
Year: 2014

Since the first publication of the "OWASP Top 10" (2004), cross-site scripting (XSS) vulnerabilities have always been among the top 5 web application security bugs. Black-box vulnerability scanners are widely used in the industry to reproduce (XSS) attacks automatically. In spite of the technical sophistication and advancement, previous work showed that black-box scanners miss a non-negligible portion of vulnerabilities, and report non-existing, non-exploitable or uninteresting vulnerabilities. Unfortunately, these results hold true even for XSS vulnerabilities, which are relatively simple to trigger if compared, for instance, to logic flaws. Black-box scanners have not been studied in depth on this vertical: knowing precisely how scanners try to detect XSS can provide useful insights to understand their limitations, to design better detection methods. In this paper, we present and discuss the results of a detailed and systematic study on 6 black-box web scanners (both proprietary and open source) that we conducted in coordination with the respective vendors. To this end, we developed an automated tool to (1) extract the payloads used by each scanner, (2) distill the "templates" that have originated each payload, (3) evaluate them according to quality indicators, and (4) perform a cross-scanner analysis. Unlike previous work, our testbed application, which contains a large set of XSS vulnerabilities, including DOM XSS, was gradually retrofitted to accomodate for the payloads that triggered no vulnerabilities. Our analysis reveals a highly fragmented scenario. Scanners exhibit a wide variety of distinct payloads, a non-uniform approach to fuzzing and mutating the payloads, and a very diverse detection effectiveness.
Online Network Design Algorithms via Hierarchical Decompositions
Venue: arXiv cs.DS 2014
Year: 2014

We develop a new approach for online network design and obtain improved competitive ratios for several problems. Our approach gives natural deterministic algorithms and simple analyses. At the heart of our work is a novel application of embeddings into hierarchically well-separated trees (HSTs) to the analysis of online network design algorithms --- we charge the cost of the algorithm to the cost of the optimal solution on any HST embedding of the terminals. This analysis technique is widely applicable to many problems and gives a unified framework for online network design. In a sense, our work brings together two of the main approaches to online network design. The first uses greedy-like algorithms and analyzes them using dual-fitting. The second uses tree embeddings and results in randomized $O(\log n)$-competitive algorithms, where $n$ is the total number of vertices in the graph. Our approach uses deterministic greedy-like algorithms but analyzes them via HST embeddings of the terminals. Our proofs are simpler as we do not need to carefully construct dual solutions and we get $O(\log k)$ competitive ratios, where $k$ is the number of terminals. In this paper, we apply our approach to obtain deterministic $O(\log k)$-competitive online algorithms for the following problems. - Steiner network with edge duplication. Previously, only a randomized $O(\log n)$-competitive algorithm was known. - Rent-or-buy. Previously, only deterministic $O(\log^2 k)$-competitive and randomized $O(\log k)$-competitive algorithms by Awerbuch, Azar and Bartal (2004) were known. - Connected facility location. Previously, only a randomized $O(\log^2 k)$-competitive algorithm by San Felice, Williamson and Lee (2014) was known. - Prize-collecting Steiner forest. We match the competitive ratio first achieved by Qian and Williamson (2011) and give a simpler analysis.
Anatomy of a Crash
Venue: arXiv cs.SY 2014
Year: 2014

Transportation networks constitute a critical infrastructure enabling the transfers of passengers and goods, with a significant impact on the economy at different scales. Transportation modes, whether air, road or rail, are coupled and interdependent. The frequent occurrence of perturbations on one or several modes disrupts passengers' entire journeys, directly and through ripple effects. The present paper provides a case report of the Asiana Crash in San Francisco International Airport on July 6th 2013 and its repercussions on the multimodal transportation network. It studies the resulting propagation of disturbances on the transportation infrastructure in the United States. The perturbation takes different forms and varies in scale and time frame : cancellations and delays snowball in the airspace, highway traffic near the airport is impacted by congestion in previously never congested locations, and transit passenger demand exhibit unusual traffic peaks in between airports in the Bay Area. This paper, through a case study, aims at stressing the importance of further data-driven research on interdependent infrastructure networks for increased resilience. The end goal is to form the basis for optimization models behind providing more reliable passenger door-to-door journeys.
Can SDN Mitigate Disasters?
Venue: arXiv cs.NI 2014
Year: 2014

Datacenter networks and services are at risk in the face of disasters. Existing fault-tolerant storage services cannot even achieve a nil recovery point objective (RPO) as client-generated data may get lost before the termination of their migration across geo-replicated datacenters. SDN has proved instrumental in exploiting application-level information to optimise the routing of information. In this paper, we propose Software Defined Edge (SDE) or the implementation of SDN at the network edge to achieve nil RPO. We illustrate our proposal with a fault-tolerant key-value store that experimentally recovers from disaster within 30s. Although SDE is inherently fault-tolerant and scalable, its deployment raises new challenges on the partnership between ISPs and CDN providers. We conclude that failure detection information at the SDN-level can effectively benefit applications to recover from disaster.
Digital Investigation of Security Attacks on Cardiac Implantable Medical Devices
Venue: arXiv cs.CR 2014
Year: 2014

A Cardiac Implantable Medical device (IMD) is a device, which is surgically implanted into a patient's body, and wirelessly configured using an external programmer by prescribing physicians and doctors. A set of lethal attacks targeting these devices can be conducted due to the use of vulnerable wireless communication and security protocols, and the lack of security protection mechanisms deployed on IMDs. In this paper, we propose a system for postmortem analysis of lethal attack scenarios targeting cardiac IMDs. Such a system reconciles in the same framework conclusions derived by technical investigators and deductions generated by pathologists. An inference system integrating a library of medical rules is used to automatically infer potential medical scenarios that could have led to the death of a patient. A Model Checking based formal technique allowing the reconstruction of potential technical attack scenarios on the IMD, starting from the collected evidence, is also proposed. A correlation between the results obtained by the two techniques allows to prove whether a potential attack scenario is the source of the patient's death.