OpenRaiser/Intern-Atlas huggingface dataset:
A General, Fast, and Robust Implementation of the Time-Optimal Path Parameterization Algorithm
Venue: arXiv cs.RO 2014
Year: 2014

Finding the Time-Optimal Parameterization of a given Path (TOPP) subject to kinodynamic constraints is an essential component in many robotic theories and applications. The objective of this article is to provide a general, fast and robust implementation of this component. For this, we give a complete solution to the issue of dynamic singularities, which are the main cause of failure in existing implementations. We then present an open-source implementation of the algorithm in C++/Python and demonstrate its robustness and speed in various robotics settings.
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
Venue: arXiv cs.DM 2014
Year: 2014

A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized parts. We prove that Bisection is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that Bisection does not admit polynomial-size kernels for these parameters. For the Vertex Bisection problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices k if the solution cuts the graph into a constant number c of connected components. The latter condition is unavoidable, since we also prove that Vertex Bisection is W[1]-hard w.r.t. (k,c). Our algorithms for finding bisections can easily be adapted to finding partitions into d equal-sized parts, which entails additional running time factors of n^{O(d)}. We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t. d, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.
Constrained Parametric Proposals and Pooling Methods for Semantic Segmentation in RGB-D Images
Venue: arXiv cs.CV 2014
Year: 2014

We focus on the problem of semantic segmentation based on RGB-D data, with emphasis on analyzing cluttered indoor scenes containing many instances from many visual categories. Our approach is based on a parametric figure-ground intensity and depth-constrained proposal process that generates spatial layout hypotheses at multiple locations and scales in the image followed by a sequential inference algorithm that integrates the proposals into a complete scene estimate. Our contributions can be summarized as proposing the following: (1) a generalization of parametric max flow figure-ground proposal methodology to take advantage of intensity and depth information, in order to systematically and efficiently generate the breakpoints of an underlying spatial model in polynomial time, (2) new region description methods based on second-order pooling over multiple features constructed using both intensity and depth channels, (3) an inference procedure that can resolve conflicts in overlapping spatial partitions, and handles scenes with a large number of objects category instances, of very different scales, (4) extensive evaluation of the impact of depth, as well as the effectiveness of a large number of descriptors, both pre-designed and automatically obtained using deep learning, in a difficult RGB-D semantic segmentation problem with 92 classes. We report state of the art results in the challenging NYU Depth v2 dataset, extended for RMRC 2013 Indoor Segmentation Challenge, where currently the proposed model ranks first, with an average score of 24.61% and a number of 39 classes won. Moreover, we show that by combining second-order and deep learning features, over 15% relative accuracy improvements can be additionally achieved. In a scene classification benchmark, our methodology further improves the state of the art by 24%.
Modeling Attractiveness and Multiple Clicks in Sponsored Search Results
Venue: arXiv cs.IR 2014
Year: 2014

Click models are an important tool for leveraging user feedback, and are used by commercial search engines for surfacing relevant search results. However, existing click models are lacking in two aspects. First, they do not share information across search results when computing attractiveness. Second, they assume that users interact with the search results sequentially. Based on our analysis of the click logs of a commercial search engine, we observe that the sequential scan assumption does not always hold, especially for sponsored search results. To overcome the above two limitations, we propose a new click model. Our key insight is that sharing information across search results helps in identifying important words or key-phrases which can then be used to accurately compute attractiveness of a search result. Furthermore, we argue that the click probability of a position as well as its attractiveness changes during a user session and depends on the user's past click experience. Our model seamlessly incorporates the effect of externalities (quality of other search results displayed in response to a user query), user fatigue, as well as pre and post-click relevance of a sponsored search result. We propose an efficient one-pass inference scheme and empirically evaluate the performance of our model via extensive experiments using the click logs of a large commercial search engine.
Learning without Concentration
Venue: arXiv cs.LG 2014
Year: 2014

