OpenRaiser/Intern-Atlas huggingface dataset:
Localizing and Orienting Street Views Using Overhead Imagery
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we aim to determine the location and orientation of a ground-level query image by matching to a reference database of overhead (e.g. satellite) images. For this task we collect a new dataset with one million pairs of street view and overhead images sampled from eleven U.S. cities. We explore several deep CNN architectures for cross-domain matching -- Classification, Hybrid, Siamese, and Triplet networks. Classification and Hybrid architectures are accurate but slow since they allow only partial feature precomputation. We propose a new loss function which significantly improves the accuracy of Siamese and Triplet embedding networks while maintaining their applicability to large-scale retrieval tasks like image geolocalization. This image matching task is challenging not just because of the dramatic viewpoint difference between ground-level and overhead imagery but because the orientation (i.e. azimuth) of the street views is unknown making correspondence even more difficult. We examine several mechanisms to match in spite of this -- training for rotation invariance, sampling possible rotations at query time, and explicitly predicting relative rotation of ground and overhead images with our deep networks. It turns out that explicit orientation supervision also improves location prediction accuracy. Our best performing architectures are roughly 2.5 times as accurate as the commonly used Siamese network baseline.
Data-Driven Background Subtraction Algorithm for in-Camera Acceleration in Thermal Imagery
Venue: arXiv cs.CV 2017
Year: 2017

Detection of moving objects in videos is a crucial step towards successful surveillance and monitoring applications. A key component for such tasks is called background subtraction and tries to extract regions of interest from the image background for further processing or action. For this reason, its accuracy and real-time performance is of great significance. Although, effective background subtraction methods have been proposed, only a few of them take into consideration the special characteristics of thermal imagery. In this work, we propose a background subtraction scheme, which models the thermal responses of each pixel as a mixture of Gaussians with unknown number of components. Following a Bayesian approach, our method automatically estimates the mixture structure, while simultaneously it avoids over/under fitting. The pixel density estimate is followed by an efficient and highly accurate updating mechanism, which permits our system to be automatically adapted to dynamically changing operation conditions. We propose a reference implementation of our method in reconfigurable hardware achieving both adequate performance and low power consumption. Adopting a High Level Synthesis design, demanding floating point arithmetic operations are mapped in reconfigurable hardware; demonstrating fast-prototyping and on-field customization at the same time.
The blockchain: a new framework for robotic swarm systems
Venue: arXiv cs.RO 2017
Year: 2017

Swarms of robots will revolutionize many industrial applications, from targeted material delivery to precision farming. However, several of the heterogeneous characteristics that make them ideal for certain future applications --- robot autonomy, decentralized control, collective emergent behavior, etc. --- hinder the evolution of the technology from academic institutions to real-world problems. Blockchain, an emerging technology originated in the Bitcoin field, demonstrates that by combining peer-to-peer networks with cryptographic algorithms a group of agents can reach an agreement on a particular state of affairs and record that agreement without the need for a controlling authority. The combination of blockchain with other distributed systems, such as robotic swarm systems, can provide the necessary capabilities to make robotic swarm operations more secure, autonomous, flexible and even profitable. This work explains how blockchain technology can provide innovative solutions to four emergent issues in the swarm robotics research field. New security, decision making, behavior differentiation and business models for swarm robotic systems are described by providing case scenarios and examples. Finally, limitations and possible future problems that arise from the combination of these two technologies are described.
Meraculous2: fast accurate short-read assembly of large polymorphic genomes
Venue: arXiv cs.DS 2017
Year: 2017

