OpenRaiser/Intern-Atlas huggingface dataset:
Covering Problems for Partial Words and for Indeterminate Strings
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of the alphabet that could be present at the corresponding position. We also consider covering partial words, which are a special case of indeterminate strings where each non-solid symbol is a don't care symbol. We prove that indeterminate string covering problem and partial word covering problem are NP-complete for binary alphabet and show that both problems are fixed-parameter tractable with respect to $k$, the number of non-solid symbols. For the indeterminate string covering problem we obtain a $2^{O(k \log k)} + n k^{O(1)}$-time algorithm. For the partial word covering problem we obtain a $2^{O(\sqrt{k}\log k)} + nk^{O(1)}$-time algorithm. We prove that, unless the Exponential Time Hypothesis is false, no $2^{o(\sqrt{k})} n^{O(1)}$-time solution exists for either problem, which shows that our algorithm for this case is close to optimal. We also present an algorithm for both problems which is feasible in practice.
An Automatic Seeded Region Growing for 2D Biomedical Image Segmentation
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, an automatic seeded region growing algorithm is proposed for cellular image segmentation. First, the regions of interest (ROIs) extracted from the preprocessed image. Second, the initial seeds are automatically selected based on ROIs extracted from the image. Third, the most reprehensive seeds are selected using a machine learning algorithm. Finally, the cellular image is segmented into regions where each region corresponds to a seed. The aim of the proposed is to automatically extract the Region of Interests (ROI) from the cellular images in terms of overcoming the explosion, under segmentation and over segmentation problems. Experimental results show that the proposed algorithm can improve the segmented image and the segmented results are less noisy as compared to some existing algorithms.
Representing Data by a Mixture of Activated Simplices
Venue: arXiv cs.CV 2014
Year: 2014

We present a new model which represents data as a mixture of simplices. Simplices are geometric structures that generalize triangles. We give a simple geometric understanding that allows us to learn a simplicial structure efficiently. Our method requires that the data are unit normalized (and thus lie on the unit sphere). We show that under this restriction, building a model with simplices amounts to constructing a convex hull inside the sphere whose boundary facets is close to the data. We call the boundary facets of the convex hull that are close to the data Activated Simplices. While the total number of bases used to build the simplices is a parameter of the model, the dimensions of the individual activated simplices are learned from the data. Simplices can have different dimensions, which facilitates modeling of inhomogeneous data sources. The simplicial structure is bounded --- this is appropriate for modeling data with constraints, such as human elbows can not bend more than 180 degrees. The simplices are easy to interpret and extremes within the data can be discovered among the vertices. The method provides good reconstruction and regularization. It supports good nearest neighbor classification and it allows realistic generative models to be constructed. It achieves state-of-the-art results on benchmark datasets, including 3D poses and digits.
In-vivo Network of Sensors and Actuators
Venue: arXiv cs.SY 2014
Year: 2014

An advanced system of sensors/actuators should allow the direct feedback of a sensed signal into an actuation, e.g., an action potential propagation through an axon or a special cell activity might be sensed and suppressed by an actuator through voltage stimulation or chemical delivery. Such a complex procedure of sensing and stimulation calls for direct communication among these sensors and actuators. In addition, minimizing the sensor/actuator to the size of a biological cell can enable the cell-level automatic therapy. For this objective, we propose such an approach to form a peer-to-peer network of \emph{in vivo} sensors/actuators (S/As) that can be deployed with or even inside biological cells. The S/As can communicate with each other via electromagnetic waves of optical frequencies. In comparison with the comparable techniques including the radio-frequency identification (RFID) and the wireless sensor network (WSN), this technique is well adapted for the cell-level sensing-actuating tasks considering the requirements on size, actuation speed, signal-collision avoidance, etc.
A survey of modern optical character recognition techniques
Venue: arXiv cs.CV 2014
Year: 2014

This report explores the latest advances in the field of digital document recognition. With the focus on printed document imagery, we discuss the major developments in optical character recognition (OCR) and document image enhancement/restoration in application to Latin and non-Latin scripts. In addition, we review and discuss the available technologies for hand-written document recognition. In this report, we also provide some company-accumulated benchmark results on available OCR engines.
Descriptor Ensemble: An Unsupervised Approach to Descriptor Fusion in the Homography Space
Venue: arXiv cs.CV 2014
Year: 2014

