OpenRaiser/Intern-Atlas huggingface dataset:
Formation of General Position by Asynchronous Mobile Robots
Venue: arXiv cs.DC 2014
Year: 2014

The traditional distributed model of autonomous, homogeneous, mobile point robots usually assumes that the robots do not create any visual obstruction for the other robots, i.e., the robots are see through. In this paper, we consider a slightly more realistic model, by incorporating the notion of obstructed visibility (i.e., robots are not see through) for other robots. Under the new model of visibility, a robot may not have the full view of its surroundings. Many of the existing algorithms demand that each robot should have the complete knowledge of the positions of other robots. Since, vision is the only mean of their communication, it is required that the robots are in general position (i.e., no three robots are collinear). We consider asynchronous robots. They also do not have common chirality (or any agreement on a global coordinate system). In this paper, we present a distributed algorithm for obtaining a general position for the robots in finite time from any arbitrary configuration. The algorithm also assures collision free motion for each robot. This algorithm may also be used as a preprocessing module for many other subsequent tasks performed by the robots.
Primary User-aware Network Coding for Multi-hop Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

Network coding has proved its efficiency in increasing the network performance for traditional ad-hoc networks. In this paper, we investigate using network coding for enhancing the throughput of multi-hop cognitive radio networks. We formulate the network coding throughput maximization problem as a graph theory problem, where different constraints and primary users' characteristics are mapped to the graph structure. We then show that the optimal solution to this problem in NP-hard and propose a heuristic algorithm to efficiently solve it. Evaluation of the proposed algorithm through NS2 simulations shows that we can increase the throughput of the constrained secondary users' network by 150\% to 200\% for a wide range of scenarios covering different primary users' densities, traffic loads, and spectrum availability.
Case Studies and Challenges in Reproducibility in the Computational Sciences
Venue: arXiv cs.CE 2014
Year: 2014

