OpenRaiser/Intern-Atlas huggingface dataset:
Wireless Sensor Network Virtualization: Early Architecture and Research Perspectives
Venue: arXiv cs.NI 2015
Year: 2015

Wireless sensor networks (WSNs) have become pervasive and are used in many applications and services. Usually the deployments of WSNs are task oriented and domain specific; thereby precluding re-use when other applications and services are contemplated. This inevitably leads to the proliferation of redundant WSN deployments. Virtualization is a technology that can aid in tackling this issue, as it enables the sharing of resources/infrastructure by multiple independent entities. In this paper we critically review the state of the art and propose a novel architecture for WSN virtualization. The proposed architecture has four layers (physical layer, virtual sensor layer, virtual sensor access layer and overlay layer) and relies on the constrained application protocol (CoAP). We illustrate its potential by using it in a scenario where a single WSN is shared by multiple applications; one of which is a fire monitoring application. We present the proof-of-concept prototype we have built along with the performance measurements, and discuss future research directions.
Enhancing Reuse of Constraint Solutions to Improve Symbolic Execution
Venue: arXiv cs.SE 2015
Year: 2015

Constraint solution reuse is an effective approach to save the time of constraint solving in symbolic execution. Most of the existing reuse approaches are based on syntactic or semantic equivalence of constraints; e.g. the Green framework is able to reuse constraints which have different representations but are semantically equivalent, through canonizing constraints into syntactically equivalent normal forms. However, syntactic/semantic equivalence is not a necessary condition for reuse--some constraints are not syntactically or semantically equivalent, but their solutions still have potential for reuse. Existing approaches are unable to recognize and reuse such constraints. In this paper, we present GreenTrie, an extension to the Green framework, which supports constraint reuse based on the logical implication relations among constraints. GreenTrie provides a component, called L-Trie, which stores constraints and solutions into tries, indexed by an implication partial order graph of constraints. L-Trie is able to carry out logical reduction and logical subset and superset querying for given constraints, to check for reuse of previously solved constraints. We report the results of an experimental assessment of GreenTrie against the original Green framework, which shows that our extension achieves better reuse of constraint solving result and saves significant symbolic execution time.
Structural Patterns of the Occupy Movement on Facebook
Venue: arXiv cs.SI 2015
Year: 2015

In this work we study a peculiar example of social organization on Facebook: the Occupy Movement -- i.e., an international protest movement against social and economic inequality organized online at a city level. We consider 179 US Facebook public pages during the time period between September 2011 and February 2013. The dataset includes 618K active users and 753K posts that received about 5.2M likes and 1.1M comments. By labeling user according to their interaction patterns on pages -- e.g., a user is considered to be polarized if she has at least the 95% of her likes on a specific page -- we find that activities are not locally coordinated by geographically close pages, but are driven by pages linked to major US cities that act as hubs within the various groups. Such a pattern is verified even by extracting the backbone structure -- i.e., filtering statistically relevant weight heterogeneities -- for both the pages-reshares and the pages-common users networks.
Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras
Venue: arXiv cs.LO 2015
Year: 2015

Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. Similar to well-known results for monadic second-order logic over trees, we provide a translation of this logic into a class of automata, relative to the class of coalgebras that admit a tree-like supporting Kripke frame. We then consider invariance under behavioral equivalence of formulas; more in particular, we investigate whether the coalgebraic mu-calculus is the bisimulation-invariant fragment of monadic second-order logic. Building on recent results by the third author we show that in order to provide such a coalgebraic generalization of the Janin-Walukiewicz Theorem, it suffices to find what we call an adequate uniform construction for the functor. As applications of this result we obtain a partly new proof of the Janin-Walukiewicz Theorem, and bisimulation invariance results for the bag functor (graded modal logic) and all exponential polynomial functors. Finally, we consider in some detail the monotone neighborhood functor, which provides coalgebraic semantics for monotone modal logic. It turns out that there is no adequate uniform construction for this functor, whence the automata-theoretic approach towards bisimulation invariance does not apply directly. This problem can be overcome if we consider global bisimulations between neighborhood models: one of our main technical results provides a characterization of the monotone modal mu-calculus extended with the global modalities, as the fragment of monadic second-order logic for the monotone neighborhood functor that is invariant for global bisimulations.
Distributionally Robust Counterpart in Markov Decision Processes
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies Markov Decision Processes under parameter uncertainty. We adapt the distributionally robust optimization framework, and assume that the uncertain parameters are random variables following an unknown distribution, and seeks the strategy which maximizes the expected performance under the most adversarial distribution. In particular, we generalize previous study \cite{xu2012distributionally} which concentrates on distribution sets with very special structure to much more generic class of distribution sets, and show that the optimal strategy can be obtained efficiently under mild technical condition. This significantly extends the applicability of distributionally robust MDP to incorporate probabilistic information of uncertainty in a more flexible way.
Tejas Simulator : Validation against Hardware
Venue: arXiv cs.AR 2015
Year: 2015