With the aim to improve the performance of feature matching, we present an unsupervised approach to fuse various local descriptors in the space of homographies. Inspired by the observation that the homographies of correct feature correspondences vary smoothly along the spatial domain, our approach stands on the unsupervised nature of feature matching, and can select a good descriptor for matching each feature point. Specifically, the homography space serves as the common domain, in which a correspondence obtained by any descriptor is considered as a point, for integrating various heterogeneous descriptors. Both geometric coherence and spatial continuity among correspondences are considered via computing their geodesic distances in the space. In this way, mutual verification across different descriptors is allowed, and correct correspondences will be highlighted with a high degree of consistency (i.e., short geodesic distances here). It follows that one-class SVM can be applied to identifying these correct correspondences, and boosts the performance of feature matching. The proposed approach is comprehensively compared with the state-of-the-art approaches, and evaluated on four benchmarks of image matching. The promising results manifest its effectiveness.
Scalable Hierarchical Scheduling for Malleable Parallel Jobs on Multiprocessor-based Systems
Venue: arXiv cs.DC 2014
Year: 2014

The proliferation of multi-core and multiprocessor-based computer systems has led to explosive development of parallel applications and hence the need for efficient schedulers. In this paper, we study hierarchical scheduling for malleable parallel jobs on multiprocessor-based systems, which appears in many distributed and multilayered computing environments. We propose a hierarchical scheduling algorithm, named AC-DS, that consists of a feedback-driven adaptive scheduler, a desire aggregation scheme and an efficient resource allocation policy. From theoretical perspective, we show that AC-DS has scalable performance regardless of the number of hierarchical levels. In particular, we prove that AC-DS achieves $O(1)$-competitiveness with respect to the overall completion time of the jobs, or the makespan. A detailed malleable job model is developed to experimentally evaluate the effectiveness of the proposed scheduling algorithm. The results verify the scalability of AC-DS and demonstrate that AC-DS outperforms other strategies for a wide range of parallel workloads.
A Canonical Representation of Data-Linear Visualization Algorithms
Venue: arXiv cs.GR 2014
Year: 2014

We introduce linear-state dataflows, a canonical model for a large set of visualization algorithms that we call data-linear visualizations. Our model defines a fixed dataflow architecture: partitioning and subpartitioning of input data, ordering, graphic primitives, and graphic attributes generation. Local variables and accumulators are specific concepts that extend the expressiveness of the dataflow to support features of visualization algorithms that require state handling. We first show the flexibility of our model: it enables the declarative construction of many common algorithms with just a few mappings. Furthermore, the model enables easy mixing of visual mappings, such as creating treemaps of histograms and 2D plots, plots of histograms... Finally, we introduce our model in a more formal way and present some of its important properties. We have implemented this model in a visualization framework built around the concept of linear-state dataflows.
Automatic video scene segmentation based on spatial-temporal clues and rhythm
Venue: arXiv cs.CV 2014
Year: 2014

With ever increasing computing power and data storage capacity, the potential for large digital video libraries is growing rapidly.However, the massive use of video for the moment is limited by its opaque characteristics. Indeed, a user who has to handle and retrieve sequentially needs too much time in order to find out segments of interest within a video. Therefore, providing an environment both convenient and efficient for video storing and retrieval, especially for content-based searching as this exists in traditional textbased database systems, has been the focus of recent and important efforts of a large research community In this paper, we propose a new automatic video scene segmentation method that explores two main video features; these are spatial-temporal relationship and rhythm of shots. The experimental evidence we obtained from a 80 minutevideo showed that our prototype provides very high accuracy for video segmentation.
An Important Corollary for the Fast Solution of Dynamic Maximal Clique Enumeration Problems
Venue: arXiv cs.DM 2014
Year: 2014

In this paper we modify an algorithm for updating a maximal clique enumeration after an edge insertion to provide an algorithm that runs in linear time with respect to the number of cliques containing one of the edge's endpoints, whereas existing algorithms take quadratic time.
Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes
Venue: arXiv cs.CR 2014
Year: 2014

MDS matrices allow to build optimal linear diffusion layers in block ciphers. However, MDS matrices cannot be sparse and usually have a large description, inducing costly software/hardware implementations. Recursive MDS matrices allow to solve this problem by focusing on MDS matrices that can be computed as a power of a simple companion matrix, thus having a compact description suitable even for constrained environ- ments. However, up to now, finding recursive MDS matrices required to perform an exhaustive search on families of companion matrices, thus limiting the size of MDS matrices one could look for. In this article we propose a new direct construction based on shortened BCH codes, al- lowing to efficiently construct such matrices for whatever parameters. Unfortunately, not all recursive MDS matrices can be obtained from BCH codes, and our algorithm is not always guaranteed to find the best matrices for a given set of parameters.
The topology of a discussion: the #occupy case
Venue: arXiv cs.SI 2014
Year: 2014

