OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Neural Network Approach to Abstractive Multi-Document Summarization
Venue: arXiv cs.CL 2018
Year: 2018

Till now, neural abstractive summarization methods have achieved great success for single document summarization (SDS). However, due to the lack of large scale multi-document summaries, such methods can be hardly applied to multi-document summarization (MDS). In this paper, we investigate neural abstractive methods for MDS by adapting a state-of-the-art neural abstractive summarization model for SDS. We propose an approach to extend the neural abstractive model trained on large scale SDS data to the MDS task. Our approach only makes use of a small number of multi-document summaries for fine tuning. Experimental results on two benchmark DUC datasets demonstrate that our approach can outperform a variety of baseline neural models.
Propagation of content similarity through a collaborative network for live show recommendation
Venue: arXiv cs.SI 2018
Year: 2018

We present a network-based recommender system for live shows (concerts, theater, circus, etc) that finds a set of people probably interested in a given, new show. We combine collaborative and content-based filtering to take benefit of past activity of users and of the features of the new show. Indeed, as this show is new we cannot rely on collaborative filtering only. To solve this cold-start problem, we perform network alignment and insert the new show in a way consistent with collaborative filtering. We refine the obtained similarities using spreading in the network. We illustrate the performances of our system on a large scale real-world dataset.
Guarded Computational Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

Nakano's later modality can be used to specify and define recursive functions which are causal or synchronous; in concert with a notion of clock variable, it is possible to also capture the broader class of productive (co)programs. Until now, it has been difficult to combine these constructs with dependent types in a way that preserves the operational meaning of type theory and admits a hierarchy of universes. We present an operational account of guarded dependent type theory with clocks called Guarded Computational Type Theory, featuring a novel clock intersection connective that enjoys the clock irrelevance principle, as well as a predicative hierarchy of universes which does not require any indexing in clock contexts. Guarded Computational Type Theory is simultaneously a programming language with a rich specification logic, as well as a computational metalanguage that can be used to develop semantics of other languages and logics.
Floods impact dynamics quantified from big data sources
Venue: arXiv cs.CY 2018
Year: 2018

Natural disasters affect hundreds of millions of people worldwide every year. Early warning, humanitarian response and recovery mechanisms can be improved by using big data sources. Measuring the different dimensions of the impact of natural disasters is critical for designing policies and building up resilience. Detailed quantification of the movement and behaviours of affected populations requires the use of high granularity data that entails privacy risks. Leveraging all this data is costly and has to be done ensuring privacy and security of large amounts of data. Proxies based on social media and data aggregates would streamline this process by providing evidences and narrowing requirements. We propose a framework that integrates environmental data, social media, remote sensing, digital topography and mobile phone data to understand different types of floods and how data can provide insights useful for managing humanitarian action and recovery plans. Thus, data is dynamically requested upon data-based indicators forming a multi-granularity and multi-access data pipeline. We present a composed study of three cases to show potential variability in the natures of floodings,as well as the impact and applicability of data sources. Critical heterogeneity of the available data in the different cases has to be addressed in order to design systematic approaches based on data. The proposed framework establishes the foundation to relate the physical and socio-economical impacts of floods.
Seer: Leveraging Big Data to Navigate the Increasing Complexity of Cloud Debugging
Venue: arXiv cs.DC 2018
Year: 2018

Performance unpredictability in cloud services leads to poor user experience, degraded availability, and has revenue ramifications. Detecting performance degradation a posteriori helps the system take corrective action, but does not avoid the QoS violations. Detecting QoS violations after the fact is even more detrimental when a service consists of hundreds of thousands of loosely-coupled microservices, since performance hiccups can quickly propagate across the dependency graph of microservices. In this work we focus on anticipating QoS violations in cloud settings to mitigate performance unpredictability to begin with. We propose Seer, a cloud runtime that leverages the massive amount of tracing data cloud systems collect over time and a set of practical learning techniques to signal upcoming QoS violations, as well as identify the microservice(s) causing them. Once an imminent QoS violation is detected Seer uses machine-level hardware events to determine the cause of the QoS violation, and adjusts the resource allocations to prevent it. In local clusters with 10 40-core servers and 200-instance clusters on GCE running diverse cloud microservices, we show that Seer correctly anticipates QoS violations 91% of the time, and attributes the violation to the correct microservice in 89% of cases. Finally, Seer detects QoS violations early enough for a corrective action to almost always be applied successfully.
DOOM Level Generation using Generative Adversarial Networks
Venue: arXiv cs.LG 2018
Year: 2018

