OpenRaiser/Intern-Atlas huggingface dataset:
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
Venue: arXiv cs.CG 2015
Year: 2015

We consider the problem of finding minimum-link rectilinear paths in rectilinear polygonal domains in the plane. A path or a polygon is rectilinear if all its edges are axis-parallel. Given a set $\mathcal{P}$ of $h$ pairwise-disjoint rectilinear polygonal obstacles with a total of $n$ vertices in the plane, a minimum-link rectilinear path between two points is a rectilinear path that avoids all obstacles with the minimum number of edges. In this paper, we present a new algorithm for finding minimum-link rectilinear paths among $\mathcal{P}$. After the plane is triangulated, with respect to any source point $s$, our algorithm builds an $O(n)$-size data structure in $O(n+h\log h)$ time, such that given any query point $t$, the number of edges of a minimum-link rectilinear path from $s$ to $t$ can be computed in $O(\log n)$ time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithm computes such a data structure in $O(n\log n)$ time.
Maximum a Posteriori Estimation by Search in Probabilistic Programs
Venue: arXiv cs.AI 2015
Year: 2015

We introduce an approximate search algorithm for fast maximum a posteriori probability estimation in probabilistic programs, which we call Bayesian ascent Monte Carlo (BaMC). Probabilistic programs represent probabilistic models with varying number of mutually dependent finite, countable, and continuous random variables. BaMC is an anytime MAP search algorithm applicable to any combination of random variables and dependencies. We compare BaMC to other MAP estimation algorithms and show that BaMC is faster and more robust on a range of probabilistic models.
Spline Path Following for Redundant Mechanical Systems
Venue: arXiv cs.RO 2015
Year: 2015

Path following controllers make the output of a control system approach and traverse a pre-specified path with no apriori time parametrization. In this paper we present a method for path following control design applicable to framed curves generated by splines in the workspace of kinematically redundant mechanical systems. The class of admissible paths includes self-intersecting curves. Kinematic redundancies are resolved by designing controllers that solve a suitably defined constrained quadratic optimization problem. By employing partial feedback linearization, the proposed path following controllers have a clear physical meaning. The approach is experimentally verified on a 4-degree-of-freedom (4-DOF) manipulator with a combination of revolute and linear actuated links and significant model uncertainty.
Preventing SQL Injection attack using pattern matching algorithm
Venue: arXiv cs.DB 2015
Year: 2015

SQL injection attacks, a class of injection flaw in which specially crafted input strings leads to illegal queries to databases, are one of the topmost threats to web applications. A Number of research prototypes and commercial products that maintain the queries structure in web applications have been developed. But these techniques either fail to address the full scope of the problem or have limitations. Based on our observation that the injected string in a SQL injection attack is interpreted differently on different databases.Injection attack is a method that can inject any kind of malicious string or anomaly string on the original string. Pattern matching is a technique that can be used to identify or detect any anomaly packet from a sequential action. Most of the pattern based techniques are used static analysis and patterns are generated from the attacked statements. In this paper, we proposed a detection and prevention technique for preventing SQL Injection Attack using AhoCorasick pattern matching algorithm. In this paper, we proposed an overview of the architecture. In the initial stage evaluation, we consider some sample of standard attack patterns and it shows that the proposed algorithm is works well against the SQL Injection Attack.
An Active Learning Based Approach For Effective Video Annotation And Retrieval
Venue: arXiv cs.MM 2015
Year: 2015

Conventional multimedia annotation/retrieval systems such as Normalized Continuous Relevance Model (NormCRM) [16] require a fully labeled training data for a good performance. Active Learning, by determining an order for labeling the training data, allows for a good performance even before the training data is fully annotated. In this work we propose an active learning algorithm, which combines a novel measure of sample uncertainty with a novel clustering-based approach for determining sample density and diversity and integrate it with NormCRM. The clusters are also iteratively refined to ensure both feature and label-level agreement among samples. We show that our approach outperforms multiple baselines both on a recent, open character animation dataset and on the popular TRECVID corpus at both the tasks of annotation and text-based retrieval of videos.
On-Board Vision Processing For Small UAVs: Time to Rethink Strategy
Venue: arXiv cs.CV 2015
Year: 2015

