OpenRaiser/Intern-Atlas huggingface dataset:
Wireless Sensor Networks: Local Multicast Study
Venue: arXiv cs.NI 2016
Year: 2016

Wireless sensor networks and Ad-hoc network in the region Multicast (Geocasting) means to deliver the message to all nodes in a given geographical area from the source point. Regional Multicast practical application of the specified area and other regions may be formed to broadcast transmission and location-related business information, extensive advertising, or to send an urgent message. Regional multicast protocol design goal is to ensure messaging and low transport costs. Most have been proposed agreement does not guarantee message delivery, although some other guaranteed messaging protocol has triggered high transmission costs. The goal now is to ensure that research messaging and low-cost local transmission protocol and its algorithm, to promote the development of domain communication. This paper introduces the research background and research results, and proposed to solve the problems and ideas.
Using Semantic Similarity for Input Topic Identification in Crawling-based Web Application Testing
Venue: arXiv cs.SE 2016
Year: 2016

To automatically test web applications, crawling-based techniques are usually adopted to mine the behavior models, explore the state spaces or detect the violated invariants of the applications. However, in existing crawlers, rules for identifying the topics of input text fields, such as login ids, passwords, emails, dates and phone numbers, have to be manually configured. Moreover, the rules for one application are very often not suitable for another. In addition, when several rules conflict and match an input text field to more than one topics, it can be difficult to determine which rule suggests a better match. This paper presents a natural-language approach to automatically identify the topics of encountered input fields during crawling by semantically comparing their similarities with the input fields in labeled corpus. In our evaluation with 100 real-world forms, the proposed approach demonstrated comparable performance to the rule-based one. Our experiments also show that the accuracy of the rule-based approach can be improved by up to 19% when integrated with our approach.
Neural Networks with Smooth Adaptive Activation Functions for Regression
Venue: arXiv cs.CV 2016
Year: 2016

In Neural Networks (NN), Adaptive Activation Functions (AAF) have parameters that control the shapes of activation functions. These parameters are trained along with other parameters in the NN. AAFs have improved performance of Neural Networks (NN) in multiple classification tasks. In this paper, we propose and apply AAFs on feedforward NNs for regression tasks. We argue that applying AAFs in the regression (second-to-last) layer of a NN can significantly decrease the bias of the regression NN. However, using existing AAFs may lead to overfitting. To address this problem, we propose a Smooth Adaptive Activation Function (SAAF) with piecewise polynomial form which can approximate any continuous function to arbitrary degree of error. NNs with SAAFs can avoid overfitting by simply regularizing the parameters. In particular, an NN with SAAFs is Lipschitz continuous given a bounded magnitude of the NN parameters. We prove an upper-bound for model complexity in terms of fat-shattering dimension for any Lipschitz continuous regression model. Thus, regularizing the parameters in NNs with SAAFs avoids overfitting. We empirically evaluated NNs with SAAFs and achieved state-of-the-art results on multiple regression datasets.
Algorithms for the Iterative Estimation of Discrete-Valued Sparse Vectors
Venue: arXiv cs.IT 2016
Year: 2016

In Compressed Sensing, a real-valued sparse vector has to be estimated from an underdetermined system of linear equations. In many applications, however, the elements of the sparse vector are drawn from a finite set. For the estimation of these discrete-valued vectors, matched algorithms are required which take the additional knowledge of the discrete nature into account. In this paper, the estimation problem is treated from a communications engineering point of view. A powerful new algorithm incorporating techniques known from digital communications and information theory is derived. For comparison, Turbo Compressed Sensing is adapted to the discrete setup and a simplified and generalized notation is presented. The performance of the algorithms is covered by numerical simulations.
Fathom: Reference Workloads for Modern Deep Learning Methods
Venue: arXiv cs.LG 2016
Year: 2016

Deep learning has been popularized by its recent successes on challenging artificial intelligence problems. One of the reasons for its dominance is also an ongoing challenge: the need for immense amounts of computational power. Hardware architects have responded by proposing a wide array of promising ideas, but to date, the majority of the work has focused on specific algorithms in somewhat narrow application domains. While their specificity does not diminish these approaches, there is a clear need for more flexible solutions. We believe the first step is to examine the characteristics of cutting edge models from across the deep learning community. Consequently, we have assembled Fathom: a collection of eight archetypal deep learning workloads for study. Each of these models comes from a seminal work in the deep learning community, ranging from the familiar deep convolutional neural network of Krizhevsky et al., to the more exotic memory networks from Facebook's AI research group. Fathom has been released online, and this paper focuses on understanding the fundamental performance characteristics of each model. We use a set of application-level modeling tools built around the TensorFlow deep learning framework in order to analyze the behavior of the Fathom workloads. We present a breakdown of where time is spent, the similarities between the performance profiles of our models, an analysis of behavior in inference and training, and the effects of parallelism on scaling.
Application of Public Ledgers to Revocation in Distributed Access Control
Venue: arXiv cs.CR 2016
Year: 2016