We applied Generative Adversarial Networks (GANs) to learn a model of DOOM levels from human-designed content. Initially, we analysed the levels and extracted several topological features. Then, for each level, we extracted a set of images identifying the occupied area, the height map, the walls, and the position of game objects. We trained two GANs: one using plain level images, one using both the images and some of the features extracted during the preliminary analysis. We used the two networks to generate new levels and compared the results to assess whether the network trained using also the topological features could generate levels more similar to human-designed ones. Our results show that GANs can capture intrinsic structure of DOOM levels and appears to be a promising approach to level generation in first person shooter games.
The quantitative measure and statistical distribution of fame
Venue: arXiv cs.SI 2018
Year: 2018

Fame and celebrity play an ever-increasing role in our culture. However, despite the cultural and economic importance of fame and its gradations, there exists no consensus method for quantifying the fame of an individual, or of comparing that of two individuals. We argue that, even if fame is difficult to measure with precision, one may develop useful metrics for fame that correlate well with intuition and that remain reasonably stable over time. Using datasets of recently deceased individuals who were highly renowned, we have evaluated several internet-based methods for quantifying fame. We find that some widely-used internet-derived metrics, such as search engine results, correlate poorly with human subject judgments of fame. However other metrics exist that agree well with human judgments and appear to offer workable, easily accessible measures of fame. Using such a metric we perform a preliminary investigation of the statistical distribution of fame, which has some of the power law character seen in other natural and social phenomena such as landslides and market crashes. In order to demonstrate how such findings can generate quantitative insight into celebrity culture, we assess some folk ideas regarding the frequency distribution and apparent clustering of celebrity deaths.
Resource Allocation and HARQ Optimization for URLLC Traffic in 5G Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

5G wireless networks are expected to support Ultra Reliable Low Latency Communications (URLLC) traffic which requires very low packet delays ( < 1 msec.) and extremely high reliability ($\sim$99.999\%). In this paper we focus on the design of a wireless system supporting downlink URLLC traffic. Using a queuing network based model for the wireless system we characterize the effect of various design choices on the maximum URLLC load it can support, including: 1) system parameters such as the bandwidth, link SINR , and QoS requirements; 2) resource allocation schemes in Orthogonal Frequency Division Multiple Access (OFDMA) based systems; and 3) Hybrid Automatic Repeat Request (HARQ) schemes. Key contributions of this paper which are of practical interest are: 1) study of how the the minimum required system bandwidth to support a given URLLC load scales with associated QoS constraints; 2) characterization of optimal OFDMA resource allocation schemes which maximize the admissible URLLC load; and 3) optimization of a repetition code based HARQ scheme which approximates Chase HARQ combining.
Cache-aware data structures for packet forwarding tables on general purpose CPUs
Venue: arXiv cs.NI 2018
Year: 2018

Longest prefix matching has long been the bottleneck of the Bloom filter-based solutions for packet forwarding implemented in software. We propose a search algorithm to match a destination IP address against a compact representation of the FIB table in CPU cache on general purpose hardware with an average performance target of O(log n) for an n-bit address.
Commonsense mining as knowledge base completion? A study on the impact of novelty
Venue: arXiv cs.CL 2018
Year: 2018

Commonsense knowledge bases such as ConceptNet represent knowledge in the form of relational triples. Inspired by the recent work by Li et al., we analyse if knowledge base completion models can be used to mine commonsense knowledge from raw text. We propose novelty of predicted triples with respect to the training set as an important factor in interpreting results. We critically analyse the difficulty of mining novel commonsense knowledge, and show that a simple baseline method outperforms the previous state of the art on predicting more novel.
An Adaptive Primary User Emulation Attack Detection Mechanism for Cognitive Radio Networks
Venue: arXiv cs.NI 2018
Year: 2018