We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used here relies on a `small-ball' assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets. The resulting estimates scale correctly with the `noise level' of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.
The impossibility of obfuscation with auxiliary input or a universal simulator
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we show that the existence of general indistinguishability obfuscators conjectured in a few recent works implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, we show that indistinguishability obfuscation for all circuits implies: * The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy. Such circuit families include all pseudo-random function families, and all families of encryption algorithms and randomized digital signatures that generate their required coin flips pseudo-randomly. Impossibility holds even when the auxiliary input depends only on the public circuit family, and not the specific circuit in the family being obfuscated. * The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (STOC 2005).
The effect of constraints on information loss and risk for clustering and modification based graph anonymization methods
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we present a novel approach for anonymizing Online Social Network graphs which can be used in conjunction with existing perturbation approaches such as clustering and modification. The main insight of this paper is that by imposing additional constraints on which nodes can be selected we can reduce the information loss with respect to key structural metrics, while maintaining an acceptable risk. We present and evaluate two constraints, 'local1' and 'local2' which select the most similar subgraphs within the same community while excluding some key structural nodes. To this end, we introduce a novel distance metric based on local subgraph characteristics and which is calibrated using an isomorphism matcher. Empirical testing is conducted with three real OSN datasets, six information loss measures, five adversary queries as risk measures, and different levels of k-anonymity. The results show that overall, the methods with constraints give the best results for information loss and risk of disclosure.
User-Generated Free-Form Gestures for Authentication: Security and Memorability
Venue: arXiv cs.CR 2014
Year: 2014

This paper studies the security and memorability of free-form multitouch gestures for mobile authentication. Towards this end, we collected a dataset with a generate-test-retest paradigm where participants (N=63) generated free-form gestures, repeated them, and were later retested for memory. Half of the participants decided to generate one-finger gestures, and the other half generated multi-finger gestures. Although there has been recent work on template-based gestures, there are yet no metrics to analyze security of either template or free-form gestures. For example, entropy-based metrics used for text-based passwords are not suitable for capturing the security and memorability of free-form gestures. Hence, we modify a recently proposed metric for analyzing information capacity of continuous full-body movements for this purpose. Our metric computed estimated mutual information in repeated sets of gestures. Surprisingly, one-finger gestures had higher average mutual information. Gestures with many hard angles and turns had the highest mutual information. The best-remembered gestures included signatures and simple angular shapes. We also implemented a multitouch recognizer to evaluate the practicality of free-form gestures in a real authentication system and how they perform against shoulder surfing attacks. We conclude the paper with strategies for generating secure and memorable free-form gestures, which present a robust method for mobile authentication.
An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2014
Year: 2014

A sufficient condition reported very recently for perfect recovery of a K-sparse vector via orthogonal matching pursuit (OMP) in K iterations is that the restricted isometry constant of the sensing matrix satisfies delta_K+1<1/(sqrt(delta_K+1)+1). By exploiting an approximate orthogonality condition characterized via the achievable angles between two orthogonal sparse vectors upon compression, this paper shows that the upper bound on delta can be further relaxed to delta_K+1<(sqrt(1+4*delta_K+1)-1)/(2K).This result thus narrows the gap between the so far best known bound and the ultimate performance guarantee delta_K+1<1/(sqrt(delta_K+1)) that is conjectured by Dai and Milenkovic in 2009. The proposed approximate orthogonality condition is also exploited to derive less restricted sufficient conditions for signal reconstruction in several compressive sensing problems, including signal recovery via OMP in a noisy environment, compressive domain interference cancellation, and support identification via the subspace pursuit algorithm.
Flight trajectory recreation and playback system of aerial mission based on ossimplanet
Venue: arXiv cs.HC 2014
Year: 2014

Recreation of flight trajectory is important among research areas. The design of a flight trajectory recreation and playback system is presented in this paper. Rather than transferring the flight data to diagram, graph and table, flight data is visualized on the 3D global of ossimPlanet. ossimPlanet is an open-source 3D global geo-spatial viewer and the system realization is based on analysis it. Users are allowed to choose their interested flight of aerial mission. The aerial photographs and corresponding configuration files in which flight data is included would be read in. And the flight statuses would be stored. The flight trajectory is then recreated. Users can view the photographs and flight trajectory marks on the correct positions of 3D global. The scene along flight trajectory is also simulated at the plane's eye point. This paper provides a more intuitive way for recreation of flight trajectory. The cost is decreased remarkably and security is ensured by secondary development on open-source platform.
A Framework for Creating a Distributed Rendering Environment on the Compute Clusters
Venue: arXiv cs.DC 2014
Year: 2014

