OpenRaiser/Intern-Atlas huggingface dataset:
Memory Efficient Forwarding Information Base for Content-Centric Networking
Venue: arXiv cs.NI 2017
Year: 2017

Content-Centric Networking (CCN) is a new paradigm for the future Internet where content is addressed by hierarchically organized names with the goal to replace TCP/IP networks. Unlike IP addresses, names have arbitrary length and are larger than the four bytes of IPv4 addresses. One important data structure in CCN is the Forwarding Information Base (FIB) where prefixes of names are stored together with the forwarding face. Long prefixes create problems for memory constrained Internet of Things (IoT) devices. In this work, we derive requirements for a FIB in the IoT and survey possible solutions. We investigate, design and compare memory-efficient solutions for the FIB based on hashes and Bloom-Filters. For large number of prefixes and an equal distribution of prefixes to faces we recommend a FIB implementation based on Bloom-Filters. In all other cases, we recommend an implementation of the FIB with hashes.
Classification of Smart Environment Scenarios in combination with a Human-Wearable-Environment-Communication using wireless connectivity
Venue: arXiv cs.HC 2017
Year: 2017

The development of computer technology has been rapid. Not so long ago, the first computer was developed which was large and bulky. Now, the latest generation of smartphones has a calculation power, which would have been considered those of supercomputers in 1990. For a smart environment, the person recognition and re-recognition is an important topic. The distribution of new technologies like wearable computing is a new approach to the field of person recognition and re-recognition. This article lays out the idea of identifying and re-identifying wearable computing devices by listening to their wireless communication connectivity like Wi-Fi and Bluetooth and building a classification of interaction scenarios for the combination of human-wearable-environment.
Latency Optimized Asynchronous Early Output Ripple Carry Adder based on Delay-Insensitive Dual-Rail Data Encoding
Venue: arXiv cs.AR 2017
Year: 2017

Asynchronous circuits employing delay-insensitive codes for data representation i.e. encoding and following a 4-phase return-to-zero protocol for handshaking are generally robust. Depending upon whether a single delay-insensitive code or multiple delay-insensitive code(s) are used for data encoding, the encoding scheme is called homogeneous or heterogeneous delay-insensitive data encoding. This article proposes a new latency optimized early output asynchronous ripple carry adder (RCA) that utilizes single-bit asynchronous full adders (SAFAs) and dual-bit asynchronous full adders (DAFAs) which incorporate redundant logic and are based on the delay-insensitive dual-rail code i.e. homogeneous data encoding, and follow a 4-phase return-to-zero handshaking. Amongst various RCA, carry lookahead adder (CLA), and carry select adder (CSLA) designs, which are based on homogeneous or heterogeneous delay-insensitive data encodings which correspond to the weak-indication or the early output timing model, the proposed early output asynchronous RCA that incorporates SAFAs and DAFAs with redundant logic is found to result in reduced latency for a dual-operand addition operation. In particular, for a 32-bit asynchronous RCA, utilizing 15 stages of DAFAs and 2 stages of SAFAs leads to reduced latency. The theoretical worst-case latencies of the different asynchronous adders were calculated by taking into account the typical gate delays of a 32/28nm CMOS digital cell library, and a comparison is made with their practical worst-case latencies estimated. The theoretical and practical worst-case latencies show a close correlation....
A Blockchain-based Approach for Data Accountability and Provenance Tracking
Venue: arXiv cs.CR 2017
Year: 2017

The recent approval of the General Data Protection Regulation (GDPR) imposes new data protection requirements on data controllers and processors with respect to the processing of European Union (EU) residents' data. These requirements consist of a single set of rules that have binding legal status and should be enforced in all EU member states. In light of these requirements, we propose in this paper the use of a blockchain-based approach to support data accountability and provenance tracking. Our approach relies on the use of publicly auditable contracts deployed in a blockchain that increase the transparency with respect to the access and usage of data. We identify and discuss three different models for our approach with different granularity and scalability requirements where contracts can be used to encode data usage policies and provenance tracking information in a privacy-friendly way. From these three models we designed, implemented, and evaluated a model where contracts are deployed by data subjects for each data controller, and a model where subjects join contracts deployed by data controllers in case they accept the data handling conditions. Our implementations show in practice the feasibility and limitations of contracts for the purposes identified in this paper.
Provable benefits of representation learning
Venue: arXiv cs.LG 2017
Year: 2017