The ultimate research goal for unmanned aerial vehicles (UAVs) is to facilitate autonomy of operation. Research in the last decade has highlighted the potential of vision sensing in this regard. Although vital for accomplishment of missions assigned to any type of unmanned aerial vehicles, vision sensing is more critical for small aerial vehicles due to lack of high precision inertial sensors. In addition, uncertainty of GPS signal in indoor and urban environments calls for more reliance on vision sensing for such small vehicles. With off-line processing does not offer an attractive option in terms of autonomy, these vehicles have been challenging platforms to implement vision processing onboard due to their strict payload capacity and power budget. The strict constraints drive the need for new vision processing architectures for small unmanned aerial vehicles. Recent research has shown encouraging results with FPGA based hardware architectures. This paper reviews the bottle necks involved in implementing vision processing on-board, advocates the potential of hardware based solutions to tackle strict constraints of small unmanned aerial vehicles and finally analyzes feasibility of ASICs, Structured ASICs and FPGAs for use on future systems.
Deterministic Symmetry Breaking in Ring Networks
Venue: arXiv cs.DC 2015
Year: 2015

We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronised rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that $n$ mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The {\em location discovery} task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to %information about distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem.
Learning Instructor Intervention from MOOC Forums: Early Results and Issues
Venue: arXiv cs.CY 2015
Year: 2015

With large student enrollment, MOOC instructors face the unique challenge in deciding when to intervene in forum discussions with their limited bandwidth. We study this problem of instructor intervention. Using a large sample of forum data culled from 61 courses, we design a binary classifier to predict whether an instructor should intervene in a discussion thread or not. By incorporating novel information about a forum's type into the classification process, we improve significantly over the previous state-of-the-art. We show how difficult this decision problem is in the real world by validating against indicative human judgment, and empirically show the problem's sensitivity to instructors' intervention preferences. We conclude this paper with our take on the future research issues in intervention.
Private Disclosure of Information in Health Tele-monitoring
Venue: arXiv cs.CR 2015
Year: 2015

We present a novel framework, called Private Disclosure of Information (PDI), which is aimed to prevent an adversary from inferring certain sensitive information about subjects using the data that they disclosed during communication with an intended recipient. We show cases where it is possible to achieve perfect privacy regardless of the adversary's auxiliary knowledge while preserving full utility of the information to the intended recipient and provide sufficient conditions for such cases. We also demonstrate the applicability of PDI on a real-world data set that simulates a health tele-monitoring scenario.
Toward Smart Power Grids: Communication Network Design for Power Grids Synchronization
Venue: arXiv cs.NE 2015
Year: 2015

In smart power grids, keeping the synchronicity of generators and the corresponding controls is of great importance. To do so, a simple model is employed in terms of swing equation to represent the interactions among dynamics of generators and feedback control. In case of having a communication network available, the control can be done based on the transmitted measurements by the communication network. The stability of system is denoted by the largest eigenvalue of the weighted sum of the Laplacian matrices of the communication infrastructure and power network. In this work, we use graph theory to model the communication network as a graph problem. Then, Ant Colony System (ACS) is employed for optimum design of above graph for synchronization of power grids. Performance evaluation of the proposed method for the 39-bus New England power system versus methods such as exhaustive search and Rayleigh quotient approximation indicates feasibility and effectiveness of our method for even large scale smart power grids.
Compressive Rate Estimation with Applications to Device-to-Device Communications
Venue: arXiv cs.IT 2015
Year: 2015