In this report we show results that validate the Tejas architectural simulator against native hardware. We report mean error rates of 11.45% and 18.77% for the SPEC2006 and Splash2 benchmark suites respectively. These error rates are competitive and in most cases better than the numbers reported by other contemporary simulators.
Contemporary Internet of Things platforms
Venue: arXiv cs.OH 2015
Year: 2015

This document regroups a representative, but non-exhaustive, list of contemporary IoT platforms. The platforms are ordered alphabetically. The aim of this document is to provide the a quick review of current IoT platforms, as well as relevant information.
When Does an Ensemble of Matrices with Randomly Scaled Rows Lose Rank?
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of determining rank loss conditions for a concatenation of full-rank matrices, such that each row of the composing matrices is scaled by a random coefficient. This problem has applications in wireless interference management and recommendation systems. We determine necessary and sufficient conditions for the design of each matrix, such that the random ensemble will almost surely lose rank by a certain amount. The result is proved by converting the problem to determining rank loss conditions for the union of some specific matroids, and then using tools from matroid and graph theories to derive the necessary and sufficient conditions. As an application, we discuss how this result can be applied to the problem of topological interference management, and characterize the linear symmetric degrees of freedom for a class of network topologies.
Blob indentation identification via curvature measurement
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a novel method for identifying indentations on the boundary of solid 2D shape. It uses the signed curvature at a set of points along the boundary to identify indentations and provides one parameter for tuning the selection mechanism for discriminating indentations from other boundary irregularities. An efficient implementation is described based on the Fourier transform for calculating curvature from a sequence of points obtained from the boundary of a binary blob.
Reliable Initialization of GPU-enabled Parallel Stochastic Simulations Using Mersenne Twister for Graphics Processors
Venue: arXiv cs.DC 2015
Year: 2015

Parallel stochastic simulations tend to exploit more and more computing power and they are now also developed for General Purpose Graphics Process Units (GP-GPUs). Conse-quently, they need reliable random sources to feed their applications. We propose a survey of the current Pseudo Random Numbers Generators (PRNG) available on GPU. We give a particular focus to the recent Mersenne Twister for Graphics Processors (MTGP) that has just been released. Our work provides empirically checked statuses designed to initialize a particular configuration of this generator, in order to prevent any potential bias introduced by the parallelization of the PRNG.
Montblanc: GPU accelerated Radio Interferometer Measurement Equations in support of Bayesian Inference for Radio Observations
Venue: arXiv cs.DC 2015
Year: 2015

We present Montblanc, a GPU implementation of the Radio interferometer measurement equation (RIME) in support of the Bayesian inference for radio observations (BIRO) technique. BIRO uses Bayesian inference to select sky models that best match the visibilities observed by a radio interferometer. To accomplish this, BIRO evaluates the RIME multiple times, varying sky model parameters to produce multiple model visibilities. Chi-squared values computed from the model and observed visibilities are used as likelihood values to drive the Bayesian sampling process and select the best sky model. As most of the elements of the RIME and chi-squared calculation are independent of one another, they are highly amenable to parallel computation. Additionally, Montblanc caters for iterative RIME evaluation to produce multiple chi-squared values. Modified model parameters are transferred to the GPU between each iteration. We implemented Montblanc as a Python package based upon NVIDIA's CUDA architecture. As such, it is easy to extend and implement different pipelines. At present, Montblanc supports point and Gaussian morphologies, but is designed for easy addition of new source profiles. Montblanc's RIME implementation is performant: On an NVIDIA K40, it is approximately 250 times faster than MeqTrees on a dual hexacore Intel E5-2620v2 CPU. Compared to the OSKAR simulator's GPU-implemented RIME components it is 7.7 and 12 times faster on the same K40 for single and double-precision floating point respectively. However, OSKAR's RIME implementation is more general than Montblanc's BIRO-tailored RIME. Theoretical analysis of Montblanc's dominant CUDA kernel suggests that it is memory bound. In practice, profiling shows that is balanced between compute and memory, as much of the data required by the problem is retained in L1 and L2 cache.
Near Optimal Subdivision Algorithms for Real Root Isolation
Venue: arXiv cs.NA 2015
Year: 2015