There is general consensus that learning representations is useful for a variety of reasons, e.g. efficient use of labeled data (semi-supervised learning), transfer learning and understanding hidden structure of data. Popular techniques for representation learning include clustering, manifold learning, kernel-learning, autoencoders, Boltzmann machines, etc. To study the relative merits of these techniques, it's essential to formalize the definition and goals of representation learning, so that they are all become instances of the same definition. This paper introduces such a formal framework that also formalizes the utility of learning the representation. It is related to previous Bayesian notions, but with some new twists. We show the usefulness of our framework by exhibiting simple and natural settings -- linear mixture models and loglinear models, where the power of representation learning can be formally shown. In these examples, representation learning can be performed provably and efficiently under plausible assumptions (despite being NP-hard), and furthermore: (i) it greatly reduces the need for labeled data (semi-supervised learning) and (ii) it allows solving classification tasks when simpler approaches like nearest neighbors require too much data (iii) it is more powerful than manifold learning methods.
Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms
Venue: arXiv cs.GT 2017
Year: 2017

We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite showed that even with only one seller and one buyer, no Individually Rational (IR), Bayesian Incentive Compatible (BIC) and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). On the other hand, they proposed the "second-best" mechanism that maximizes the GFT subject to IR, BIC and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, IR, BIC and BB, and achieves $\frac{1}{2}$ of the optimal GFT among all IR, BIC and BB mechanisms. Our result holds for arbitrary distributions of the buyers' and sellers' values and can accommodate any downward-closed feasibility constraints over the allocations. The analysis of our mechanism is facilitated by extending the Cai-Weinberg-Devanur duality framework to two-sided markets.
PrettyCat: Adaptive guarantee-controlled software partitioning of security protocols
Venue: arXiv cs.CR 2017
Year: 2017

One single error can result in a total compromise of all security in today's large, monolithic software. Partitioning of software can help simplify code-review and verification, whereas isolated execution of software-components limits the impact of incorrect implementations. However, existing application partitioning techniques are too expensive, too imprecise, or involve unsafe manual steps. An automatic, yet safe, approach to dissect security protocols into component-based systems is not available. We present a method and toolset to automatically segregate security related software into an indefinite number of partitions, based on the security guarantees required by the deployed cryptographic building blocks. As partitioning imposes communication overhead, we offer a range of sound performance optimizations. Furthermore, by applying our approach to the secure messaging protocol OTR, we demonstrate its applicability and achieve a significant reduction of the trusted computing base. Compared to a monolithic implementation, only 29% of the partitioned protocol requires confidentiality guarantees with a process overhead comparable to common sandboxing techniques.
A Policy-Aware Model for Intelligent Transportation Systems
Venue: arXiv cs.NI 2017
Year: 2017

Recent advancements in the field of smart machine-to-machine (M2M) communications impose the necessity to improve the service delivery by enforcing appropriate security rules. Due to the large number of connected devices, the criticality of the M2M applications, and the network stability weaknesses, we need to consider and analyse the security aspects and establish a flexible policy-aware architecture. This paper explores the relevant architectural challenges in this environment and proposes a Policy-Aware smart M2M Architecture (PAArc) based on ETSI M2M communications functional architecture. We explore the policy-based management aspects to improve the security of the M2M components and services and to mitigate the security concerns that arise by evaluating an Intelligent Transportation System use case. It is shown that the policy enforcement enables enhanced security management capabilities, increased agility, and better service levels in the field of smart M2M communications.
Improved Set-based Symbolic Algorithms for Parity Games
Venue: arXiv cs.DS 2017
Year: 2017

Graph games with ω-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify ω-regular winning conditions. Graph games with parity conditions are equivalent to μ-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with $n$ vertices and parity conditions with $c$ priorities. While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires $O(n^c)$ symbolic operations and linear space; and (b) an improved algorithm that requires $O(n^{c/2+1})$ symbolic operations but also $O(n^{c/2+1})$ space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires $O(n^{c/2+1})$ symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires $O(n^{c/3+1})$ symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations.
A softening-healing law for self-healing quasi-brittle materials: analyzing with Strong Discontinuity embedded Approach
Venue: arXiv cs.CE 2017
Year: 2017