The proliferation of advanced information technologies (IT), especially the wide spread of Internet of Things (IoTs) makes wireless spectrum a precious resource. Cognitive radio network (CRN) has been recognized as the key to achieve efficient utility of communication bands. Because of the great difficulty, high complexity and regulations in dynamic spectrum access (DSA), it is very challenging to protect CRNs from malicious attackers or selfish abusers. Primary user emulation (PUE) attacks is one type of easy-to-launch but hard-to-detect attacks in CRNs that malicious entities mimic PU signals in order to either occupy spectrum resource selfishly or conduct Denial of Service (DoS) attacks. Inspired by the physical features widely used as the fingerprint of variant electronic devices, an adaptive and realistic PUE attack detection technique is proposed in this paper. It leverages the PU transmission features that attackers are not able to mimic. In this work, the transmission power is selected as one of the hard-to-mimic features due to the intrinsic discrepancy between PUs and attackers, while considering constraints in real implementations. Our experimental results verified the effectiveness and correctness of the proposed mechanism.
BlendCAC: A BLockchain-ENabled Decentralized Capability-based Access Control for IoTs
Venue: arXiv cs.NI 2018
Year: 2018

The prevalence of Internet of Things (IoTs) allows heterogeneous embedded smart devices to collaboratively provide smart services with or without human intervention. While leveraging the large scale IoT based applications like Smart Gird or Smart Cities, IoTs also incur more concerns on privacy and security. Among the top security challenges that IoTs face, access authorization is critical in resource sharing and information protection. One of the weaknesses in today's access control (AC) is the centralized authorization server, which can be the performance bottleneck or the single point of failure. In this paper, BlendCAC, a blockchain enabled decentralized capability based AC is proposed for the security of IoTs. The BlendCAC aims at an effective access control processes to devices, services and information in large scale IoT systems. Based on the blockchain network, a capability delegation mechanism is suggested for access permission propagation. A robust identity based capability token management strategy is proposed, which takes advantage of smart contract for registering, propagation and revocation of the access authorization. In the proposed BlendCAC scheme, IoT devices are their own master to control their resources instead of being supervised by a centralized authority. Implemented and tested on a Raspberry Pi device and on a local private blockchain network, our experimental results demonstrate the feasibility of the proposed BlendCAC approach to offer a decentralized, scalable, lightweight and fine grained AC solution to IoT systems.
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes
Venue: arXiv cs.DS 2018
Year: 2018