We present Meraculous2, an update to the Meraculous short-read assembler that includes (1) handling of allelic variation using "bubble" structures within the de Bruijn graph, (2) improved gap closing, and (3) an improved scaffolding algorithm that produces more complete assemblies without compromising scaffolding accuracy. The speed and bandwidth efficiency of the new parallel implementation have also been substantially improved, allowing the assembly of a human genome to be accomplished in 24 hours on the JGI/NERSC Genepool system. To highlight the features of Meraculous2 we present here the assembly of the diploid human genome NA12878, and compare it with previously published assemblies of the same data using other algorithms. The Meraculous2 assemblies are shown to have better completeness, contiguity, and accuracy than other published assemblies for these data. Practical considerations including pre-assembly analyses of polymorphism and repetitiveness are described.
FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning
Venue: arXiv cs.RO 2017
Year: 2017

Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce Extended Action Specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving \proc{strips} planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has finite expected runtime. Finally, we empirically demonstrate FFRob's effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.
Linear-time Kernelization for Feedback Vertex Set
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we propose an algorithm that, given an undirected graph $G$ of $m$ edges and an integer $k$, computes a graph $G'$ and an integer $k'$ in $O(k^4 m)$ time such that (1) the size of the graph $G'$ is $O(k^2)$, (2) $k'\leq k$, and (3) $G$ has a feedback vertex set of size at most $k$ if and only if $G'$ has a feedback vertex set of size at most $k'$. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is $2k^2+k$ vertices and $4k^2$ edges, which is smaller than the previous best of $4k^2$ vertices and $8k^2$ edges. Thus, we improve the size and the running time simultaneously. We note that under the assumption of $\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$, Feedback Vertex Set does not admit an $O(k^{2-ε})$-size kernel for any $ε>0$. Our kernel exploits $k$-submodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of $k$-submodular relaxation of Feedback Vertex Set can be seen as a half-integral variant of $A$-path packing, and to obtain the linear-time complexity, we propose an efficient augmenting-path algorithm for this problem. We believe that this combinatorial algorithm is of independent interest. A solver based on the proposed method won first place in the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge.
Dividing goods or bads under additive utilities
Venue: arXiv cs.GT 2017
Year: 2017

We compare the Egalitarian Equivalent and the Competitive Equilibrium with Equal Incomes rules to divide a bundle of goods (heirlooms) or a bundle of bads (chores). For goods the Competitive division fares better, as it is Resource Monotonic, and makes it harder to strategically misreport preferences. But for bads, the Competitive rule, unlike the Egalitarian one, is multivalued, harder to compute, and admits no continuous selection. We also provide an axiomatic characterization of the Competitive rule based on the simple formulation of Maskin Monotonicity under additive utilities.
Autonomous Take-Off and Flight of a Tethered Aircraft for Airborne Wind Energy
Venue: arXiv cs.SY 2017
Year: 2017

A control design approach to achieve fully autonomous take-off and flight maneuvers with a tethered aircraft is presented and demonstrated in real-world flight tests with a small-scale prototype. A ground station equipped with a controlled winch and a linear motion system accelerates the aircraft to take-off speed and controls the tether reeling in order to limit the pulling force. This setup corresponds to airborne wind energy systems with ground-based energy generation and rigid aircrafts. A simple model of the aircraft's dynamics is introduced and its parameters are identified from experimental data. A model-based, hierarchical feedback controller is then designed, whose aim is to manipulate the elevator, aileron and propeller inputs in order to stabilize the aircraft during the take-off and to achieve figure-of-eight flight patterns parallel to the ground. The controller operates in a fully decoupled mode with respect to the ground station. Parameter tuning and stability/robustness aspect are discussed, too. The experimental results indicate that the controller is able to achieve satisfactory performance and robustness, notwithstanding its simplicity, and confirm that the considered take-off approach is technically viable and solves the issue of launching this kind of airborne wind energy systems in a compact space and at low additional cost.
Bridging the Gap: Incorporating a Semantic Similarity Measure for Effectively Mapping PubMed Queries to Documents
Venue: arXiv cs.CL 2017
Year: 2017

The main approach of traditional information retrieval (IR) is to examine how many words from a query appear in a document. A drawback of this approach, however, is that it may fail to detect relevant documents where no or only few words from a query are found. The semantic analysis methods such as LSA (latent semantic analysis) and LDA (latent Dirichlet allocation) have been proposed to address the issue, but their performance is not superior compared to common IR approaches. Here we present a query-document similarity measure motivated by the Word Mover's Distance. Unlike other similarity measures, the proposed method relies on neural word embeddings to compute the distance between words. This process helps identify related words when no direct matches are found between a query and a document. Our method is efficient and straightforward to implement. The experimental results on TREC Genomics data show that our approach outperforms the BM25 ranking function by an average of 12% in mean average precision. Furthermore, for a real-world dataset collected from the PubMed search logs, we combine the semantic measure with BM25 using a learning to rank method, which leads to improved ranking scores by up to 25%. This experiment demonstrates that the proposed approach and BM25 nicely complement each other and together produce superior performance.
Identifying Designs from Incomplete, Fragmented Cultural Heritage Objects by Curve-Pattern Matching
Venue: arXiv cs.CV 2017
Year: 2017