There has recently been a flood of interest in potential new applications of blockchains, as well as proposals for more generic designs called public ledgers. Most of the novel proposals have been in the financial sector. However, the public ledger is an abstraction that solves several of the fundamental problems in the design of secure distributed systems: global time in the form of a strict linear order of past events, globally consistent and immutable view of the history, and enforcement of some application-specific safety properties. This paper investigates the applications of public ledgers to access control and, more specifically, to group management in distributed systems where entities are represented by their public keys and authorization is encoded into signed certificates. It is particularly difficult to handle negative information, such as revocation of certificates or group membership, in the distributed setting. The linear order of events and global consistency simplify these problems, but the enforcement of internal constraints in the ledger implementation often presents problems. We show that different types of revocation require slightly different properties from the ledger. We compare the requirements with Bitcoin, the best known blockchain, and describe an efficient ledger design for membership revocation that combines ideas from blockchains and from web-PKI monitoring. While we use certificate-based group-membership management as the case study, the same ideas can be applied more widely to rights revocation in distributed systems.
Resource Allocation in Dynamic TDD Heterogeneous Networks under Mixed Traffic
Venue: arXiv cs.NI 2016
Year: 2016

Recently, Dynamic Time Division Duplex (TDD) has been proposed to handle the asymmetry of traffic demand between DownLink (DL) and UpLink (UL) in Heterogeneous Networks (HetNets). However, for mixed traffic consisting of best effort traffic and soft Quality of Service (QoS) traffic, the resource allocation problem has not been adequately studied in Dynamic TDD HetNets. In this paper, we focus on such problem in a two-tier HetNet with co-channel deployment of one Macro cell Base Station (MBS) and multiple Small cell Base Stations (SBSs) in hotspots. Different from existing work, we introduce low power almost blank subframes to alleviate MBS-to-SBS interference which is inherent in TDD operation. To tackle the resource allocation problem, we propose a two-step strategy. First, from the view point of base stations, we propose a transmission protocol and perform time resource allocation by formulating and solving a network capacity maximization problem under DL/UL traffic demands. Second, from the view point of User Equipments (UEs), we formulate their resource allocation as a Network Utility Maximization (NUM) problem. An efficient iterative algorithm is proposed to solve the NUM problem. Simulations show the advantage of the proposed algorithm in terms of network throughput and UE QoS satisfaction level.
Parallel K-Medoids++ Spatial Clustering Algorithm Based on MapReduce
Venue: arXiv cs.DC 2016
Year: 2016

Clustering analysis has received considerable attention in spatial data mining for several years. With the rapid development of the geospatial information technologies, the size of spatial information data is growing exponentially which makes clustering massive spatial data a challenging task. In order to improve the efficiency of spatial clustering for large scale data, many researchers proposed several efficient clustering algorithms in parallel. In this paper, a new K-Medoids++ spatial clustering algorithm based on MapReduce for clustering massive spatial data is proposed. The initialization algorithm to decrease the number of iterations is combined with the MapReduce framework. Comparative Experiments conducted over different dataset and different number of nodes indicate that the proposed K-Medoids spatial clustering algorithm provides better efficiency than traditional K-Medoids and scales well while processing massive spatial data on commodity hardware.
Bayesian Statistics in Software Engineering: Practical Guide and Case Studies
Venue: arXiv cs.SE 2016
Year: 2016

Statistics comes in two main flavors: frequentist and Bayesian. For historical and technical reasons, frequentist statistics has dominated data analysis in the past; but Bayesian statistics is making a comeback at the forefront of science. In this paper, we give a practical overview of Bayesian statistics and illustrate its main advantages over frequentist statistics for the kinds of analyses that are common in empirical software engineering, where frequentist statistics still is standard. We also apply Bayesian statistics to empirical data from previous research investigating agile vs. structured development processes, the performance of programming languages, and random testing of object-oriented programs. In addition to being case studies demonstrating how Bayesian analysis can be applied in practice, they provide insights beyond the results in the original publications (which used frequentist statistics), thus showing the practical value brought by Bayesian statistics.
Design-Space Exploration and Optimization of an Energy-Efficient and Reliable 3D Small-world Network-on-Chip
Venue: arXiv cs.ET 2016
Year: 2016