We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C ? A major difficulty in this task is that the Maximum Matching problem is not preserved by quotient, thereby making difficult to exploit the structural properties of the quotient subgraphs of the modular decomposition. So far, we are only aware of a recent framework in [Coudert et al., SODA'18] that only applies when the quotient subgraphs have bounded order and/or under additional assumptions on the nontriv-ial modules in the graph. As a first attempt toward improving this framework we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. More precisely, we remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a "pruned modular decomposition", that can be computed in O(m log n)-time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. This result is mostly based on two pruning rules on pendant and anti-pendant modules -- that are adjacent, respectively, to one or all but one other modules in the graph. Furthermore, these two latter rules are surprisingly intricate and we consider them as our main technical contribution in the paper. We stress that the class of graphs that can be totally decomposed by the pruned modular decomposition contains all the distance-hereditary graphs, and so, it is larger than cographs. In particular, as a byproduct of our approach we also obtain the first known linear-time algorithms for Maximum Matching on distance-hereditary graphs and graphs with modular-treewidth at most one. Finally, we can use an extended version of our framework in order to compute a maximum matching, in linear-time, for all graph classes that can be modularly decomposed into cycles. Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.
Incremental Optimization of Independent Sets under Reachability Constraints
Venue: arXiv cs.DM 2018
Year: 2018

We introduce a new framework for reconfiguration problems, and apply it to independent sets as the first example. Suppose that we are given an independent set $I_0$ of a graph $G$, and an integer $l \ge 0$ which represents a lower bound on the size of any independent set of $G$. Then, we are asked to find an independent set of $G$ having the maximum size among independent sets that are reachable from $I_0$ by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least $l$. We show that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the fixed-parameter (in)tractability of the problem with respect to the following three parameters: the degeneracy $d$ of an input graph, a lower bound $l$ on the size of the independent sets, and a lower bound $s$ on the solution size. We show that the problem is fixed-parameter intractable when only one of $d$, $l$, and $s$ is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by $s+d$; this result implies that the problem parameterized only by $s$ is fixed-parameter tractable for planar graphs, and for bounded treewidth graphs.
Price of Anarchy for Mechanisms with Risk-Averse Agents
Venue: arXiv cs.GT 2018
Year: 2018

We study the price of anarchy of mechanisms in the presence of risk-averse agents. Previous work has focused on agents with quasilinear utilities, possibly with a budget. Our model subsumes this as a special case but also captures that agents might be less sensitive to payments than in the risk-neutral model. We show that many positive price-of-anarchy results proved in the smoothness framework continue to hold in the more general risk-averse setting. A sufficient condition is that agents can never end up with negative quasilinear utility after playing an undominated strategy. This is true, e.g., for first-price and second-price auctions. For all-pay auctions, similar results do not hold: We show that there are Bayes-Nash equilibria with arbitrarily bad social welfare compared to the optimum.
Deep Convolutional AutoEncoder-based Lossy Image Compression
Venue: arXiv cs.CV 2018
Year: 2018

Image compression has been investigated as a fundamental research topic for many decades. Recently, deep learning has achieved great success in many computer vision tasks, and is gradually being used in image compression. In this paper, we present a lossy image compression architecture, which utilizes the advantages of convolutional autoencoder (CAE) to achieve a high coding efficiency. First, we design a novel CAE architecture to replace the conventional transforms and train this CAE using a rate-distortion loss function. Second, to generate a more energy-compact representation, we utilize the principal components analysis (PCA) to rotate the feature maps produced by the CAE, and then apply the quantization and entropy coder to generate the codes. Experimental results demonstrate that our method outperforms traditional image coding algorithms, by achieving a 13.7% BD-rate decrement on the Kodak database images compared to JPEG2000. Besides, our method maintains a moderate complexity similar to JPEG2000.
GRASP: a GReen energy Aware SDN Platform
Venue: arXiv cs.NI 2018
Year: 2018

The transition to renewable energy sources for data centers has become a popular trend in the IT industry. However, the volatility of renewable energy, such as solar and wind power, impedes the operation of green data centers. In this work, we leverage Software Defined Networking (SDN) to build GRASP, a platform that schedules job requests to distributed data centers according to the amount of green energy available at each site. GRASP can be re-configured with different scheduling algorithms to address diverse factors such as amounts of instantly available solar power, wind power and CPU load of data centers. We utilize realistic green energy datasets from National Solar Radiation Database and evaluate GRASP in the GENI testbed; in addition, we create necessary GENI artifacts to repeat our experiment. GRASP can serve as a practical platform to test various job scheduling mechanisms for distributed green data centers.
Evaluating Low-Power Wireless Cyber-Physical Systems
Venue: arXiv cs.NI 2018
Year: 2018

Simulation tools and testbeds have been proposed to assess the performance of control designs and wireless protocols in isolation. A cyber-physical system (CPS), however, integrates control with network elements, which must be evaluated together under real-world conditions to assess control performance, stability, and associated costs. We present an approach to evaluate CPS relying on embedded devices and low-power wireless technology. Using one or multiple inverted pendulums as physical system, our approach supports a spectrum of realistic CPS scenarios that impose different requirements onto the control and networking elements. Moreover, our approach allows one to flexibly combine simulated and real pendulums, promoting adoption, scalability, repeatability, and integration with existing wireless testbed infrastructures. A case study demonstrates implementation, execution, and measurements using the proposed evaluation approach.
Charades-Ego: A Large-Scale Dataset of Paired Third and First Person Videos
Venue: arXiv cs.CV 2018
Year: 2018

In Actor and Observer we introduced a dataset linking the first and third-person video understanding domains, the Charades-Ego Dataset. In this paper we describe the egocentric aspect of the dataset and present annotations for Charades-Ego with 68,536 activity instances in 68.8 hours of first and third-person video, making it one of the largest and most diverse egocentric datasets available. Charades-Ego furthermore shares activity classes, scripts, and methodology with the Charades dataset, that consist of additional 82.3 hours of third-person video with 66,500 activity instances. Charades-Ego has temporal annotations and textual descriptions, making it suitable for egocentric video classification, localization, captioning, and new tasks utilizing the cross-modal nature of the data.
Quickest Search for a Change Point
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers a sequence of random variables generated according to a common distribution. The distribution might undergo periods of transient changes at an unknown set of time instants, referred to as change-points. The objective is to sequentially collect measurements from the sequence and design a dynamic decision rule for the quickest identification of one change-point in real time, while, in parallel, the rate of false alarms is controlled. This setting is different from the conventional change-point detection settings in which there exists at most one change-point that can be either persistent or transient. The problem is considered under the minimax setting with a constraint on the false alarm rate before the first change occurs. It is proved that the Shewhart test achieves exact optimality under worst-case change points and also worst-case data realization. Numerical evaluations are also provided to assess the performance of the decision rule characterized.