Study of cultural-heritage objects with embellished realistic and abstract designs made up of connected and intertwined curves crosscuts a number of related disciplines, including archaeology, art history, and heritage management. However, many objects, such as pottery sherds found in the archaeological record, are fragmentary, making the underlying complete designs unknowable at the scale of the sherd fragment. The challenge to reconstruct and study complete designs is stymied because 1) most fragmentary cultural-heritage objects contain only a small portion of the underlying full design, 2) in the case of a stamping application, the same design may be applied multiple times with spatial overlap on one object, and 3) curve patterns detected on an object are usually incomplete and noisy. As a result, classical curve-pattern matching algorithms, such as Chamfer matching, may perform poorly in identifying the underlying design. In this paper, we develop a new partial-to-global curve matching algorithm to address these challenges and better identify the full design from a fragmented cultural heritage object. Specifically, we develop the algorithm to identify the designs of the carved wooden paddles of the Southeastern Woodlands from unearthed pottery sherds. A set of pottery sherds from the Snow Collection, curated at Georgia Southern University, are used to test the proposed algorithm, with promising results.
Boundary-based MWE segmentation with text partitioning
Venue: arXiv cs.CL 2017
Year: 2017

This work presents a fine-grained, text-chunking algorithm designed for the task of multiword expressions (MWEs) segmentation. As a lexical class, MWEs include a wide variety of idioms, whose automatic identification are a necessity for the handling of colloquial language. This algorithm's core novelty is its use of non-word tokens, i.e., boundaries, in a bottom-up strategy. Leveraging boundaries refines token-level information, forging high-level performance from relatively basic data. The generality of this model's feature space allows for its application across languages and domains. Experiments spanning 19 different languages exhibit a broadly-applicable, state-of-the-art model. Evaluation against recent shared-task data places text partitioning as the overall, best performing MWE segmentation algorithm, covering all MWE classes and multiple English domains (including user-generated text). This performance, coupled with a non-combinatorial, fast-running design, produces an ideal combination for implementations at scale, which are facilitated through the release of open-source software.
SELint: an SEAndroid policy analysis tool
Venue: arXiv cs.CR 2017
Year: 2017

SEAndroid enforcement is now mandatory for Android devices. In order to provide the desired level of security for their products, Android OEMs need to be able to minimize their mistakes in writing SEAndroid policies. However, existing SEAndroid and SELinux tools are not very useful for this purpose. It has been shown that SEAndroid policies found in commercially available devices for multiple manufacturers contain mistakes and redundancies. In this paper we present a new tool, SELint, which aims to help OEMs to produce better SEAndroid policies. SELint is extensible and configurable to suit the needs of different OEMs. It is provided with a default configuration based on the AOSP SEAndroid policy, but can be customized by OEMs.
Well Behaved Transition Systems
Venue: arXiv cs.LO 2017
Year: 2017

The well-quasi-ordering (i.e., a well-founded quasi-ordering such that all antichains are finite) that defines well-structured transition systems (WSTS) is shown not to be the weakest hypothesis that implies decidability of the coverability problem. We show coverability decidable for monotone transition systems that only require the absence of infinite antichains and call well behaved transitions systems (WBTS) the new strict superclass of the class of WSTS that arises. By contrast, we confirm that boundedness and termination are undecidable for WBTS under the usual hypotheses, and show that stronger monotonicity conditions can enforce decidability. Proofs are similar or even identical to existing proofs but the surprising message is that a hypothesis implicitely assumed minimal for twenty years in the theory of WSTS can meaningfully be relaxed, allowing more orderings to be handled in an abstract way.
First-Order Modular Logic Programs and their Conservative Extensions
Venue: arXiv cs.LO 2017
Year: 2017

