OpenRaiser/Intern-Atlas huggingface dataset:
Outward Influence and Cascade Size Estimation in Billion-scale Networks
Venue: arXiv cs.DS 2017
Year: 2017

Estimating cascade size and nodes' influence is a fundamental task in social, technological, and biological networks. Yet this task is extremely challenging due to the sheer size and the structural heterogeneity of networks. We investigate a new influence measure, termed outward influence (OI), defined as the (expected) number of nodes that a subset of nodes $S$ will activate, excluding the nodes in S. Thus, OI equals, the de facto standard measure, influence spread of S minus |S|. OI is not only more informative for nodes with small influence, but also, critical in designing new effective sampling and statistical estimation methods. Based on OI, we propose SIEA/SOIEA, novel methods to estimate influence spread/outward influence at scale and with rigorous theoretical guarantees. The proposed methods are built on two novel components 1) IICP an important sampling method for outward influence, and 2) RSA, a robust mean estimation method that minimize the number of samples through analyzing variance and range of random variables. Compared to the state-of-the art for influence estimation, SIEA is $Ω(\log^4 n)$ times faster in theory and up to several orders of magnitude faster in practice. For the first time, influence of nodes in the networks of billions of edges can be estimated with high accuracy within a few minutes. Our comprehensive experiments on real-world networks also give evidence against the popular practice of using a fixed number, e.g. 10K or 20K, of samples to compute the "ground truth" for influence spread.
Uncovering Architectural Design Decisions
Venue: arXiv cs.SE 2017
Year: 2017

Over the past three decades, considerable effort has been devoted to the study of software architecture. A major portion of this effort has focused on the originally proposed view of four "C"s---components, connectors, configurations, and constraints---that are the building blocks of a system's architecture. Despite being simple and appealing, this view has proven to be incomplete and has required further elaboration. To that end, researchers have more recently tried to approach architectures from another important perspective---that of design decisions that yield a system's architecture. These more recent efforts have lacked a precise understanding of several key questions, however: (1) What is an architectural design decision (definition)? (2) How can architectural design decisions be found in existing systems (identification)? (3) What system decisions are and are not architectural (classification)? (4) How are architectural design decisions manifested in the code (reification)? (5) How can important architectural decisions be preserved and/or changed as desired (evolution)? This paper presents a technique targeted at answering these questions by analyzing information that is readily available about software systems. We applied our technique on over 100 different versions of two widely adopted open- source systems, and found that it can accurately uncover the architectural design decisions embodied in the systems.
Least square ellipsoid fitting using iterative orthogonal transformations
Venue: arXiv cs.CV 2017
Year: 2017

We describe a generalised method for ellipsoid fitting against a minimum set of data points. The proposed method is numerically stable and applies to a wide range of ellipsoidal shapes, including highly elongated and arbitrarily oriented ellipsoids. This new method also provides for the retrieval of rotational angle and length of semi-axes of the fitted ellipsoids accurately. We demonstrate the efficacy of this algorithm on simulated data sets and also indicate its potential use in gravitational wave data analysis.
Morpheo: Traceable Machine Learning on Hidden data
Venue: arXiv cs.AI 2017
Year: 2017

Morpheo is a transparent and secure machine learning platform collecting and analysing large datasets. It aims at building state-of-the art prediction models in various fields where data are sensitive. Indeed, it offers strong privacy of data and algorithm, by preventing anyone to read the data, apart from the owner and the chosen algorithms. Computations in Morpheo are orchestrated by a blockchain infrastructure, thus offering total traceability of operations. Morpheo aims at building an attractive economic ecosystem around data prediction by channelling crypto-money from prediction requests to useful data and algorithms providers. Morpheo is designed to handle multiple data sources in a transfer learning approach in order to mutualize knowledge acquired from large datasets for applications with smaller but similar datasets.
Google's Cloud Vision API Is Not Robust To Noise
Venue: arXiv cs.CV 2017
Year: 2017

Google has recently introduced the Cloud Vision API for image analysis. According to the demonstration website, the API "quickly classifies images into thousands of categories, detects individual objects and faces within images, and finds and reads printed words contained within images." It can be also used to "detect different types of inappropriate content from adult to violent content." In this paper, we evaluate the robustness of Google Cloud Vision API to input perturbation. In particular, we show that by adding sufficient noise to the image, the API generates completely different outputs for the noisy image, while a human observer would perceive its original content. We show that the attack is consistently successful, by performing extensive experiments on different image types, including natural images, images containing faces and images with texts. For instance, using images from ImageNet dataset, we found that adding an average of 14.25% impulse noise is enough to deceive the API. Our findings indicate the vulnerability of the API in adversarial environments. For example, an adversary can bypass an image filtering system by adding noise to inappropriate images. We then show that when a noise filter is applied on input images, the API generates mostly the same outputs for restored images as for original images. This observation suggests that cloud vision API can readily benefit from noise filtering, without the need for updating image analysis algorithms.
Making data center computations fast, but not so furious
Venue: arXiv cs.DC 2017
Year: 2017