This paper discusses the deployment of existing render farm manager in a typical compute cluster environment such as a university. Usually, both a render farm and a compute cluster use different queue managers and assume total control over the physical resources. But, taking out the physical resources from an existing compute cluster in a university-like environment whose primary use of the cluster is to run numerical simulations may not be possible. It can potentially reduce the overall resource utilization in a situation where compute tasks are more than rendering tasks. Moreover, it can increase the system administration cost. In this paper, a framework has been proposed that creates a dynamic distributed rendering environment on top of the compute clusters using existing render farm managers without requiring the physical separation of the resources.
Of course we share! Testing Assumptions about Social Tagging Systems
Venue: arXiv cs.IR 2014
Year: 2014

Social tagging systems have established themselves as an important part in today's web and have attracted the interest from our research community in a variety of investigations. The overall vision of our community is that simply through interactions with the system, i.e., through tagging and sharing of resources, users would contribute to building useful semantic structures as well as resource indexes using uncontrolled vocabulary not only due to the easy-to-use mechanics. Henceforth, a variety of assumptions about social tagging systems have emerged, yet testing them has been difficult due to the absence of suitable data. In this work we thoroughly investigate three available assumptions - e.g., is a tagging system really social? - by examining live log data gathered from the real-world public social tagging system BibSonomy. Our empirical results indicate that while some of these assumptions hold to a certain extent, other assumptions need to be reflected and viewed in a very critical light. Our observations have implications for the design of future search and other algorithms to better reflect the actual user behavior.
Data Smashing
Venue: arXiv cs.LG 2014
Year: 2014

Investigation of the underlying physics or biology from empirical data requires a quantifiable notion of similarity - when do two observed data sets indicate nearly identical generating processes, and when they do not. The discriminating characteristics to look for in data is often determined by heuristics designed by experts, $e.g.$, distinct shapes of "folded" lightcurves may be used as "features" to classify variable stars, while determination of pathological brain states might require a Fourier analysis of brainwave activity. Finding good features is non-trivial. Here, we propose a universal solution to this problem: we delineate a principle for quantifying similarity between sources of arbitrary data streams, without a priori knowledge, features or training. We uncover an algebraic structure on a space of symbolic models for quantized data, and show that such stochastic generators may be added and uniquely inverted; and that a model and its inverse always sum to the generator of flat white noise. Therefore, every data stream has an anti-stream: data generated by the inverse model. Similarity between two streams, then, is the degree to which one, when summed to the other's anti-stream, mutually annihilates all statistical structure to noise. We call this data smashing. We present diverse applications, including disambiguation of brainwaves pertaining to epileptic seizures, detection of anomalous cardiac rhythms, and classification of astronomical objects from raw photometry. In our examples, the data smashing principle, without access to any domain knowledge, meets or exceeds the performance of specialized algorithms tuned by domain experts.
An Interaction Model for Simulation and Mitigation of Cascading Failures
Venue: arXiv cs.SY 2014
Year: 2014

In this paper the interactions between component failures are quantified and the interaction matrix and interaction network are obtained. The quantified interactions can capture the general propagation patterns of the cascades from utilities or simulation, thus helping to better understand how cascading failures propagate and to identify key links and key components that are crucial for cascading failure propagation. By utilizing these interactions a high-level probabilistic model called interaction model is proposed to study the influence of interactions on cascading failure risk and to support online decision-making. It is much more time efficient to first quantify the interactions between component failures with fewer original cascades from a more detailed cascading failure model and then perform the interaction model simulation than it is to directly simulate a large number of cascades with a more detailed model. Interaction-based mitigation measures are suggested to mitigate cascading failure risk by weakening key links, which can be achieved in real systems by wide area protection such as blocking of some specific protective relays. The proposed interaction quantifying method and interaction model are validated with line outage data generated by the AC OPA cascading simulations on the IEEE 118-bus system.
Properties of phoneme N -grams across the world's language families
Venue: arXiv cs.CL 2014
Year: 2014