We develop a framework that we call compressive rate estimation. We assume that the composite channel gain matrix (i.e. the matrix of all channel gains between all network nodes) is compressible which means it can be approximated by a sparse or low rank representation. We develop and study a novel sensing and reconstruction protocol for the estimation of achievable rates. We develop a sensing protocol that exploits the superposition principle of the wireless channel and enables the receiving nodes to obtain non-adaptive random measurements of columns of the composite channel matrix. The random measurements are fed back to a central controller that decodes the composite channel gain matrix (or parts of it) and estimates individual user rates. We analyze the rate loss for a linear and a non-linear decoder and find the scaling laws according to the number of non-adaptive measurements. In particular if we consider a system with $N$ nodes and assume that each column of the composite channel matrix is $k$ sparse, our findings can be summarized as follows. For a certain class of non-linear decoders we show that if the number of pilot signals $M$ scales like $M \sim k \log(N/k)$, then the rate loss compared to perfect channel state information remains bounded. For a certain class of linear decoders we show that the rate loss compared to perfect channel state information scales like $1/\sqrt{M}$.
Succint greedy routing without metric on planar triangulations
Venue: arXiv cs.NI 2015
Year: 2015

Geographic routing is an appealing routing strategy that uses the location information of the nodes to route the data. This technique uses only local information of the communication graph topology and does not require computational effort to build routing table or equivalent data structures. A particularly efficient implementation of this paradigm is greedy routing, where along the data path the nodes forward the data to a neighboring node that is closer to the destination. The decreasing distance to the destination implies the success of the routing scheme. A related problem is to consider an abstract graph and decide whether there exists an embedding of the graph in a metric space, called a greedy embedding, such that greedy routing guarantees the delivery of the data. In the present paper, we use a metric-free definition of greedy path and we show that greedy routing is successful on planar triangulations without considering the existence of greedy embedding. Our algorithm rely entirely on the combinatorial description of the graph structure and the coordinate system requires O(log(n)) bits where n is the number of nodes in the graph. Previous works on greedy routing make use of the embedding to route the data. In particular, in our framework, it is known that there exists an embedding of planar triangulations such that greedy routing guarantees the delivery of data. The result presented in this article leads to the question whether the success of (any) greedy routing strategy is always coupled with the existence of a greedy embedding?
Fast Quasi-Threshold Editing
Venue: arXiv cs.DS 2015
Year: 2015

We introduce Quasi-Threshold Mover (QTM), an algorithm to solve the quasi-threshold (also called trivially perfect) graph editing problem with edge insertion and deletion. Given a graph it computes a quasi-threshold graph which is close in terms of edit count. This edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM is the first algorithm that is able to scale to large real-world graphs in practice. As a side result we further present a simple linear-time algorithm for the quasi-threshold recognition problem.
Compact CNN for Indexing Egocentric Videos
Venue: arXiv cs.CV 2015
Year: 2015

While egocentric video is becoming increasingly popular, browsing it is very difficult. In this paper we present a compact 3D Convolutional Neural Network (CNN) architecture for long-term activity recognition in egocentric videos. Recognizing long-term activities enables us to temporally segment (index) long and unstructured egocentric videos. Existing methods for this task are based on hand tuned features derived from visible objects, location of hands, as well as optical flow. Given a sparse optical flow volume as input, our CNN classifies the camera wearer's activity. We obtain classification accuracy of 89%, which outperforms the current state-of-the-art by 19%. Additional evaluation is performed on an extended egocentric video dataset, classifying twice the amount of categories than current state-of-the-art. Furthermore, our CNN is able to recognize whether a video is egocentric or not with 99.2% accuracy, up by 24% from current state-of-the-art. To better understand what the network actually learns, we propose a novel visualization of CNN kernels as flow fields.
An Improved DFT-based Channel Estimation for Mobile Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

Channel estimation is one of the most important parts in current mobile communication systems. Among the huge contributions in channel estimation studies, the discrete Fourier transform (DFT)-based channel estimation has attracted lots of interests since it can not only be easily implemented but also have acceptable performance in practical systems. In this paper, we propose an improved DFT-based channel estimation scheme that tries to clean the reference signals in the time domain before being used for interpolation using the estimated noise variance from reference signals on multiple orthogonal frequency division multiplexing (OFDM) symbols via the property of DFT. The proposed channel estimation scheme does not need any priori channel information. We validate the proposed channel estimation scheme in various channel models via simulations and comparison with conventional channel estimation schemes.
Stratification and enumeration of Boolean functions by canalizing depth
Venue: arXiv cs.DM 2015
Year: 2015

Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively picked off, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
Duplicate Detection with Efficient Language Models for Automatic Bibliographic Heterogeneous Data Integration
Venue: arXiv cs.DB 2015
Year: 2015