We propose an aggressive computational sprinting variant for data center environments. While most of previous work on computational sprinting focuses on maximizing the sprinting process while ensuring non-faulty conditions, we take advantage of the existing replication in data centers to push the system beyond its safety limits. In this paper we outline this vision, we survey existing techniques for achieving it, and we present some design ideas for future work in this area.
The Causality/Repair Connection in Databases: Causality-Programs
Venue: arXiv cs.DB 2017
Year: 2017

In this work, answer-set programs that specify repairs of databases are used as a basis for solving computational and reasoning problems about causes for query answers from databases.
On Predicting Geolocation of Tweets using Convolutional Neural Networks
Venue: arXiv cs.SI 2017
Year: 2017

In many Twitter studies, it is important to know where a tweet came from in order to use the tweet content to study regional user behavior. However, researchers using Twitter to understand user behavior often lack sufficient geo-tagged data. Given the huge volume of Twitter data there is a need for accurate automated geolocating solutions. Herein, we present a new method to predict a Twitter user's location based on the information in a single tweet. We integrate text and user profile meta-data into a single model using a convolutional neural network. Our experiments demonstrate that our neural model substantially outperforms baseline methods, achieving 52.8% accuracy and 92.1% accuracy on city-level and country-level prediction respectively.
Scalable Global Grid catalogue for LHC Run3 and beyond
Venue: arXiv cs.DC 2017
Year: 2017

The AliEn (ALICE Environment) file catalogue is a global unique namespace providing mapping between a UNIX-like logical name structure and the corresponding physical files distributed over 80 storage elements worldwide. Powerful search tools and hierarchical metadata information are integral parts of the system and are used by the Grid jobs as well as local users to store and access all files on the Grid storage elements. The catalogue has been in production since 2005 and over the past 11 years has grown to more than 2 billion logical file names. The backend is a set of distributed relational databases, ensuring smooth growth and fast access. Due to the anticipated fast future growth, we are looking for ways to enhance the performance and scalability by simplifying the catalogue schema while keeping the functionality intact. We investigated different backend solutions, such as distributed key value stores, as replacement for the relational database. This contribution covers the architectural changes in the system, together with the technology evaluation, benchmark results and conclusions.
The Robot Routing Problem for Collecting Aggregate Stochastic Rewards
Venue: arXiv cs.SY 2017
Year: 2017

We propose a new model for formalizing reward collection problems on graphs with dynamically generated rewards which may appear and disappear based on a stochastic model. The *robot routing problem* is modeled as a graph whose nodes are stochastic processes generating potential rewards over discrete time. The rewards are generated according to the stochastic process, but at each step, an existing reward disappears with a given probability. The edges in the graph encode the (unit-distance) paths between the rewards' locations. On visiting a node, the robot collects the accumulated reward at the node at that time, but traveling between the nodes takes time. The optimization question asks to compute an optimal (or epsilon-optimal) path that maximizes the expected collected rewards. We consider the finite and infinite-horizon robot routing problems. For finite-horizon, the goal is to maximize the total expected reward, while for infinite horizon we consider limit-average objectives. We study the computational and strategy complexity of these problems, establish NP-lower bounds and show that optimal strategies require memory in general. We also provide an algorithm for computing epsilon-optimal infinite paths for arbitrary epsilon > 0.
Benchmarking OpenCL, OpenACC, OpenMP, and CUDA: programming productivity, performance, and energy consumption
Venue: arXiv cs.DC 2017
Year: 2017

Many modern parallel computing systems are heterogeneous at their node level. Such nodes may comprise general purpose CPUs and accelerators (such as, GPU, or Intel Xeon Phi) that provide high performance with suitable energy-consumption characteristics. However, exploiting the available performance of heterogeneous architectures may be challenging. There are various parallel programming frameworks (such as, OpenMP, OpenCL, OpenACC, CUDA) and selecting the one that is suitable for a target context is not straightforward. In this paper, we study empirically the characteristics of OpenMP, OpenACC, OpenCL, and CUDA with respect to programming productivity, performance, and energy. To evaluate the programming productivity we use our homegrown tool CodeStat, which enables us to determine the percentage of code lines that was required to parallelize the code using a specific framework. We use our tool x-MeterPU to evaluate the energy consumption and the performance. Experiments are conducted using the industry-standard SPEC benchmark suite and the Rodinia benchmark suite for accelerated computing on heterogeneous systems that combine Intel Xeon E5 Processors with a GPU accelerator or an Intel Xeon Phi co-processor.
EPTL - A temporal logic for weakly consistent systems
Venue: arXiv cs.LO 2017
Year: 2017