We analyse a large sample of the Twitter activity developed around the social movement 'Occupy Wall Street' to study the complex interactions between the human communication activity and the semantic content of a discussion. We use a network approach based on the analysis of the bipartite graph @Users-#Hashtags and of its projections: the 'semantic network', whose nodes are hashtags, and the 'users interest network', whose nodes are users In the first instance, we find out that discussion topics (#hashtags) present a high heterogeneity, with the distinct role of the communication hubs where most the 'opinion traffic' passes through. In the second case, the self-organization process of users activity leads to the emergence of two classes of communicators: the 'professionals' and the 'amateurs'. Moreover the network presents a strong community structure, based on the differentiation of the semantic topics, and a high level of structural robustness when a certain set of topics are censored and/or accounts are removed. Analysing the characteristics the @Users-#Hashtags network we can distinguish three phases of the discussion about the movement. Each phase corresponds to specific moment of the movement: from declaration of intent, organisation and development and the final phase of political reactions. Each phase is characterised by the presence of specific #hashtags in the discussion. Keywords: Twitter, Network analysis
A Survey of Software Engineering Practices in Turkey (extended version)
Venue: arXiv cs.SE 2014
Year: 2014

Context: Understanding the types of software engineering practices and techniques used in the industry is important. There is a wide spectrum in terms of the types and maturity of software engineering practices conducted in each software team and company. To characterize the type of software engineering practices conducted in software firms, a variety of surveys have been conducted in different countries and regions. Turkey has a vibrant software industry and it is important to characterize and understand the state of software engineering practices in this industry. Objective: Our objective is to characterize and grasp a high-level view on type of software engineering practices in the Turkish software industry. Among the software engineering practices that we have surveyed in this study are the followings: software requirements, design, development, testing, maintenance, configuration management, release planning and support practices. The current survey is the most comprehensive of its type ever conducted in the context of Turkish software industry. Method: To achieve the above objective, we systematically designed an online survey with 46 questions based on our past experience in the Canadian and Turkish contexts and using the Software Engineering Body of Knowledge (SWEBOK). 202 practicing software engineers from the Turkish software industry participated in the survey. We analyze and report in this paper the results of the questions. Whenever possible, we also compare the trends and results of our survey with the results of a similar 2010 survey conducted in the Canadian software industry.
Towards Interactive, Incremental Programming of ROS Nodes
Venue: arXiv cs.RO 2014
Year: 2014

Writing software for controlling robots is a complex task, usually demanding command of many programming languages and requiring significant experimentation. We believe that a bottom-up development process that complements traditional component- and MDSD-based approaches can facilitate experimentation. We propose the use of an internal DSL providing both a tool to interactively create ROS nodes and a behaviour-replacement mechanism to interactively reshape existing ROS nodes by wrapping the external interfaces (the publish/subscribe topics), dynamically controlled using the Python command line interface.
A Counter-Example to Karlin's Strong Conjecture for Fictitious Play
Venue: arXiv cs.GT 2014
Year: 2014

Fictitious play is a natural dynamic for equilibrium play in zero-sum games, proposed by [Brown 1949], and shown to converge by [Robinson 1951]. Samuel Karlin conjectured in 1959 that fictitious play converges at rate $O(1/\sqrt{t})$ with the number of steps $t$. We disprove this conjecture showing that, when the payoff matrix of the row player is the $n \times n$ identity matrix, fictitious play may converge with rate as slow as $Ω(t^{-1/n})$.
Similarity Group-by Operators for Multi-dimensional Relational Data
Venue: arXiv cs.DB 2014
Year: 2014

The SQL group-by operator plays an important role in summarizing and aggregating large datasets in a data analytic stack.While the standard group-by operator, which is based on equality, is useful in several applications, allowing similarity aware grouping provides a more realistic view on real-world data that could lead to better insights. The Similarity SQL-based Group-By operator (SGB, for short) extends the semantics of the standard SQL Group-by by grouping data with similar but not necessarily equal values. While existing similarity-based grouping operators efficiently materialize this approximate semantics, they primarily focus on one-dimensional attributes and treat multidimensional attributes independently. However, correlated attributes, such as in spatial data, are processed independently, and hence, groups in the multidimensional space are not detected properly. To address this problem, we introduce two new SGB operators for multidimensional data. The first operator is the clique (or distance-to-all) SGB, where all the tuples in a group are within some distance from each other. The second operator is the distance-to-any SGB, where a tuple belongs to a group if the tuple is within some distance from any other tuple in the group. We implement and test the new SGB operators and their algorithms inside PostgreSQL. The overhead introduced by these operators proves to be minimal and the execution times are comparable to those of the standard Group-by. The experimental study, based on TPC-H and a social check-in data, demonstrates that the proposed algorithms can achieve up to three orders of magnitude enhancement in performance over baseline methods developed to solve the same problem.
Learn Physics by Programming in Haskell
Venue: arXiv cs.CY 2014
Year: 2014