We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subroutine first detects clusters of roots using a result of Ostrowski, and then uses Newton iteration to converge to them. Near a cluster, we switch to subdivision, and proceed recursively. The subroutine has the advantage that it is independent of the predicates used to terminate the subdivision. This gives us an alternative and simpler approach to recent developments of Sagraloff (2012) and Sagraloff-Mehlhorn (2013), assuming exact arithmetic. The subdivision tree size of our algorithm using predicates based on Descartes's rule of signs is bounded by $O(n\log n)$, which is better by $O(n\log L)$ compared to known results. Our analysis differs in two key aspects. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and second, we use the geometry of clusters of roots instead of the Davenport-Mahler bound. The analysis naturally extends to other predicates.
Predicting Results of the Research Excellence Framework using Departmental h-Index -- Revisited
Venue: arXiv cs.DL 2015
Year: 2015

We revisit our recent study [Predicting results of the Research Excellence Framework using departmental h-index, Scientometrics, 2014, 1-16; arXiv:1411.1996] in which we attempted to predict outcomes of the UK's Research Excellence Framework (REF~2014) using the so-called departmental $h$-index. Here we report that our predictions failed to anticipate with any accuracy either overall REF outcomes or movements of individual institutions in the rankings relative to their positions in the previous Research Assessment Exercise (RAE~2008).
A Trichotomy in the Data Complexity of Certain Query Answering for Conjunctive Queries
Venue: arXiv cs.DB 2015
Year: 2015

A relational database is said to be uncertain if primary key constraints can possibly be violated. A repair (or possible world) of an uncertain database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with the same primary key value. For any Boolean query q, CERTAINTY(q) is the problem that takes an uncertain database db on input, and asks whether q is true in every repair of db. The complexity of this problem has been particularly studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q, whether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. In this paper, we combine existing techniques for studying the above complexity classification task. We show that for any self-join-free Boolean conjunctive query q, it can be decided whether or not CERTAINTY(q) is in FO. Further, for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is either in P or coNP-complete, and the complexity dichotomy is effective. This settles a research question that has been open for ten years, since [9].
Sketch-a-Net that Beats Humans
Venue: arXiv cs.CV 2015
Year: 2015

We propose a multi-scale multi-channel deep neural network framework that, for the first time, yields sketch recognition performance surpassing that of humans. Our superior performance is a result of explicitly embedding the unique characteristics of sketches in our model: (i) a network architecture designed for sketch rather than natural photo statistics, (ii) a multi-channel generalisation that encodes sequential ordering in the sketching process, and (iii) a multi-scale network ensemble with joint Bayesian fusion that accounts for the different levels of abstraction exhibited in free-hand sketches. We show that state-of-the-art deep networks specifically engineered for photos of natural objects fail to perform well on sketch recognition, regardless whether they are trained using photo or sketch. Our network on the other hand not only delivers the best performance on the largest human sketch dataset to date, but also is small in size making efficient training possible using just CPUs.
TuPAQ: An Efficient Planner for Large-scale Predictive Analytic Queries
Venue: arXiv cs.DB 2015
Year: 2015

The proliferation of massive datasets combined with the development of sophisticated analytical techniques have enabled a wide variety of novel applications such as improved product recommendations, automatic image tagging, and improved speech-driven interfaces. These and many other applications can be supported by Predictive Analytic Queries (PAQs). A major obstacle to supporting PAQs is the challenging and expensive process of identifying and training an appropriate predictive model. Recent efforts aiming to automate this process have focused on single node implementations and have assumed that model training itself is a black box, thus limiting the effectiveness of such approaches on large-scale problems. In this work, we build upon these recent efforts and propose an integrated PAQ planning architecture that combines advanced model search techniques, bandit resource allocation via runtime algorithm introspection, and physical optimization via batching. The result is TuPAQ, a component of the MLbase system, which solves the PAQ planning problem with comparable quality to exhaustive strategies but an order of magnitude more efficiently than the standard baseline approach, and can scale to models trained on terabytes of data across hundreds of machines.
On Optimization of Network-coded Scalable Multimedia Service Multicasting
Venue: arXiv cs.IT 2015
Year: 2015

In the near future, the delivery of multimedia multicast services over next-generation networks is likely to become one of the main pillars of future cellular networks. In this extended abstract, we address the issue of efficiently multicasting layered video services by defining a novel optimization paradigm that is based on an Unequal Error Protection implementation of Random Linear Network Coding, and aims to ensure target service coverages by using a limited amount of radio resources.
Twitter Hash Tag Recommendation
Venue: arXiv cs.IR 2015
Year: 2015

The rise in popularity of microblogging services like Twitter has led to increased use of content annotation strategies like the hashtag. Hashtags provide users with a tagging mechanism to help organize, group, and create visibility for their posts. This is a simple idea but can be challenging for the user in practice which leads to infrequent usage. In this paper, we will investigate various methods of recommending hashtags as new posts are created to encourage more widespread adoption and usage. Hashtag recommendation comes with numerous challenges including processing huge volumes of streaming data and content which is small and noisy. We will investigate preprocessing methods to reduce noise in the data and determine an effective method of hashtag recommendation based on the popular classification algorithms.
Combining k-Induction with Continuously-Refined Invariants
Venue: arXiv cs.SE 2015
Year: 2015