Modular logic programs provide a way of viewing logic programs as consisting of many independent, meaningful modules. This paper introduces first-order modular logic programs, which can capture the meaning of many answer set programs. We also introduce conservative extensions of such programs. This concept helps to identify strong relationships between modular programs as well as between traditional programs. We show how the notion of a conservative extension can be used to justify the common projection rewriting. This note is under consideration for publication in Theory and Practice of Logic Programming.
Similarity Search on Automata Processors
Venue: arXiv cs.DC 2017
Year: 2017

Similarity search is a critical primitive for a wide variety of applications including natural language processing, content-based search, machine learning, computer vision, databases, robotics, and recommendation systems. At its core, similarity search is implemented using the k-nearest neighbors (kNN) algorithm, where computation consists of highly parallel distance calculations and a global top-k sort. In contemporary von-Neumann architectures, kNN is bottlenecked by data movement which limits throughput and latency. In this paper, we present and evaluate a novel automata-based algorithm for kNN on the Micron Automata Processor (AP), which is a non-von Neumann near-data processing architecture. By employing near-data processing, the AP minimizes the data movement bottleneck and is able to achieve better performance. Unlike prior work in the automata processing space, our work combines temporal encodings with automata design to augment the space of applications for the AP. We evaluate our design's performance on the AP and compare to state-of-the-art CPU, GPU, and FPGA implementations; we show that the current generation of AP hardware can achieve over 50x speedup over CPUs while maintaining competitive energy efficiency gains. We also propose several automata optimization techniques and simple architectural extensions that highlight the potential of the AP hardware.
Convexity in complex networks
Venue: arXiv cs.SI 2017
Year: 2017

Metric graph properties lie in the heart of the analysis of complex networks, while in this paper we study their convexity through mathematical definition of a convex subgraph. A subgraph is convex if every geodesic path between the nodes of the subgraph lies entirely within the subgraph. According to our perception of convexity, convex network is such in which every connected subset of nodes induces a convex subgraph. We show that convexity is an inherent property of many networks that is not present in a random graph. Most convex are spatial infrastructure networks and social collaboration graphs due to their tree-like or clique-like structure, whereas the food web is the only network studied that is truly non-convex. Core-periphery networks are regionally convex as they can be divided into a non-convex core surrounded by a convex periphery. Random graphs, however, are only locally convex meaning that any connected subgraph of size smaller than the average geodesic distance between the nodes is almost certainly convex. We present different measures of network convexity and discuss its applications in the study of networks.
Multi-View Product Image Search Using Deep ConvNets Representations
Venue: arXiv cs.CV 2017
Year: 2017

Multi-view product image queries can improve retrieval performance over single view queries significantly. In this paper, we investigated the performance of deep convolutional neural networks (ConvNets) on multi-view product image search. First, we trained a VGG-like network to learn deep ConvNets representations of product images. Then, we computed the deep ConvNets representations of database and query images and performed single view queries, and multi-view queries using several early and late fusion approaches. We performed extensive experiments on the publicly available Multi-View Object Image Dataset (MVOD 5K) with both clean background queries from the Internet and cluttered background queries from a mobile phone. We compared the performance of ConvNets to the classical bag-of-visual-words (BoWs). We concluded that (1) multi-view queries with deep ConvNets representations perform significantly better than single view queries, (2) ConvNets perform much better than BoWs and have room for further improvement, (3) pre-training of ConvNets on a different image dataset with background clutter is needed to obtain good performance on cluttered product image queries obtained with a mobile phone.
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Venue: arXiv cs.DS 2017
Year: 2017

[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the $c$-Approximate Near Neighbor Search problem. For the $d$-dimensional Euclidean space and $n$-point datasets, we develop a data structure with space $n^{1 + ρ_u + o(1)} + O(dn)$ and query time $n^{ρ_q + o(1)} + d n^{o(1)}$ for every $ρ_u, ρ_q \geq 0$ such that: \begin{equation} c^2 \sqrt{ρ_q} + (c^2 - 1) \sqrt{ρ_u} = \sqrt{2c^2 - 1}. \end{equation} This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor $c > 1$, improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for $ρ_q = 0$, improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.