A three-dimensional (3D) Network-on-Chip (NoC) enables the design of high performance and low power many-core chips. Existing 3D NoCs are inadequate for meeting the ever-increasing performance requirements of many-core processors since they are simple extensions of regular 2D architectures and they do not fully exploit the advantages provided by 3D integration. Moreover, the anticipated performance gain of a 3D NoC-enabled many-core chip may be compromised due to the potential failures of through-silicon-vias (TSVs) that are predominantly used as vertical interconnects in a 3D IC. To address these problems, we propose a machine-learning-inspired predictive design methodology for energy-efficient and reliable many-core architectures enabled by 3D integration. We demonstrate that a small-world network-based 3D NoC (3D SWNoC) performs significantly better than its 3D MESH-based counterparts. On average, the 3D SWNoC shows 35% energy-delay-product (EDP) improvement over 3D MESH for the PARSEC and SPLASH2 benchmarks considered in this work. To improve the reliability of 3D NoC, we propose a computationally efficient spare-vertical link (sVL) allocation algorithm based on a state-space search formulation. Our results show that the proposed sVL allocation algorithm can significantly improve the reliability as well as the lifetime of 3D SWNoC.
A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness
Venue: arXiv cs.DS 2016
Year: 2016

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n \log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \to \{0,1\}$. In this note we describe a simple non-adaptive, $O(n \log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.
Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
Venue: arXiv cs.DS 2016
Year: 2016

A 3-path vertex cover in a graph is a vertex subset $C$ such that every path of three vertices contains at least one vertex from $C$. The parameterized 3-path vertex cover problem asks whether a graph has a 3-path vertex cover of size at most $k$. In this paper, we give a kernel of $5k$ vertices and an $O^*(1.7485^k)$-time and polynomial-space algorithm for this problem, both new results improve previous known bounds.
The (minimum) rank of typical fooling set matrices
Venue: arXiv cs.DM 2016
Year: 2016

A fooling-set matrix has nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at least $\sqrt n$. It is known that the bound is tight (up to a multiplicative constant). We ask for the "typical" minimum rank of a fooling-set matrix: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field $\mathbb F$ closer to its lower bound $\sqrt{n}$ or to its upper bound $n$? We study random patterns with a given density $p$, and prove an $Ω(n)$ bound for the cases when: (a) $p$ tends to $0$ quickly enough, (b) $p$ tends to $0$ slowly, and $|\mathbb F|=O(1)$, (c) $p\in(0,1]$ is a constant. We have to leave open the case when $p\to 0$ slowly and $\mathbb F$ is a large or infinite field (e.g., $\mathbb F=GF(2^n)$, $F=\mathbb{R}$).
Transient performance analysis of zero-attracting LMS
Venue: arXiv cs.PF 2016
Year: 2016

Zero-attracting least-mean-square (ZA-LMS) algorithm has been widely used for online sparse system identification. It combines the LMS framework and $\ell_1$-norm regularization to promote sparsity, and relies on subgradient iterations. Despite the significant interest in ZA-LMS, few works analyzed its transient behavior. The main difficulty lies in the nonlinearity of the update rule. In this work, a detailed analysis in the mean and mean-square sense is carried out in order to examine the behavior of the algorithm. Simulation results illustrate the accuracy of the model and highlight its performance through comparisons with an existing model.
Modelling and evaluation of a multi-tag LED-ID platform
Venue: arXiv cs.NI 2016
Year: 2016

An LED-ID system works like an electronic "tag" transmitting a short digital broadcasted message. Low complexity LED-ID installations, being a subset of an emerging class of visible light communication (VLC) systems, may be considered as a replacement of popular RFID tags, Bluetooth tags and Wi-Fi beacons. In this work, we focus on multi LED-ID environments with "dense" tag placement. The problems that we focus on are estimating the level of cross-tag interference and the issue of tag proximity: how closely can we place the tags without making the system unusable? We present a theoretical model with a numerical simulation of sample arrangements. We also describe the results of experiments we conducted in a real- world test environment under different external lighting conditions.
A Simple Guide to S3 Methods
Venue: arXiv cs.PL 2016
Year: 2016

Writing functions in R is an important skill for anyone using R. S3 methods allow for functions to be generalised across different classes and are easy to implement. Whilst many R users are be adept at creating their own functions, it seems that there is room for many more to take advantage of R's S3 methods. This paper provides a simple and targeted guide to explain what S3 methods are, why people should them, and how they can do it.
Root Sparse Bayesian Learning for Off-Grid DOA Estimation
Venue: arXiv cs.IT 2016
Year: 2016

The performance of the existing sparse Bayesian learning (SBL) methods for off-gird DOA estimation is dependent on the trade off between the accuracy and the computational workload. To speed up the off-grid SBL method while remain a reasonable accuracy, this letter describes a computationally efficient root SBL method for off-grid DOA estimation, where a coarse refinable grid, whose sampled locations are viewed as the adjustable parameters, is adopted. We utilize an expectation-maximization (EM) algorithm to iteratively refine this coarse grid, and illustrate that each updated grid point can be simply achieved by the root of a certain polynomial. Simulation results demonstrate that the computational complexity is significantly reduced and the modeling error can be almost eliminated.
Scheduling Resource-Bounded Monitoring Devices for Event Detection and Isolation in Networks
Venue: arXiv cs.NI 2016
Year: 2016

In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, these devices have limited energy supplies, and they can operate for a limited duration. As a result, energy-efficient monitoring of various target locations through a set of monitoring devices with limited energy supplies is a crucial problem in networked systems. In this paper, we study optimal scheduling of monitoring devices to maximize network coverage for detecting and isolating events on targets for a given network lifetime. The monitoring devices considered could remain active only for a fraction of the overall network lifetime. We formulate the problem of scheduling of monitoring devices as a graph labeling problem, which unlike other existing solutions, allows us to directly utilize the underlying network structure to explore the trade-off between coverage and network lifetime. In this direction, first we propose a greedy heuristic to solve the graph labeling problem, and then provide a game-theoretic solution to achieve near optimal graph labeling. Moreover, the proposed setup can be used to simultaneously solve the scheduling and placement of monitoring devices, which yields improved performance as compared to separately solving the placement and scheduling problems. Finally, we illustrate our results on various networks, including real-world water distribution networks.
Scalable Compression of Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks generally involve some layers with mil- lions of parameters, making them difficult to be deployed and updated on devices with limited resources such as mobile phones and other smart embedded systems. In this paper, we propose a scalable representation of the network parameters, so that different applications can select the most suitable bit rate of the network based on their own storage constraints. Moreover, when a device needs to upgrade to a high-rate network, the existing low-rate network can be reused, and only some incremental data are needed to be downloaded. We first hierarchically quantize the weights of a pre-trained deep neural network to enforce weight sharing. Next, we adaptively select the bits assigned to each layer given the total bit budget. After that, we retrain the network to fine-tune the quantized centroids. Experimental results show that our method can achieve scalable compression with graceful degradation in the performance.
Uncovering Influence Cookbooks : Reverse Engineering the Topological Impact in Peer Ranking Services
Venue: arXiv cs.SI 2016
Year: 2016

Ensuring the early detection of important social network users is a challenging task. Some peer ranking services are now well established, such as PeerIndex, Klout, or Kred. Their function is to rank users according to their influence. This notion of influence is however abstract, and the algorithms achieving this ranking are opaque. Following the rising demand for a more transparent web, we explore the problem of gaining knowledge by reverse engineering such peer ranking services, with regards to the social network topology they get as an input. Since these services exploit the online activity of users (and therefore their connectivity in social networks), we provide a precise evaluation of how topological metrics of the social network impact the final user ranking. Our approach is the following : we first model the ranking service as a black-box with which we interact by creating user profiles and by performing operations on them. Through those profiles, we trigger some slight topological modifications. By monitoring the impact of these modifications on the rankings of those profiles, we infer the weight of each topological metric in the black-box, thus reversing the service influence cookbook.
A Note on the Practicality of Maximal Planar Subgraph Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

Given a graph $G$, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of $G$ with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but---to the best of our knowledge---they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice.
Re-embedding a 1-Plane Graph into a Straight-line Drawing in Linear Time
Venue: arXiv cs.CG 2016
Year: 2016

Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335-341, 1988]. In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.