The high availability and scalability of weakly-consistent systems attracts system designers. Yet, writing correct application code for this type of systems is difficult; even how to specify the intended behavior of such systems is still an open question. There has not been established any standard method to specify the intended dynamic behavior of a weakly consistent system. There exist specifications of various consistency models for distributed and concurrent systems; and the semantics of replicated datatypes like CRDTs have been specified in axiomatic and operational models based on visibility relations. In this paper, we present a temporal logic, EPTL, that is tailored to specify properties of weakly consistent systems. In contrast to LTL and CTL, EPTL takes into account that operations of weakly consistent systems are in many cases not serializable and have to be treated respectively to capture the behavior. We embed our temporal logic in Isabelle/HOL and can thereby leverage strong semi-automatic proving capabilities.
Feedback-Capacity of Degraded Gaussian Vector BC using Directed Information and Concave Envelopes
Venue: arXiv cs.IT 2017
Year: 2017

It is known that the capacity region of a two user physically degraded discrete memoryless (DM) broadcast channel (BC) is not enlarged by feedback. An identical result holds true for a physically degraded Gaussian BC, established later using a variant of the Entropy Power Inequality (EPI). In this paper, we extend the latter result to a physically degraded Gaussian Vector BC (PD-GVBC). However, the extension is not EPI based, but employs a recent result on the factorization of concave envelopes. While the existing concave envelope factorization results do not hold in the presence of feedback, we show that factorizing the corresponding directed information quantities suffice to attain the feedback capacity region of a PD-GVBC. Our work demonstrates that factorizing concave envelopes of directed information can handle situations involving feedback. We further show that the capacity region of a discrete memoryless reversely physically degraded BC is not enlarged by feedback.
Building Regular Registers with Rational Malicious Servers and Anonymous Clients -- Extended Version
Venue: arXiv cs.DC 2017
Year: 2017

The paper addresses the problem of emulating a regular register in a synchronous distributed system where clients invoking ${\sf read}()$ and ${\sf write}()$ operations are anonymous while server processes maintaining the state of the register may be compromised by rational adversaries (i.e., a server might behave as \emph{rational malicious Byzantine} process). We first model our problem as a Bayesian game between a client and a rational malicious server where the equilibrium depends on the decisions of the malicious server (behave correctly and not be detected by clients vs returning a wrong register value to clients with the risk of being detected and then excluded by the computation). We prove such equilibrium exists and finally we design a protocol implementing the regular register that forces the rational malicious server to behave correctly.
Discovering Evolutionary Stepping Stones through Behavior Domination
Venue: arXiv cs.NE 2017
Year: 2017

Behavior domination is proposed as a tool for understanding and harnessing the power of evolutionary systems to discover and exploit useful stepping stones. Novelty search has shown promise in overcoming deception by collecting diverse stepping stones, and several algorithms have been proposed that combine novelty with a more traditional fitness measure to refocus search and help novelty search scale to more complex domains. However, combinations of novelty and fitness do not necessarily preserve the stepping stone discovery that novelty search affords. In several existing methods, competition between solutions can lead to an unintended loss of diversity. Behavior domination defines a class of algorithms that avoid this problem, while inheriting theoretical guarantees from multiobjective optimization. Several existing algorithms are shown to be in this class, and a new algorithm is introduced based on fast non-dominated sorting. Experimental results show that this algorithm outperforms existing approaches in domains that contain useful stepping stones, and its advantage is sustained with scale. The conclusion is that behavior domination can help illuminate the complex dynamics of behavior-driven search, and can thus lead to the design of more scalable and robust algorithms.
Using Contexts and Constraints for Improved Geotagging of Human Trafficking Webpages
Venue: arXiv cs.AI 2017
Year: 2017

Extracting geographical tags from webpages is a well-motivated application in many domains. In illicit domains with unusual language models, like human trafficking, extracting geotags with both high precision and recall is a challenging problem. In this paper, we describe a geotag extraction framework in which context, constraints and the openly available Geonames knowledge base work in tandem in an Integer Linear Programming (ILP) model to achieve good performance. In preliminary empirical investigations, the framework improves precision by 28.57% and F-measure by 36.9% on a difficult human trafficking geotagging task compared to a machine learning-based baseline. The method is already being integrated into an existing knowledge base construction system widely used by US law enforcement agencies to combat human trafficking.
Proactive Eavesdropping in Relaying Systems
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the performance of a legitimate surveillance system, where a legitimate monitor aims to eavesdrop on a dubious decode-and-forward relaying communication link. In order to maximize the effective eavesdropping rate, two strategies are proposed, where the legitimate monitor adaptively acts as an eavesdropper, a jammer or a helper. In addition, the corresponding optimal jamming beamformer and jamming power are presented. Numerical results demonstrate that the proposed strategies attain better performance compared with intuitive benchmark schemes. Moreover, it is revealed that the position of the legitimate monitor plays an important role on the eavesdropping performance for the two strategies.
TrustShadow: Secure Execution of Unmodified Applications with ARM TrustZone
Venue: arXiv cs.CR 2017
Year: 2017

