OpenRaiser/Intern-Atlas huggingface dataset:
Inverse, forward and other dynamic computations computationally optimized with sparse matrix factorizations
Venue: arXiv cs.RO 2017
Year: 2017

We propose an algorithm to compute the dynamics of articulated rigid-bodies with different sensor distributions. Prior to the on-line computations, the proposed algorithm performs an off-line optimisation step to simplify the computational complexity of the underlying solution. This optimisation step consists in formulating the dynamic computations as a system of linear equations. The computational complexity of computing the associated solution is reduced by performing a permuted LU-factorisation with off-line optimised permutations. We apply our algorithm to solve classical dynamic problems: inverse and forward dynamics. The computational complexity of the proposed solution is compared to `gold standard' algorithms: recursive Newton-Euler and articulated body algorithm. It is shown that our algorithm reduces the number of floating point operations with respect to previous approaches. We also evaluate the numerical complexity of our algorithm by performing tests on dynamic computations for which no gold standard is available.
KompicsTesting - Unit Testing Event Streams
Venue: arXiv cs.SE 2017
Year: 2017

In this paper we present KompicsTesting, a framework for unit testing components in the Kompics component model. Components in Kompics are event-driven entities which communicate asynchronously solely by message passing. Similar to actors in the actor model, they do not share their internal state in message-passing, making them less prone to errors, compared to other models of concurrency using shared state. However, they are neither immune to simpler logical and specification errors nor errors such as dataraces that stem from nondeterminism. As a result, there exists a need for tools that enable rapid and iterative development and testing of message passing components in general, in a manner similar to the xUnit frameworks for functions and modular segments code. These frameworks work in an imperative manner, ill suited for testing message-passing components given that the behavior of such components are encoded in the streams of messages that they send and receive. In this work, we present a theoretical framework for describing and verifying the behavior of message-passing components, independent of the model and framework implementation, in a manner similar to describing a stream of characters using regular expressions. We show how this approach can be used to perform both black box and white box testing of components and illustrate its feasibility through the design and implementation a prototype based on this approach, KompicsTesting.
Atypical Stable Multipath Routing Strategy in MANET
Venue: arXiv cs.NI 2017
Year: 2017

MANET is a collection of mobile nodes operated by battery source with limited energy reservoir. The dynamic topology and absence of pre-existing infrastructure in MANET makes routing technique more thought-provoking. The arbitrary movement of nodes may lead towards more packet drop, routing overhead and end-to-end delay. Moreover power deficiency in nodes affects the packet forwarding ability and thus reduces network lifetime. So a power aware stable routing strategy is in demand in MANET. In this manuscript we have proposed a novel multipath routing strategy that could select multiple stable routes between source and destination during data transmission depending on two factors residual energy and link expiration time (LET) of nodes. Our proposed energy aware stable multipath routing strategy could attain the reliability, load balancing, and bandwidth aggregation in order to increase the network lifetime.
Benchmark for Complex Answer Retrieval
Venue: arXiv cs.IR 2017
Year: 2017

Retrieving paragraphs to populate a Wikipedia article is a challenging task. The new TREC Complex Answer Retrieval (TREC CAR) track introduces a comprehensive dataset that targets this retrieval scenario. We present early results from a variety of approaches -- from standard information retrieval methods (e.g., tf-idf) to complex systems that using query expansion using knowledge bases and deep neural networks. The goal is to offer future participants of this track an overview of some promising approaches to tackle this problem.
Automatically Redundant Features Removal for Unsupervised Feature Selection via Sparse Feature Graph
Venue: arXiv cs.LG 2017
Year: 2017

The redundant features existing in high dimensional datasets always affect the performance of learning and mining algorithms. How to detect and remove them is an important research topic in machine learning and data mining research. In this paper, we propose a graph based approach to find and remove those redundant features automatically for high dimensional data. Based on the sparse learning based unsupervised feature selection framework, Sparse Feature Graph (SFG) is introduced not only to model the redundancy between two features, but also to disclose the group redundancy between two groups of features. With SFG, we can divide the whole features into different groups, and improve the intrinsic structure of data by removing detected redundant features. With accurate data structure, quality indicator vectors can be obtained to improve the learning performance of existing unsupervised feature selection algorithms such as multi-cluster feature selection (MCFS). Our experimental results on benchmark datasets show that the proposed SFG and feature redundancy remove algorithm can improve the performance of unsupervised feature selection algorithms consistently.
Extracting urban impervious surface from GF-1 imagery using one-class classifiers
Venue: arXiv cs.CV 2017
Year: 2017

Impervious surface area is a direct consequence of the urbanization, which also plays an important role in urban planning and environmental management. With the rapidly technical development of remote sensing, monitoring urban impervious surface via high spatial resolution (HSR) images has attracted unprecedented attention recently. Traditional multi-classes models are inefficient for impervious surface extraction because it requires labeling all needed and unneeded classes that occur in the image exhaustively. Therefore, we need to find a reliable one-class model to classify one specific land cover type without labeling other classes. In this study, we investigate several one-class classifiers, such as Presence and Background Learning (PBL), Positive Unlabeled Learning (PUL), OCSVM, BSVM and MAXENT, to extract urban impervious surface area using high spatial resolution imagery of GF-1, China's new generation of high spatial remote sensing satellite, and evaluate the classification accuracy based on artificial interpretation results. Compared to traditional multi-classes classifiers (ANN and SVM), the experimental results indicate that PBL and PUL provide higher classification accuracy, which is similar to the accuracy provided by ANN model. Meanwhile, PBL and PUL outperforms OCSVM, BSVM, MAXENT and SVM models. Hence, the one-class classifiers only need a small set of specific samples to train models without losing predictive accuracy, which is supposed to gain more attention on urban impervious surface extraction or other one specific land cover type.
Which Broadcast Abstraction Captures $k$-Set Agreement?
Venue: arXiv cs.DC 2017
Year: 2017

It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" $k$-set agreement? To this end, it introduces a new broadcast communication abstraction, called $k$-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast ($1$-BO-Broadcast boils down to total order broadcast). Hence, in this context, $k=1$ is not a special number, but only the first integer in an increasing integer sequence. This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.
Spatiotemporal Rate Adaptive Tiled Scheme for 360 Sports Events
Venue: arXiv cs.MM 2017
Year: 2017

The recent rise of interest in Virtual Reality (VR) came with the availability of commodity commercial VR products, such as the Head Mounted Displays (HMD) created by Oculus and other vendors. One of the main applications of virtual reality that has been recently adopted is streaming sports events. For instance, the last olympics held in Rio De Janeiro was streamed over the Internet for users to view on VR headsets or using 360 video players. A big challenge for streaming VR sports events is the users limited bandwidth and the amount of data required to transmit 360 videos. While 360 video demands high bandwidth, at any time instant users are only viewing a small portion of the video according to the HMD field of view (FOV). Many approaches have been proposed in the literature such as proposing new representations (e.g. pyramid and offset-cubemap) and tiling the video and streaming the tiles currently being viewed. In this paper, we propose a tiled streaming framework, where we provide a degrading quality model similar to the state-of-the-art offset-cubemap while minimizing its storage requirements at the server side. We conduct objective studies showing the effectiveness of our approach providing smooth degradation of quality from the user FOV to the back of the 360 space. In addition, we conduct subjective studies showing that users tend to prefer our proposed scheme over offset-cubemap in low bandwidth connections, and they don't feel difference for higher bandwidth connections. That is, we achieve better perceived quality with huge storage savings up to 670%.
Pricing and Revenue Sharing for Secondary Data Market
Venue: arXiv cs.NI 2017
Year: 2017

Recent advances in technology enable public or commercial establishments and individual data plan subscribers to operate as Wi-Fi providers, offering Internet access. However, the model of a monthly flat service fee charged by ISP to establishment or individual WFPs offers very little incentives for ISP to provide additional bandwidth to WFPs customers. Thus, these users may experience insufficient bandwidth when there is high demand for bandwidth. In addition, ISP even discourages individual subscribers to provide Internet access through their smartphone because such practices may cause market saturation. To address this, in this paper we propose a dynamic pricing scheme and a revenue sharing mechanism that provide incentives for ISP to support establishment and individual Wi-Fi providers offering Internet access to users. Our revenue sharing model is based on Shapley value mechanism. Importantly, our proposed revenue sharing mechanism captures the power negotiation between ISP and Wi-Fi providers, and how shifts in the power balance between the two entities influence revenue division. Specifically, the model assures that the party who contributes more receives a higher portion of the revenue. In addition to that, the division of revenue eventually converges to a percentage value.
Timing Model Extraction for Sequential Circuits Considering Process Variations
Venue: arXiv cs.AR 2017
Year: 2017

As semiconductor devices continue to scale down, process vari- ations become more relevant for circuit design. Facing such variations, statistical static timing analysis is introduced to model variations more accurately so that the pessimism in tra- ditional worst case timing analysis is reduced. Because all de- lays are modeled using correlated random variables, most statis- tical timing methods are much slower than corner based timing analysis. To speed up statistical timing analysis, we propose a method to extract timing models for flip-flop and latch based sequential circuits respectively. When such a circuit is used as a module in a hierarchical design, the timing model instead of the original circuit is used for timing analysis. The extracted timing models are much smaller than the original circuits. Ex- periments show that using extracted timing models accelerates timing verification by orders of magnitude compared to previ- ous approaches using flat netlists directly. Accuracy is main- tained, however, with the mean and standard deviation of the clock period both showing usually less than 1% error compared to Monte Carlo simulation on a number of benchmark circuits.
Statistical Timing Analysis for Latch-Controlled Circuits with Reduced Iterations and Graph Transformations
Venue: arXiv cs.OH 2017
Year: 2017

Level-sensitive latches are widely used in high- performance designs. For such circuits efficient statistical timing analysis algorithms are needed to take increasing process vari- ations into account. But existing methods solving this problem are still computationally expensive and can only provide the yield at a given clock period. In this paper we propose a method combining reduced iterations and graph transformations. The reduced iterations extract setup time constraints and identify a subgraph for the following graph transformations handling the constraints from nonpositive loops. The combined algorithms are very efficient, more than 10 times faster than other existing methods, and result in a parametric minimum clock period, which together with the hold time constraints can be used to compute the yield at any given clock period very easily.
ILP-based Alleviation of Dense Meander Segments with Prioritized Shifting and Progressive Fixing in PCB Routing
Venue: arXiv cs.AR 2017
Year: 2017

Length-matching is an important technique to bal- ance delays of bus signals in high-performance PCB routing. Existing routers, however, may generate very dense meander segments. Signals propagating along these meander segments exhibit a speedup effect due to crosstalk between the segments of the same wire, thus leading to mismatch of arrival times even under the same physical wire length. In this paper, we present a post-processing method to enlarge the width and the distance of meander segments and hence distribute them more evenly on the board so that crosstalk can be reduced. In the proposed framework, we model the sharing of available routing areas after removing dense meander segments from the initial routing, as well as the generation of relaxed meander segments and their groups for wire length compensation. This model is transformed into an ILP problem and solved for a balanced distribution of wire patterns. In addition, we adjust the locations of long wire segments according to wire priorities to swap free spaces toward critical wires that need much length compensation. To reduce the problem space of the ILP model, we also introduce a progressive fixing technique so that wire patterns are grown gradually from the edge of the routing toward the center area. Experimental results show that the proposed method can expand meander segments significantly even under very tight area constraints, so that the speedup effect can be alleviated effectively in high- performance PCB designs.
PieceTimer: A Holistic Timing Analysis Framework Considering Setup/Hold Time Interdependency Using A Piecewise Model
Venue: arXiv cs.AR 2017
Year: 2017

In static timing analysis, clock-to-q delays of flip-flops are considered as constants. Setup times and hold times are characterized separately and also used as constants. The characterized delays, setup times and hold times, are ap- plied in timing analysis independently to verify the perfor- mance of circuits. In reality, however, clock-to-q delays of flip-flops depend on both setup and hold times. Instead of being constants, these delays change with respect to different setup/hold time combinations. Consequently, the simple ab- straction of setup/hold times and constant clock-to-q delays introduces inaccuracy in timing analysis. In this paper, we propose a holistic method to consider the relation between clock-to-q delays and setup/hold time combinations with a piecewise linear model. The result is more accurate than that of traditional timing analysis, and the incorporation of the interdependency between clock-to-q delays, setup times and hold times may also improve circuit performance.
Testing Microfluidic Fully Programmable Valve Arrays (FPVAs)
Venue: arXiv cs.ET 2017
Year: 2017

Fully Programmable Valve Array (FPVA) has emerged as a new architecture for the next-generation flow-based microfluidic biochips. This 2D-array consists of regularly-arranged valves, which can be dynamically configured by users to realize microfluidic devices of different shapes and sizes as well as interconnections. Additionally, the regularity of the underlying structure renders FPVAs easier to integrate on a tiny chip. However, these arrays may suffer from various manufacturing defects such as blockage and leakage in control and flow channels. Unfortunately, no efficient method is yet known for testing such a general-purpose architecture. In this paper, we present a novel formulation using the concept of flow paths and cut-sets, and describe an ILP-based hierarchical strategy for generating compact test sets that can detect multiple faults in FPVAs. Simulation results demonstrate the efficacy of the proposed method in detecting manufacturing faults with only a small number of test vectors.
FLASH: A Faster Optimizer for SBSE Tasks
Venue: arXiv cs.SE 2017
Year: 2017

Most problems in search-based software engineering involve balancing conflicting objectives. Prior approaches to this task have required a large number of evaluations- making them very slow to execute and very hard to comprehend. To solve these problems, this paper introduces FLASH, a decision tree based optimizer that incrementally grows one decision tree per objective. These trees are then used to select the next best sample. This paper compares FLASH to state-of-the-art algorithms from search-based SE and machine learning. This comparison uses multiple SBSE case studies for release planning, configuration control, process modeling, and sprint planning for agile development. FLASH was found to be the fastest optimizer (sometimes requiring less than 1% of the evaluations used by evolutionary algorithms). Also, measured in terms of model size, FLASH's reasoning was far more succinct and comprehensible. Further, measured in terms of finding effective optimization, FLASH's recommendations were highly competitive with other approaches. Finally, FLASH scaled to more complex models since it always terminated (while state-of-the-art algorithm did not).
Capacity of Some Index Coding Problems with Symmetric Neighboring Interference
Venue: arXiv cs.IT 2017
Year: 2017

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has equal number of $K$ messages and $K$ receivers, the $k$th receiver $R_{k}$ wanting the $k$th message $x_{k}$ and having the side-information $\mathcal{K}_{k}=(\mathcal{I}_{k} \cup x_{k})^c,$ where ${I}_k= \{x_{k-U},\dots,x_{k-2},x_{k-1}\}\cup\{x_{k+1}, x_{k+2},\dots,x_{k+D}\}$ is the interference with $D$ messages after and $U$ messages before its desired message. Maleki, Cadambe and Jafar obtained the capacity of this symmetric neighboring interference single unicast index coding problem (SNI-SUICP) with $(K)$ tending to infinity and Blasiak, Kleinberg and Lubetzky for the special case of $(D=U=1)$ with $K$ being finite. In this work, for any finite $K$ and arbitrary $D$ we obtain the capacity for the case $U=gcd(K,D+1)-1.$ Our proof is constructive, i.e., we give an explicit construction of a linear index code achieving the capacity.
Single Image Super-Resolution Using Multi-Scale Convolutional Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

Methods based on convolutional neural network (CNN) have demonstrated tremendous improvements on single image super-resolution. However, the previous methods mainly restore images from one single area in the low resolution (LR) input, which limits the flexibility of models to infer various scales of details for high resolution (HR) output. Moreover, most of them train a specific model for each up-scale factor. In this paper, we propose a multi-scale super resolution (MSSR) network. Our network consists of multi-scale paths to make the HR inference, which can learn to synthesize features from different scales. This property helps reconstruct various kinds of regions in HR images. In addition, only one single model is needed for multiple up-scale factors, which is more efficient without loss of restoration quality. Experiments on four public datasets demonstrate that the proposed method achieved state-of-the-art performance with fast speed.
Learning Semantics for Image Annotation
Venue: arXiv cs.CV 2017
Year: 2017

Image search and retrieval engines rely heavily on textual annotation in order to match word queries to a set of candidate images. A system that can automatically annotate images with meaningful text can be highly beneficial for such engines. Currently, the approaches to develop such systems try to establish relationships between keywords and visual features of images. In this paper, We make three main contributions to this area: (i) We transform this problem from the low-level keyword space to the high-level semantics space that we refer to as the "{\em image theme}", (ii) Instead of treating each possible keyword independently, we use latent Dirichlet allocation to learn image themes from the associated texts in a training phase. Images are then annotated with image themes rather than keywords, using a modified continuous relevance model, which takes into account the spatial coherence and the visual continuity among images of common theme. (iii) To achieve more coherent annotations among images of common theme, we have integrated ConceptNet in learning the semantics of images, and hence augment image descriptions beyond annotations provided by humans. Images are thus further annotated by a few most significant words of the prominent image theme. Our extensive experiments show that a coherent theme-based image annotation using high-level semantics results in improved precision and recall as compared with equivalent classical keyword annotation systems.
Tuning Modular Networks with Weighted Losses for Hand-Eye Coordination
Venue: arXiv cs.RO 2017
Year: 2017

This paper introduces an end-to-end fine-tuning method to improve hand-eye coordination in modular deep visuo-motor policies (modular networks) where each module is trained independently. Benefiting from weighted losses, the fine-tuning method significantly improves the performance of the policies for a robotic planar reaching task.