Quasi-brittle materials such as concrete suffer from cracks during their life cycle, requiring great cost for conventional maintenance or replacement. In the last decades, self-healing materials are developed which are capable of filling and healing the cracks and regaining part of the stiffness and strength automatically after getting damaged, bringing the possibility of maintenance-free materials and structures. In this paper, a time dependent softening-healing law for self-healing quasi-brittle materials is presented by introducing limited material parameters with clear physical background. Strong Discontinuity embedded Approach (SDA) is adopted for evaluating the reliability of the model. In the numerical studies, values of healing parameters are firstly obtained by back analysis of experimental results of self-healing beams. Then numerical models regarding concrete members and structures built with self-healing and non-healing materials are simulated and compared for showing the capability of the self-healing material.
Investigating the Potential of Pseudo Quadrature Mirror Filter-Banks in Music Source Separation Tasks
Venue: arXiv cs.SD 2017
Year: 2017

Estimating audio and musical signals from single channel mixtures often, if not always, involves a transformation of the mixture signal to the time-frequency (T-F) domain in which a masking operation takes place. Masking is realized as an element-wise multiplication of the mixture signal's T-F representation with a ratio of computed sources' spectrogram. Studies have shown that the performance of the overall source estimation scheme is subject to the sparsity and disjointness properties of a given T-F representation. In this work we investigate the potential of an optimized pseudo quadrature mirror filter-bank (PQMF), as a T-F representation for music source separation tasks. Experimental results, suggest that the PQMF maintains the aforementioned desirable properties and can be regarded as an alternative for representing mixtures of musical signals.
The complexity of the Multiple Pattern Matching Problem for random strings
Venue: arXiv cs.DS 2017
Year: 2017

We generalise a multiple string pattern matching algorithm, recently proposed by Fredriksson and Grabowski [J. Discr. Alg. 7, 2009], to deal with arbitrary dictionaries on an alphabet of size $s$. If $r_m$ is the number of words of length $m$ in the dictionary, and $ϕ(r) = \max_m \ln(s\, m\, r_m)/m$, the complexity rate for the string characters to be read by this algorithm is at most $κ_{{}_\textrm{UB}}\, ϕ(r)$ for some constant $κ_{{}_\textrm{UB}}$. On the other side, we generalise the classical lower bound of Yao [SIAM J. Comput. 8, 1979], for the problem with a single pattern, to deal with arbitrary dictionaries, and determine it to be at least $κ_{{}_\textrm{LB}}\, ϕ(r)$. This proves the optimality of the algorithm, improving and correcting previous claims.
Generalized Voltage-based State-Space Modelling of Modular Multilevel Converters with Constant Equilibrium in Steady-State
Venue: arXiv cs.SY 2017
Year: 2017

This paper demonstrates that the sum and difference of the upper and lower arm voltages are suitable variables for deriving a generalized state-space model of an MMC which settles at a constant equilibrium in steady-state operation, while including the internal voltage and current dynamics. The presented modelling approach allows for separating the multiple frequency components appearing within the MMC as a first step of the model derivation, to avoid variables containing multiple frequency components in steady-state. On this basis, it is shown that Park transformations at three different frequencies ($+ω$, $-2ω$ and $+3ω$) can be applied for deriving a model formulation where all state-variables will settle at constant values in steady-state, corresponding to an equilibrium point of the model. The resulting model is accurately capturing the internal current and voltage dynamics of a three-phase MMC, independently from how the control system is implemented. The main advantage of this model formulation is that it can be linearised, allowing for eigenvalue-based analysis of the MMC dynamics. Furthermore, the model can be utilized for control system design by multi-variable methods requiring any stable equilibrium to be defined by a fixed operating point. Time-domain simulations in comparison to an established average model of the MMC, as well as results from a detailed simulation model of an MMC with 400 sub-modules per arm, are presented as verification of the validity and accuracy of the developed model.
Research Topics Map: rtopmap
Venue: arXiv cs.IR 2017
Year: 2017