The rapid evolution of Internet-of-Things (IoT) technologies has led to an emerging need to make it smarter. A variety of applications now run simultaneously on an ARM-based processor. For example, devices on the edge of the Internet are provided with higher horsepower to be entrusted with storing, processing and analyzing data collected from IoT devices. This significantly improves efficiency and reduces the amount of data that needs to be transported to the cloud for data processing, analysis and storage. However, commodity OSes are prone to compromise. Once they are exploited, attackers can access the data on these devices. Since the data stored and processed on the devices can be sensitive, left untackled, this is particularly disconcerting. In this paper, we propose a new system, TrustShadow that shields legacy applications from untrusted OSes. TrustShadow takes advantage of ARM TrustZone technology and partitions resources into the secure and normal worlds. In the secure world, TrustShadow constructs a trusted execution environment for security-critical applications. This trusted environment is maintained by a lightweight runtime system that coordinates the communication between applications and the ordinary OS running in the normal world. The runtime system does not provide system services itself. Rather, it forwards requests for system services to the ordinary OS, and verifies the correctness of the responses. To demonstrate the efficiency of this design, we prototyped TrustShadow on a real chip board with ARM TrustZone support, and evaluated its performance using both microbenchmarks and real-world applications. We showed TrustShadow introduces only negligible overhead to real-world applications.
A Novel Receiver Design with Joint Coherent and Non-Coherent Processing
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a novel splitting receiver, which involves joint processing of coherently and non-coherently received signals. Using a passive RF power splitter, the received signal at each receiver antenna is split into two streams which are then processed by a conventional coherent detection (CD) circuit and a power-detection (PD) circuit, respectively. The streams of the signals from all the receiver antennas are then jointly used for information detection. We show that the splitting receiver creates a three-dimensional received signal space, due to the joint coherent and non-coherent processing. We analyze the achievable rate of a splitting receiver, which shows that the splitting receiver provides a rate gain of $3/2$ compared to either the conventional (CD-based) coherent receiver or the PD-based non-coherent receiver in the high SNR regime. We also analyze the symbol error rate (SER) for practical modulation schemes, which shows that the splitting receiver achieves asymptotic SER reduction by a factor of at least $\sqrt{M}-1$ for $M$-QAM compared to either the conventional (CD-based) coherent receiver or the PD-based non-coherent receiver.
m-Bonsai: a Practical Compact Dynamic Trie
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with $n$ nodes with an alphabet of size $σ$, the information-theoretic lower bound is $n \log σ+ O(n)$ bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw., Pract. Exper. 23(3), 1993, p. 277-291). Its disadvantages include the user having to specify an upper bound $M$ on the trie size in advance (which cannot be changed easily after initalization), a space usage of $M \log σ+ O(M \log \log M)$ (which is asymptotically non-optimal for smaller $σ$ or if $n \ll M$) and a lack of support for deletions. It supports traversal and update operations in $O(1/ε)$ expected time (based on assumptions about the behaviour of hash functions), where $ε= (M-n)/M$ and has excellent speed performance in practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining a trie that uses $(1+β) n (\log σ+ O(1))$ bits in expectation, and supports traversal and update operations in $O(1/β)$ expected time and $O(1/β^2)$ amortized expected time, for any user-specified parameter $β> 0$ (again based on assumptions about the behaviour of hash functions). We give an implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.
Automatic Segmentation of the Left Ventricle in Cardiac CT Angiography Using Convolutional Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

Accurate delineation of the left ventricle (LV) is an important step in evaluation of cardiac function. In this paper, we present an automatic method for segmentation of the LV in cardiac CT angiography (CCTA) scans. Segmentation is performed in two stages. First, a bounding box around the LV is detected using a combination of three convolutional neural networks (CNNs). Subsequently, to obtain the segmentation of the LV, voxel classification is performed within the defined bounding box using a CNN. The study included CCTA scans of sixty patients, fifty scans were used to train the CNNs for the LV localization, five scans were used to train LV segmentation and the remaining five scans were used for testing the method. Automatic segmentation resulted in the average Dice coefficient of 0.85 and mean absolute surface distance of 1.1 mm. The results demonstrate that automatic segmentation of the LV in CCTA scans using voxel classification with convolutional neural networks is feasible.