We present a new method to detect duplicates used to merge different bibliographic record corpora with the help of lexical and social information. As we show, a trivial key is not available to delete useless documents. Merging heteregeneous document databases to get a maximum of information can be of interest. In our case we try to build a document corpus about the TOR molecule so as to extract relationships with other gene components from PubMed and WebOfScience document databases. Our approach makes key fingerprints based on n-grams. We made two documents gold standards using this corpus to make an evaluation. Comparison with other well-known methods in deduplication gives best scores of recall (95\%) and precision (100\%).
Split-by-edges trees
Venue: arXiv cs.DS 2015
Year: 2015

A split-by-edges tree of a graph G on n vertices is a binary tree T where the root = V(G), every leaf is an independent set in G, and for every other node N in T with children L and R there is a pair of vertices {u, v} in N such that L = N - v, R = N - u, and uv is an edge in G. It follows from the definition that every maximal independent set in G is a leaf in T, and the maximum independent sets of G are the leaves closest to the root of T.
Public projects, Boolean functions and the borders of Border's theorem
Venue: arXiv cs.GT 2015
Year: 2015

Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border's theorem either restrict attention to relatively simple settings, or resort to approximation. This paper identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. We also identify a surprisingly tight connection between Myerson's optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.
An automated multiscale ensemble simulation approach for vascular blood flow
Venue: arXiv cs.DC 2015
Year: 2015

Cerebrovascular diseases such as brain aneurysms are a primary cause of adult disability. The flow dynamics in brain arteries, both during periods of rest and increased activity, are known to be a major factor in the risk of aneurysm formation and rupture. The precise relation is however still an open field of investigation. We present an automated ensemble simulation method for modelling cerebrovascular blood flow under a range of flow regimes. By automatically constructing and performing an ensemble of multiscale simulations, where we unidirectionally couple a 1D solver with a 3D lattice-Boltzmann code, we are able to model the blood flow in a patient artery over a range of flow regimes. We apply the method to a model of a middle cerebral artery, and find that this approach helps us to fine-tune our modelling techniques, and opens up new ways to investigate cerebrovascular flow properties.
Mapping Tasks to Interactions for Graph Exploration and Graph Editing on Interactive Surfaces
Venue: arXiv cs.HC 2015
Year: 2015

Graph exploration and editing are still mostly considered independently and systems to work with are not designed for todays interactive surfaces like smartphones, tablets or tabletops. When developing a system for those modern devices that supports both graph exploration and graph editing, it is necessary to 1) identify what basic tasks need to be supported, 2) what interactions can be used, and 3) how to map these tasks and interactions. This technical report provides a list of basic interaction tasks for graph exploration and editing as a result of an extensive system review. Moreover, different interaction modalities of interactive surfaces are reviewed according to their interaction vocabulary and further degrees of freedom that can be used to make interactions distinguishable are discussed. Beyond the scope of graph exploration and editing, we provide an approach for finding and evaluating a mapping from tasks to interactions, that is generally applicable. Thus, this work acts as a guideline for developing a system for graph exploration and editing that is specifically designed for interactive surfaces.
Comparative study of image registration techniques for bladder video-endoscopy
Venue: arXiv cs.CV 2015
Year: 2015

Bladder cancer is widely spread in the world. Many adequate diagnosis techniques exist. Video-endoscopy remains the standard clinical procedure for visual exploration of the bladder internal surface. However, video-endoscopy presents the limit that the imaged area for each image is about nearly 1cm2. And, lesions are, typically, spread over several images. The aim of this contribution is to assess the performance of two mosaicing algorithms leading to the construction of panoramic maps (one unique image) of bladder walls. The quantitative comparison study is performed on a set of real endoscopic exam data and on simulated data relative to bladder phantom.