Bounded model checking (BMC) is a well-known and successful technique for finding bugs in software. k-induction is an approach to extend BMC-based approaches from falsification to verification. Automatically generated auxiliary invariants can be used to strengthen the induction hypothesis. We improve this approach and further increase effectiveness and efficiency in the following way: we start with light-weight invariants and refine these invariants continuously during the analysis. We present and evaluate an implementation of our approach in the open-source verification-framework CPAchecker. Our experiments show that combining k-induction with continuously-refined invariants significantly increases effectiveness and efficiency, and outperforms all existing implementations of k-induction-based software verification in terms of successful verification results.
Hybrid Update/Invalidate Schemes for Cache Coherence Protocols
Venue: arXiv cs.DC 2015
Year: 2015

In general when considering cache coherence, write back schemes are the default. These schemes invalidate all other copies of a data block during a write. In this paper we propose several hybrid schemes that will switch between updating and invalidating on processor writes at runtime, depending on program conditions. We created our own cache simulator on which we could implement our schemes, and generated data sets from both commercial benchmarks and through artificial methods to run on the simulator. We analyze the results of running the benchmarks with various schemes, and suggest further research that can be done in this area.
Nonextensive analysis on the local structure entropy of complex networks
Venue: arXiv cs.SI 2015
Year: 2015

The local structure entropy is a new method which is proposed to identify the influential nodes in the complex networks. In this paper a new form of the local structure entropy of the complex networks is proposed based on the Tsallis entropy. The value of the entropic index $q$ will influence the property of the local structure entropy. When the value of $q$ is equal to 0, the nonextensive local structure entropy is degenerated to a new form of the degree centrality. When the value of $q$ is equal to 1, the nonextensive local structure entropy is degenerated to the existing form of the local structure entropy. We also have find a nonextensive threshold value in the nonextensive local structure entropy. When the value of $q$ is bigger than the nonextensive threshold value, change the value of $q$ will has no influence on the property of the local structure entropy, and different complex networks have different nonextensive threshold value. The results in this paper show that the new nonextensive local structure entropy is a generalised of the local structure entropy. It is more reasonable and useful than the existing one.
Intercept Behavior Analysis of Industrial Wireless Sensor Networks in the Presence of Eavesdropping Attack
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the intercept behavior of an industrial wireless sensor network (WSN) consisting of a sink node and multiple sensors in the presence of an eavesdropping attacker, where the sensors transmit their sensed information to the sink node through wireless links. Due to the broadcast nature of radio wave propagation, the wireless transmission from the sensors to the sink can be readily overheard by the eavesdropper for interception purposes. In an information-theoretic sense, the secrecy capacity of the wireless transmission is the difference between the channel capacity of the main link (from sensor to sink) and that of the wiretap link (from sensor to eavesdropper). If the secrecy capacity becomes non-positive due to the wireless fading effect, the sensor's data transmission could be successfully intercepted by the eavesdropper and an intercept event occurs in this case. However, in industrial environments, the presence of machinery obstacles, metallic frictions and engine vibrations makes the wireless fading fluctuate drastically, resulting in the degradation of the secrecy capacity. As a consequence, an optimal sensor scheduling scheme is proposed in this paper to protect the legitimate wireless transmission against the eavesdropping attack, where a sensor with the highest secrecy capacity is scheduled to transmit its sensed information to the sink. Closed-form expressions of the probability of occurrence of an intercept event (called intercept probability) are derived for the conventional round-robin scheduling and the proposed optimal scheduling schemes. Also, an asymptotic intercept probability analysis is conducted to provide an insight into the impact of the sensor scheduling on the wireless security. Numerical results demonstrate that the proposed sensor scheduling scheme outperforms the conventional round-robin scheduling in terms of the intercept probability.
Evolutionary Artificial Neural Network Based on Chemical Reaction Optimization
Venue: arXiv cs.NE 2015
Year: 2015

Evolutionary algorithms (EAs) are very popular tools to design and evolve artificial neural networks (ANNs), especially to train them. These methods have advantages over the conventional backpropagation (BP) method because of their low computational requirement when searching in a large solution space. In this paper, we employ Chemical Reaction Optimization (CRO), a newly developed global optimization method, to replace BP in training neural networks. CRO is a population-based metaheuristics mimicking the transition of molecules and their interactions in a chemical reaction. Simulation results show that CRO outperforms many EA strategies commonly used to train neural networks.