This paper investigates the reproducibility of computational science research and identifies key challenges facing the community today. It is the result of the First Summer School on Experimental Methodology in Computational Science Research (https://blogs.cs.st-andrews.ac.uk/emcsr2014/). First, we consider how to reproduce experiments that involve human subjects, and in particular how to deal with different ethics requirements at different institutions. Second, we look at whether parallel and distributed computational experiments are more or less reproducible than serial ones. Third, we consider reproducible computational experiments from fields outside computer science. Our final case study looks at whether reproducibility for one researcher is the same as for another, by having an author attempt to have others reproduce their own, reproducible, paper. This paper is open, executable and reproducible: the whole process of writing this paper is captured in the source control repository hosting both the source of the paper, supplementary codes and data; we are providing setup for several experiments on which we were working; finally, we try to describe what we have achieved during the week of the school in a way that others may reproduce (and hopefully improve) our experiments.
The meshless method for solving radiative transfer problems in a slab medium based on radial basis functions
Venue: arXiv cs.NA 2014
Year: 2014

In this paper a numerical meshless method for solving the radiative transfer equations in a slab medium with an isotropic scattering is considered. The method is based on radial basis functions to approximate the solution of an integral-partial differential equation by using collocation method. For this purpose different applications of RBFs are used. To this end the numerical solutions are obtained without any mesh generation into the domain of the problems. The results of numerical experiments are compared with the existing results in illustrative examples to confirm the accuracy and efficiency of the presented scheme. Also the norm of the residual functions are obtained to show the convergence of the method.
It'll probably work out: improved list-decoding through random operations
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we introduce a framework to study the effect of random operations on the combinatorial list-decodability of a code. The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural transformations on codes, such as puncturing, folding, and taking subcodes; we show that many such operations can improve the list-decoding properties of a code. There are two main points to this. First, our goal is to advance our (combinatorial) understanding of list-decodability, by understanding what structure (or lack thereof) is necessary to obtain it. Second, we use our more general results to obtain a few interesting corollaries for list decoding: (1) We show the existence of binary codes that are combinatorially list-decodable from $1/2-ε$ fraction of errors with optimal rate $Ω(ε^2)$ that can be encoded in linear time. (2) We show that any code with $Ω(1)$ relative distance, when randomly folded, is combinatorially list-decodable $1-ε$ fraction of errors with high probability. This formalizes the intuition for why the folding operation has been successful in obtaining codes with optimal list decoding parameters; previously, all arguments used algebraic methods and worked only with specific codes. (3) We show that any code which is list-decodable with suboptimal list sizes has many subcodes which have near-optimal list sizes, while retaining the error correcting capabilities of the original code. This generalizes recent results where subspace evasive sets have been used to reduce list sizes of codes that achieve list decoding capacity.
SAT-Based Methods for Circuit Synthesis
Venue: arXiv cs.LO 2014
Year: 2014

Reactive synthesis supports designers by automatically constructing correct hardware from declarative specifications. Synthesis algorithms usually compute a strategy, and then construct a circuit that implements it. In this work, we study SAT- and QBF-based methods for the second step, i.e., computing circuits from strategies. This includes methods based on QBF-certification, interpolation, and computational learning. We present optimizations, efficient implementations, and experimental results for synthesis from safety specifications, where we outperform BDDs both regarding execution time and circuit size. This is an extended version of [2], with an additional appendix.
Notes on space complexity of integration of computable real functions in Ko-Friedman model
Venue: arXiv cs.CC 2014
Year: 2014

In the present paper it is shown that real function $g(x)=\int_{0}^{x}f(t)dt$ is a linear-space computable real function on interval $[0,1]$ if $f$ is a linear-space computable $C^2[0,1]$ real function on interval $[0,1]$, and this result does not depend on any open question in the computational complexity theory. The time complexity of computable real functions and integration of computable real functions is considered in the context of Ko-Friedman model which is based on the notion of Cauchy functions computable by Turing machines. In addition, a real computable function $f$ is given such that $\int_{0}^{1}f\in FDSPACE(n^2)_{C[a,b]}$ but $\int_{0}^{1}f\notin FP_{C[a,b]}$ if $FP\ne#P$.
Optimizing Component Combination in a Multi-Indexing Paragraph Retrieval System
Venue: arXiv cs.IR 2014
Year: 2014

We demonstrate a method to optimize the combination of distinct components in a paragraph retrieval system. Our system makes use of several indices, query generators and filters, each of them potentially contributing to the quality of the returned list of results. The components are combined with a weighed sum, and we optimize the weights using a heuristic optimization algorithm. This allows us to maximize the quality of our results, but also to determine which components are most valuable in our system. We evaluate our approach on the paragraph selection task of a Question Answering dataset.
Representing Dataset Quality Metadata using Multi-Dimensional Views
Venue: arXiv cs.DB 2014
Year: 2014

Data quality is commonly defined as fitness for use. The problem of identifying quality of data is faced by many data consumers. Data publishers often do not have the means to identify quality problems in their data. To make the task for both stakeholders easier, we have developed the Dataset Quality Ontology (daQ). daQ is a core vocabulary for representing the results of quality benchmarking of a linked dataset. It represents quality metadata as multi-dimensional and statistical observations using the Data Cube vocabulary. Quality metadata are organised as a self-contained graph, which can, e.g., be embedded into linked open datasets. We discuss the design considerations, give examples for extending daQ by custom quality metrics, and present use cases such as analysing data versions, browsing datasets by quality, and link identification. We finally discuss how data cube visualisation tools enable data publishers and consumers to analyse better the quality of their data.
Learning to see like children: proof of concept
Venue: arXiv cs.CV 2014
Year: 2014

In the last few years we have seen a growing interest in machine learning approaches to computer vision and, especially, to semantic labeling. Nowadays state of the art systems use deep learning on millions of labeled images with very successful results on benchmarks, though it is unlikely to expect similar results in unrestricted visual environments. Most learning schemes essentially ignore the inherent sequential structure of videos: this might be a critical issue, since any visual recognition process is remarkably more complex when shuffling video frames. Based on this remark, we propose a re-foundation of the communication protocol between visual agents and the environment, which is referred to as learning to see like children. Like for human interaction, visual concepts are acquired by the agents solely by processing their own visual stream along with human supervisions on selected pixels. We give a proof of concept that remarkable semantic labeling can emerge within this protocol by using only a few supervised examples. This is made possible by exploiting a constraint of motion coherent labeling that virtually offers tons of supervisions. Additional visual constraints, including those associated with object supervisions, are used within the context of learning from constraints. The framework is extended in the direction of lifelong learning, so as our visual agents live in their own visual environment without distinguishing learning and test set. Learning takes place in deep architectures under a progressive developmental scheme. In order to evaluate our Developmental Visual Agents (DVAs), in addition to classic benchmarks, we open the doors of our lab, allowing people to evaluate DVAs by crowd-sourcing. Such assessment mechanism might result in a paradigm shift in methodologies and algorithms for computer vision, encouraging truly novel solutions within the proposed framework.
Increasing-Chord Graphs On Point Sets
Venue: arXiv cs.CG 2014
Year: 2014

We tackle the problem of constructing increasing-chord graphs spanning point sets. We prove that, for every point set P with n points, there exists an increasing-chord planar graph with O(n) Steiner points spanning P. Further, we prove that, for every convex point set P with n points, there exists an increasing-chord graph with O(n log n) edges (and with no Steiner points) spanning P.
What Java Developers Know About Compatibility, And Why This Matters
Venue: arXiv cs.SE 2014
Year: 2014

Real-world programs are neither monolithic nor static -- they are constructed using platform and third party libraries, and both programs and libraries continuously evolve in response to change pressure. In case of the Java language, rules defined in the Java Language and Java Virtual Machine Specifications define when library evolution is safe. These rules distinguish between three types of compatibility - binary, source and behavioural. We claim that some of these rules are counter intuitive and not well-understood by many developers. We present the results of a survey where we quizzed developers about their understanding of the various types of compatibility. 414 developers responded to our survey. We find that while most programmers are familiar with the rules of source compatibility, they generally lack knowledge about the rules of binary and behavioural compatibility. This can be problematic when organisations switch from integration builds to technologies that require dynamic linking, such as OSGi. We have assessed the gravity of the problem by studying how often linkage-related problems are referenced in issue tracking systems, and find that they are common.
Performance Comparison of LDPC Block and Spatially Coupled Codes over GF(q)
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we compare the finite-length performance of protograph-based spatially coupled low-density parity-check (SC-LDPC) codes and LDPC block codes (LDPC-BCs) over GF(q). In order to reduce computational complexity and latency, a sliding window decoder with a stopping rule based on a soft bit-error-rate (BER) estimate is used for the q-ary SC-LDPC codes. Two regimes are considered: one when the constraint length of q-ary SC-LDPC codes is equal to the block length of q-ary LDPC-BCs and the other when the two decoding latencies are equal. Simulation results confirm that, in both regimes, (3,6)-, (3,9)-, and (3,12)-regular non-binary SC-LDPC codes can significantly outperform both binary and non-binary LDPC-BCs and binary SC-LDPC codes. Finally, we present a computational complexity comparison of q-ary SC-LDPC codes and q-ary LDPC-BCs under equal decoding latency and equal decoding performance assumptions.
A Study of Network Based Mobility Management Schemes, 6LoWPAN Mobility, Open Issues and Proposed Solutions
Venue: arXiv cs.NI 2014
Year: 2014

Wireless Sensor Nodes (SNs), the key elements for building Internet of Things (IOT), have been deployed widely in order to get and transmit information over the internet. With the introduction of IPv6 over Low Power Wireless Personal Area Network (6LoWPAN), it is possible to connect these constrained devices to IPv6 Networks and transmit IPv6 packets. The sensor nodes are being deployed/installed on many objects and some of them are mobile (moving) including mobile gadgets, physical objects (living or non-living) etc. These mobile objects require sufficient Mobility Management Schemes to take care of data transmission. Host based mobility protocols; MIPv6 and its extensions are not suitable for these resource constrained devices. In this paper our focus is to study PMIPv6 based mobility management and different Scenarios based on it along with sensor devices. Existing research has made many improvements in terms of HO latency but less attention has paid towards signaling cost and packet loss particularly in time critical areas. The study provides the complete survey of network based mobility management schemes, 6LoWPAN mobility, challenges associated with them and solutions to meet these challenges.
A Probabilistic MAC for Cognitive Radio Systems with Energy Harvesting Nodes
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we consider a cognitive radio (CR) system where the secondary user (SU) harvests energy from both the nature resources and the primary user (PU) radio frequency(RF) signal. We propose an energy-based probabilistic access scheme in which SU probabilistically accesses and senses the primary channel. The decision is based on the available energy and the PU's activity. We investigate the problem of maximizing the SU's success rate provided that the PU average quality of service (QoS) constraint is satisfied. We also assume multi-packet reception (MPR) capability and sensing errors under a Rayleigh fading channel. Numerical results show the effectiveness of the proposed probabilistic access scheme.
A Comprehensive Study of the GeoPass User Authentication Scheme
Venue: arXiv cs.HC 2014
Year: 2014

Before deploying a new user authentication scheme, it is critical to subject the scheme to comprehensive study. Few works, however, have undertaken such a study. Recently, Thorpe et al. proposed GeoPass, the most promising of a class of user authentication schemes based on geographic locations in online maps. Their study showed very high memorability (97%) and satisfactory resilience against online guessing, which means that GeoPass has compelling features for real-world use. No comprehensive study, however, has been conducted for GeoPass or any other location-based password scheme. In this paper, we present a systematic approach for the detailed evaluation of a password system, which we implement to study GeoPass. We conducted three separate studies to evaluate the suitability of GeoPass for widespread use. First, we performed a field study over two months, in which users in a real-world setting remembered their location-passwords 96% of the time and showed improvement with more login sessions. Second, we conducted a study to test how users would fare with multiple location-passwords and found that users remembered their location-passwords in less than 70% of login sessions, with 40% of login failures due to interference effects. Third, we conducted a study to examine the resilience of GeoPass against shoulder surfing. Our participants played the role of attackers and had an overall success rate of 48%. Based on our results, we suggest suitable applications of GeoPass in its current state and identify aspects of GeoPass that must be improved before widespread deployment could be considered.
A Classifier-free Ensemble Selection Method based on Data Diversity in Random Subspaces
Venue: arXiv cs.LG 2014
Year: 2014

The Ensemble of Classifiers (EoC) has been shown to be effective in improving the performance of single classifiers by combining their outputs, and one of the most important properties involved in the selection of the best EoC from a pool of classifiers is considered to be classifier diversity. In general, classifier diversity does not occur randomly, but is generated systematically by various ensemble creation methods. By using diverse data subsets to train classifiers, these methods can create diverse classifiers for the EoC. In this work, we propose a scheme to measure data diversity directly from random subspaces, and explore the possibility of using it to select the best data subsets for the construction of the EoC. Our scheme is the first ensemble selection method to be presented in the literature based on the concept of data diversity. Its main advantage over the traditional framework (ensemble creation then selection) is that it obviates the need for classifier training prior to ensemble selection. A single Genetic Algorithm (GA) and a Multi-Objective Genetic Algorithm (MOGA) were evaluated to search for the best solutions for the classifier-free ensemble selection. In both cases, objective functions based on different clustering diversity measures were implemented and tested. All the results obtained with the proposed classifier-free ensemble selection method were compared with the traditional classifier-based ensemble selection using Mean Classifier Error (ME) and Majority Voting Error (MVE). The applicability of the method is tested on UCI machine learning problems and NIST SD19 handwritten numerals.
Robust OS-ELM with a novel selective ensemble based on particle swarm optimization
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, a robust online sequential extreme learning machine (ROS-ELM) is proposed. It is based on the original OS-ELM with an adaptive selective ensemble framework. Two novel insights are proposed in this paper. First, a novel selective ensemble algorithm referred to as particle swarm optimization selective ensemble (PSOSEN) is proposed. Noting that PSOSEN is a general selective ensemble method which is applicable to any learning algorithms, including batch learning and online learning. Second, an adaptive selective ensemble framework for online learning is designed to balance the robustness and complexity of the algorithm. Experiments for both regression and classification problems with UCI data sets are carried out. Comparisons between OS-ELM, simple ensemble OS-ELM (EOS-ELM) and the proposed ROS-ELM empirically show that ROS-ELM significantly improves the robustness and stability.
Towards a Robot Perception Specification Language
Venue: arXiv cs.RO 2014
Year: 2014

In this paper we present our work in progress towards a domain-specific language called Robot Perception Specification Language (RPSL). RSPL provide means to specify the expected result (task knowledge) of a Robot Perception Architecture in a declarative and framework-independent manner.
The New Approach on Fuzzy Decision Trees
Venue: arXiv cs.AI 2014
Year: 2014

Decision trees have been widely used in machine learning. However, due to some reasons, data collecting in real world contains a fuzzy and uncertain form. The decision tree should be able to handle such fuzzy data. This paper presents a method to construct fuzzy decision tree. It proposes a fuzzy decision tree induction method in iris flower data set, obtaining the entropy from the distance between an average value and a particular value. It also presents an experiment result that shows the accuracy compared to former ID3.
Distributed Graph Automata and Verification of Distributed Algorithms
Venue: arXiv cs.FL 2014
Year: 2014

Combining ideas from distributed algorithms and alternating automata, we introduce a new class of finite graph automata that recognize precisely the languages of finite graphs definable in monadic second-order logic. By restricting transitions to be nondeterministic or deterministic, we also obtain two strictly weaker variants of our automata for which the emptiness problem is decidable. As an application, we suggest how suitable graph automata might be useful in formal verification of distributed algorithms, using Floyd-Hoare logic.
Rank, select and access in grammar-compressed strings
Venue: arXiv cs.DS 2014
Year: 2014

Given a string $S$ of length $N$ on a fixed alphabet of $σ$ symbols, a grammar compressor produces a context-free grammar $G$ of size $n$ that generates $S$ and only $S$. In this paper we describe data structures to support the following operations on a grammar-compressed string: $\mbox{rank}_c(S,i)$ (return the number of occurrences of symbol $c$ before position $i$ in $S$); $\mbox{select}_c(S,i)$ (return the position of the $i$th occurrence of $c$ in $S$); and $\mbox{access}(S,i,j)$ (return substring $S[i,j]$). For rank and select we describe data structures of size $O(nσ\log N)$ bits that support the two operations in $O(\log N)$ time. We propose another structure that uses $O(nσ\log (N/n)(\log N)^{1+ε})$ bits and that supports the two queries in $O(\log N/\log\log N)$, where $ε>0$ is an arbitrary constant. To our knowledge, we are the first to study the asymptotic complexity of rank and select in the grammar-compressed setting, and we provide a hardness result showing that significantly improving the bounds we achieve would imply a major breakthrough on a hard graph-theoretical problem. Our main result for access is a method that requires $O(n\log N)$ bits of space and $O(\log N+m/\log_σN)$ time to extract $m=j-i+1$ consecutive symbols from $S$. Alternatively, we can achieve $O(\log N/\log\log N+m/\log_σN)$ query time using $O(n\log (N/n)(\log N)^{1+ε})$ bits of space. This matches a lower bound stated by Verbin and Yu for strings where $N$ is polynomially related to $n$.