In this article, we investigate the properties of phoneme N-grams across half of the world's languages. We investigate if the sizes of three different N-gram distributions of the world's language families obey a power law. Further, the N-gram distributions of language families parallel the sizes of the families, which seem to obey a power law distribution. The correlation between N-gram distributions and language family sizes improves with increasing values of N. We applied statistical tests, originally given by physicists, to test the hypothesis of power law fit to twelve different datasets. The study also raises some new questions about the use of N-gram distributions in linguistic research, which we answer by running a statistical test.
Domain decomposition methods with overlapping subdomains for time-dependent problems
Venue: arXiv cs.NA 2014
Year: 2014

Domain decomposition (DD) methods for solving time-dependent problems can be classified by (i) the method of domain decomposition used, (ii) the choice of decomposition operators (exchange of boundary conditions), and (iii) the splitting scheme employed. To construct homogeneous numerical algorithms, overlapping subdomain methods are preferable. Domain decomposition is associated with the corresponding additive representation of the problem operator. To solve time-dependent problems with the DD splitting, different operator-splitting schemes are used. Various variants of decomposition operators differ by distinct types of data exchanges on interfaces. They ensure the convergence of the approximate solution in various spaces of grid functions.
A stochastic model for Case-Based Reasoning
Venue: arXiv cs.AI 2014
Year: 2014

Case-Bsed Reasoning (CBR) is a recent theory for problem-solving and learning in computers and people.Broadly construed it is the process of solving new problems based on the solution of similar past problems. In the present paper we introduce an absorbing Markov chain on the main steps of the CBR process.In this way we succeed in obtaining the probabilities for the above process to be in a certain step at a certain phase of the solution of the corresponding problem, and a measure for the efficiency of a CBR system. Examples are given to illustrate our results.
Selective Combining for Hybrid Cooperative Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this study, we consider the selective combining in hybrid cooperative networks (SCHCNs scheme) with one source node, one destination node and $N$ relay nodes. In the SCHCN scheme, each relay first adaptively chooses between amplify-and-forward protocol and decode-and-forward protocol on a per frame basis by examining the error-detecting code result, and $N_c$ ($1\leq N_c \leq N$) relays will be selected to forward their received signals to the destination. We first develop a signal-to-noise ratio (SNR) threshold-based frame error rate (FER) approximation model. Then, the theoretical FER expressions for the SCHCN scheme are derived by utilizing the proposed SNR threshold-based FER approximation model. The analytical FER expressions are validated through simulation results.
Antipodal Interval-Valued Fuzzy Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Concepts of graph theory have applications in many areas of computer science including data mining, image segmentation, clustering, image capturing, networks, etc . An interval-valued fuzzy set is a generalization of the notion of a fuzzy set. Interval-valued fuzzy models give more precision, flexibility and compatibility to the system as compared to the fuzzy models. In this paper, we introduce the concept of antipodal interval - valued fuzzy graph and self median interval-valued fuzzy graph of the given interval-valued fuzzy graph. We investigate isomorphism properties of antipodal interval - valued fuzzy graphs.
Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing
Venue: arXiv cs.IT 2014
Year: 2014

For the problem of binary linear classification and feature selection, we propose algorithmic approaches to classifier design based on the generalized approximate message passing (GAMP) algorithm, recently proposed in the context of compressive sensing. We are particularly motivated by problems where the number of features greatly exceeds the number of training examples, but where only a few features suffice for accurate classification. We show that sum-product GAMP can be used to (approximately) minimize the classification error rate and max-sum GAMP can be used to minimize a wide variety of regularized loss functions. Furthermore, we describe an expectation-maximization (EM)-based scheme to learn the associated model parameters online, as an alternative to cross-validation, and we show that GAMP's state-evolution framework can be used to accurately predict the misclassification rate. Finally, we present a detailed numerical study to confirm the accuracy, speed, and flexibility afforded by our GAMP-based approaches to binary linear classification and feature selection.