We describe a method for deepening a student's understanding of basic physics by asking the student to express physical ideas in a functional programming language. The method is implemented in a second-year course in computational physics at Lebanon Valley College. We argue that the structure of Newtonian mechanics is clarified by its expression in a language (Haskell) that supports higher-order functions, types, and type classes. In electromagnetic theory, the type signatures of functions that calculate electric and magnetic fields clearly express the functional dependency on the charge and current distributions that produce the fields. Many of the ideas in basic physics are well-captured by a type or a function.
Bricklayer: An Authentic Introduction to the Functional Programming Language SML
Venue: arXiv cs.CY 2014
Year: 2014

Functional programming languages are seen by many as instrumental to effectively utilizing the computational power of multi-core platforms. As a result, there is growing interest to introduce functional programming and functional thinking as early as possible within the computer science curriculum. Bricklayer is an API, written in SML, that provides a set of abstractions for creating LEGO artifacts which can be viewed using LEGO Digital Designer. The goal of Bricklayer is to create a problem space (i.e., a set of LEGO artifacts) that is accessible and engaging to programmers (especially novice programmers) while providing an authentic introduction to the functional programming language SML.
The rectilinear Steiner tree problem with given topology and length restrictions
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of embedding the Steiner points of a Steiner tree with given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. We want to minimize the total length of the tree. The problem can be formulated as a linear program and therefore it is solvable in polynomial time. In this paper we analyze the structure of feasible embeddings and give a combinatorial polynomial time algorithm for the problem. Our algorithm combines a dynamic programming approach and binary search and relies on the total unimodularity of a matrix appearing in a sub-problem.
Locally Scale-Invariant Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Convolutional Neural Networks (ConvNets) have shown excellent results on many visual classification tasks. With the exception of ImageNet, these datasets are carefully crafted such that objects are well-aligned at similar scales. Naturally, the feature learning problem gets more challenging as the amount of variation in the data increases, as the models have to learn to be invariant to certain changes in appearance. Recent results on the ImageNet dataset show that given enough data, ConvNets can learn such invariances producing very discriminative features [1]. But could we do more: use less parameters, less data, learn more discriminative features, if certain invariances were built into the learning process? In this paper we present a simple model that allows ConvNets to learn features in a locally scale-invariant manner without increasing the number of model parameters. We show on a modified MNIST dataset that when faced with scale variation, building in scale-invariance allows ConvNets to learn more discriminative features with reduced chances of over-fitting.
Measurement partitioning and observational equivalence in state estimation
Venue: arXiv cs.IT 2014
Year: 2014

This letter studies measurement partitioning and equivalence in state estimation based on graph-theoretic principles. We show that a set of critical measurements (required to ensure LTI state-space observability) can be further partitioned into two types:~$α$ and~$β$. This partitioning is driven by different graphical (or algebraic) methods used to define the corresponding measurements. Subsequently, we describe observational equivalence, i.e. given an~$α$ (or~$β$) measurement, say~$y_i$, what is the set of measurements equivalent to~$y_i$, such that only one measurement in this set is required to ensure observability? Since~$α$ and~$β$ measurements are cast using different algebraic and graphical characteristics, their equivalence sets are also derived using different algebraic and graph-theoretic principles. We illustrate the related concepts on an appropriate system digraph.
Shallow Packings in Geometry
Venue: arXiv cs.CG 2014
Year: 2014

We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let $\V$ be a finite set system defined over an $n$-point set $X$; we view $\V$ as a set of indicator vectors over the $n$-dimensional unit cube. A $δ$-separated set of $\V$ is a subcollection $\W$, s.t. the Hamming distance between each pair $\uu, \vv \in \W$ is greater than $δ$, where $δ> 0$ is an integer parameter. The $δ$-packing number is then defined as the cardinality of the largest $δ$-separated subcollection of $\V$. Haussler showed an asymptotically tight bound of $Θ((n/δ)^d)$ on the $δ$-packing number if $\V$ has VC-dimension (or \emph{primal shatter dimension}) $d$. We refine this bound for the scenario where, for any subset, $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$, the number of vectors of length at most $k$ in the restriction of $\V$ to $X'$ is only $O(m^{d_1} k^{d-d_1})$, for a fixed integer $d > 0$ and a real parameter $1 \le d_1 \le d$ (this generalizes the standard notion of \emph{bounded primal shatter dimension} when $d_1 = d$). In this case when $\V$ is "$k$-shallow" (all vector lengths are at most $k$), we show that its $δ$-packing number is $O(n^{d_1} k^{d-d_1}/δ^d)$, matching Haussler's bound for the special cases where $d_1=d$ or $k=n$. As an immediate consequence we conclude that set systems of halfspaces, balls, and parallel slabs defined over $n$ points in $d$-space admit better packing numbers when $k$ is smaller than $n$. Last but not least, we describe applications to (i) spanning trees of low total crossing number, and (ii) geometric discrepancy, based on previous work by the author.