In this paper we describe a system for visualizing and analyzing worldwide research topics, {\tt rtopmap}. We gather data from google scholar academic research profiles, putting together a weighted topics graph, consisting of over 35,000 nodes and 646,000 edges. The nodes correspond to self-reported research topics, and edges correspond to co-occurring topics in google scholar profiles. The {\tt rtopmap} system supports zooming/panning/searching and other google-maps-based interactive features. With the help of map overlays, we also visualize the strengths and weaknesses of different academic institutions in terms of human resources (e.g., number of researchers in different areas), as well as scholarly output (e.g., citation counts in different areas). Finally, we also visualize what parts of the map are associated with different academic departments, or with specific documents (such as research papers, or calls for proposals). The system itself is available at \url{http://rtopmap.arl.arizona.edu/}.
Conjunctions of Among Constraints
Venue: arXiv cs.AI 2017
Year: 2017

Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its range, is within some given bounds. It is known that domain filtering algorithms can benefit from reasoning about the interaction of among constraints so that values can be filtered out taking into consideration several among constraints simultaneously. The present pa- per embarks into a systematic investigation on the circumstances under which it is possible to obtain efficient and complete domain filtering algorithms for conjunctions of among constraints. We start by observing that restrictions on both the scope and the range of the among constraints are necessary to obtain meaningful results. Then, we derive a domain flow-based filtering algorithm and present several applications. In particular, it is shown that the algorithm unifies and generalizes several previous existing results.
Learning Disjunctions of Predicates
Venue: arXiv cs.LG 2017
Year: 2017

Let $F$ be a set of boolean functions. We present an algorithm for learning $F_\vee := \{\vee_{f\in S} f \mid S \subseteq F\}$ from membership queries. Our algorithm asks at most $|F| \cdot OPT(F_\vee)$ membership queries where $OPT(F_\vee)$ is the minimum worst case number of membership queries for learning $F_\vee$. When $F$ is a set of halfspaces over a constant dimension space or a set of variable inequalities, our algorithm runs in polynomial time. The problem we address has practical importance in the field of program synthesis, where the goal is to synthesize a program that meets some requirements. Program synthesis has become popular especially in settings aiming to help end users. In such settings, the requirements are not provided upfront and the synthesizer can only learn them by posing membership queries to the end user. Our work enables such synthesizers to learn the exact requirements while bounding the number of membership queries.
Evaluating Noisy Optimisation Algorithms: First Hitting Time is Problematic
Venue: arXiv cs.NE 2017
Year: 2017

A key part of any evolutionary algorithm is fitness evaluation. When fitness evaluations are corrupted by noise, as happens in many real-world problems as a consequence of various types of uncertainty, a strategy is needed in order to cope with this. Resampling is one of the most common strategies, whereby each solution is evaluated many times in order to reduce the variance of the fitness estimates. When evaluating the performance of a noisy optimisation algorithm, a key consideration is the stopping condition for the algorithm. A frequently used stopping condition in runtime analysis, known as "First Hitting Time", is to stop the algorithm as soon as it encounters the optimal solution. However, this is unrealistic for real-world problems, as if the optimal solution were already known, there would be no need to search for it. This paper argues that the use of First Hitting Time, despite being a commonly used approach, is significantly flawed and overestimates the quality of many algorithms in real-world cases, where the optimum is not known in advance and has to be genuinely searched for. A better alternative is to measure the quality of the solution an algorithm returns after a fixed evaluation budget, i.e., to focus on final solution quality. This paper argues that focussing on final solution quality is more realistic and demonstrates cases where the results produced by each algorithm evaluation method lead to very different conclusions regarding the quality of each noisy optimisation algorithm.
Transportation in Social Media: an automatic classifier for travel-related tweets
Venue: arXiv cs.CY 2017
Year: 2017

In the last years researchers in the field of intelligent transportation systems have made several efforts to extract valuable information from social media streams. However, collecting domain-specific data from any social media is a challenging task demanding appropriate and robust classification methods. In this work we focus on exploring geo-located tweets in order to create a travel-related tweet classifier using a combination of bag-of-words and word embeddings. The resulting classification makes possible the identification of interesting spatio-temporal relations in São Paulo and Rio de Janeiro.
An Automatic Approach for Document-level Topic Model Evaluation
Venue: arXiv cs.CL 2017
Year: 2017

Topic models jointly learn topics and document-level topic distribution. Extrinsic evaluation of topic models tends to focus exclusively on topic-level evaluation, e.g. by assessing the coherence of topics. We demonstrate that there can be large discrepancies between topic- and document-level model quality, and that basing model evaluation on topic-level analysis can be highly misleading. We propose a method for automatically predicting topic model quality based on analysis of document-level topic allocations, and provide empirical evidence for its robustness.
Parameterized Verification of Algorithms for Oblivious Robots on a Ring
Venue: arXiv cs.DC 2017
Year: 2017

We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameter-ized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several properties on the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies.