OpenRaiser/Intern-Atlas huggingface dataset:
The Quasi cellular nets-based models of transport and logistic systems
Venue: arXiv cs.OH 2015
Year: 2015

There are many systems in different subjects such as industry, medicine, transport, social and others, can be discribed on their dynamic of flows. Nowadays models of flows consist of micro- and macro-models. In practice there is a problem of convertation from different levels of simulation. In the different articles author descriptes quasi cellular nets. Quasi cellular nets are new type of discrete structures without signature. It may be used for simulation instruments. This structures can simulate flows on micro- and macro levels on the single model structure. In this article described using quasi cellular nets in transport and logistics of open-cast mining.
War of 2050: a Battle for Information, Communications, and Computer Security
Venue: arXiv cs.CR 2015
Year: 2015

As envisioned in a recent future-casting workshop, warfare will continue to be transformed by advances in information technologies. In fact, information itself will become the decisive domain of warfare. Four developments will significantly change the nature of the battle. The first of these will be a proliferation of intelligent systems; the second, augmented humans; the third, the decisive battle for the information domain; and the fourth, the introduction of new, networked approaches to command and control. Each of these new capabilities possesses the same critical vulnerability - attacks on the information, communications and computers that will enable human-robot teams to make sense of the battlefield and act decisively. Hence, the largely unseen battle for information, communications and computer security will determine the extent to which adversaries will be able to function and succeed on the battlefield of 2050.
An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
Venue: arXiv cs.DS 2015
Year: 2015

We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as computational biology. We design a generic in-place framework that fits to solve both the exact and approximate $k$-mismatch SUS finding, using the minimum $2n$ memory words plus $n$ bytes space, where $n$ is the input string size. By using the in-place framework, we can find the exact and approximate $k$-mismatch SUS for every string position using a total of $O(n)$ and $O(n^2)$ time, respectively, regardless of the value of $k$. Our framework does not involve any compressed or succinct data structures and thus is practical and easy to implement.
Characterization and Complexity Results on Jumping Finite Automata
Venue: arXiv cs.FL 2015
Year: 2015

In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.
Efficient Edge Detection on Low-Cost FPGAs
Venue: arXiv cs.AR 2015
Year: 2015

Improving the efficiency of edge detection in embedded applications, such as UAV control, is critical for reducing system cost and power dissipation. Field programmable gate arrays (FPGA) are a good platform for making improvements because of their specialised internal structure. However, current FPGA edge detectors do not exploit this structure well. A new edge detection architecture is proposed that is better optimised for FPGAs. The basis of the architecture is the Sobel edge kernels that are shown to be the most suitable because of their separability and absence of multiplications. Edge intensities are calculated with a new 4:2 compressor that consists of two custom-designed 3:2 compressors. Addition speed is increased by breaking carry propagation chains with look-ahead logic. Testing of the design showed it gives a 28% increase in speed and 4.4% reduction in area over previous equivalent designs, which demonstrated that it will lower the cost of edge detection systems, dissipate less power and still maintain high-speed control.
Double Sparse Multi-Frame Image Super Resolution
Venue: arXiv cs.CV 2015
Year: 2015

A large number of image super resolution algorithms based on the sparse coding are proposed, and some algorithms realize the multi-frame super resolution. In multi-frame super resolution based on the sparse coding, both accurate image registration and sparse coding are required. Previous study on multi-frame super resolution based on sparse coding firstly apply block matching for image registration, followed by sparse coding to enhance the image resolution. In this paper, these two problems are solved by optimizing a single objective function. The results of numerical experiments support the effectiveness of the proposed approch.
Distributed Multi Class SVM for Large Data Sets
Venue: arXiv cs.DC 2015
Year: 2015

Data mining algorithms are originally designed by assuming the data is available at one centralized site.These algorithms also assume that the whole data is fit into main memory while running the algorithm. But in today's scenario the data has to be handled is distributed even geographically. Bringing the data into a centralized site is a bottleneck in terms of the bandwidth when compared with the size of the data. In this paper for multiclass SVM we propose an algorithm which builds a global SVM model by merging the local SVMs using a distributed approach(DSVM). And the global SVM will be communicated to each site and made it available for further classification. The experimental analysis has shown promising results with better accuracy when compared with both the centralized and ensemble method. The time complexity is also reduced drastically because of the parallel construction of local SVMs. The experiments are conducted by considering the data sets of size 100s to hundred of 100s which also addresses the issue of scalability.
Implicit Location Sharing Detection in Social Media from Short Turkish Text
Venue: arXiv cs.CY 2015
Year: 2015

Social media have become a significant venue for information sharing of live updates. Users of social media are producing and sharing large amount of personal data as a part of the live updates. A significant percentage of this data contains location information that can be used by other people for many purposes. Some of the social media users deliberately share their own location information with other social network users. However, a large number of social media users blindly or implicitly share their location without noticing it or its possible consequences. Implicit location sharing is investigated in the current paper. We perform a large scale study on implicit location sharing for one of the most popular social media platform, namely Twitter. After a careful study, we built a dataset of Turkish tweets and manually tagged them. Using machine learning techniques we built classifiers that are able to classify whether a given tweet contains implicit location sharing or not. The classifiers are shown to be very accurate and efficient. Moreover, the best classifier is employed as a browser add-on tool which warns the user whenever an implicit location sharing is predicted from to be released tweet. The paper provides the methodology and the technical analysis as well. Furthermore, it discusses how these techniques can be extended to different social network services and also to different languages.
TinyLFU: A Highly Efficient Cache Admission Policy
Venue: arXiv cs.OS 2015
Year: 2015

This paper proposes to use a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. Realizing this concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and light-weight as it builds upon Bloom filter theory. We study the properties of TinyLFU through simulations of both synthetic workloads as well as multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU eviction policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit-ratios than other state of the art replacement policies on these traces. It is the only scheme to obtain such good results on all traces.
Active Learning for Delineation of Curvilinear Structures
Venue: arXiv cs.CV 2015
Year: 2015

Many recent delineation techniques owe much of their increased effectiveness to path classification algorithms that make it possible to distinguish promising paths from others. The downside of this development is that they require annotated training data, which is tedious to produce. In this paper, we propose an Active Learning approach that considerably speeds up the annotation process. Unlike standard ones, it takes advantage of the specificities of the delineation problem. It operates on a graph and can reduce the training set size by up to 80% without compromising the reconstruction quality. We will show that our approach outperforms conventional ones on various biomedical and natural image datasets, thus showing that it is broadly applicable.
Dipole Codes Attractively Encode Glue Functions
Venue: arXiv cs.FL 2015
Year: 2015

Dipole words are sequences of magnetic dipoles, in which alike elements repel and opposite elements attract. Magnetic dipoles contrast with more general sets of bonding types, called glues, in which pairwise bonding strength is specified by a glue function. We prove that every glue function $g$ has a set of dipole words, called a dipole code, that attractively encodes $g$: the pairwise attractions (positive or non-positive bond strength) between the words are identical to those of $g$. Moreover, we give such word sets of asymptotically optimal length. Similar results are obtained for a commonly used subclass of glue functions.
Fast Low-Rank Matrix Learning with Nonconvex Regularization
Venue: arXiv cs.NA 2015
Year: 2015

Low-rank modeling has a lot of important applications in machine learning, computer vision and social network analysis. While the matrix rank is often approximated by the convex nuclear norm, the use of nonconvex low-rank regularizers has demonstrated better recovery performance. However, the resultant optimization problem is much more challenging. A very recent state-of-the-art is based on the proximal gradient algorithm. However, it requires an expensive full SVD in each proximal step. In this paper, we show that for many commonly-used nonconvex low-rank regularizers, a cutoff can be derived to automatically threshold the singular values obtained from the proximal operator. This allows the use of power method to approximate the SVD efficiently. Besides, the proximal operator can be reduced to that of a much smaller matrix projected onto this leading subspace. Convergence, with a rate of O(1/T) where T is the number of iterations, can be guaranteed. Extensive experiments are performed on matrix completion and robust principal component analysis. The proposed method achieves significant speedup over the state-of-the-art. Moreover, the matrix solution obtained is more accurate and has a lower rank than that of the traditional nuclear norm regularizer.
Weighted Schatten $p$-Norm Minimization for Image Denoising and Background Subtraction
Venue: arXiv cs.CV 2015
Year: 2015

Low rank matrix approximation (LRMA), which aims to recover the underlying low rank matrix from its degraded observation, has a wide range of applications in computer vision. The latest LRMA methods resort to using the nuclear norm minimization (NNM) as a convex relaxation of the nonconvex rank minimization. However, NNM tends to over-shrink the rank components and treats the different rank components equally, limiting its flexibility in practical applications. We propose a more flexible model, namely the Weighted Schatten $p$-Norm Minimization (WSNM), to generalize the NNM to the Schatten $p$-norm minimization with weights assigned to different singular values. The proposed WSNM not only gives better approximation to the original low-rank assumption, but also considers the importance of different rank components. We analyze the solution of WSNM and prove that, under certain weights permutation, WSNM can be equivalently transformed into independent non-convex $l_p$-norm subproblems, whose global optimum can be efficiently solved by generalized iterated shrinkage algorithm. We apply WSNM to typical low-level vision problems, e.g., image denoising and background subtraction. Extensive experimental results show, both qualitatively and quantitatively, that the proposed WSNM can more effectively remove noise, and model complex and dynamic scenes compared with state-of-the-art methods.
Interactive audio-tactile maps for visually impaired people
Venue: arXiv cs.HC 2015
Year: 2015

Visually impaired people face important challenges related to orientation and mobility. Indeed, 56% of visually impaired people in France declared having problems concerning autonomous mobility. These problems often mean that visually impaired people travel less, which influences their personal and professional life and can lead to exclusion from society. Therefore this issue presents a social challenge as well as an important research area. Accessible geographic maps are helpful for acquiring knowledge about a city's or neighborhood's configuration, as well as selecting a route to reach a destination. Traditionally, raised-line paper maps with braille text have been used. These maps have proved to be efficient for the acquisition of spatial knowledge by visually impaired people. Yet, these maps possess significant limitations. For instance, due to the specificities of the tactile sense only a limited amount of information can be displayed on a single map, which dramatically increases the number of maps that are needed. For the same reason, it is difficult to represent specific information such as distances. Finally, braille labels are used for textual descriptions but only a small percentage of the visually impaired population reads braille. In France 15% of blind people are braille readers and only 10% can read and write. In the United States, fewer than 10% of the legally blind people are braille readers and only 10% of blind children actually learn braille. Recent technological advances have enabled the design of interactive maps with the aim to overcome these limitations. Indeed, interactive maps have the potential to provide a broad spectrum of the population with spatial knowledge, irrespective of age, impairment, skill level, or other factors. To this regard, they might be an efficient means for providing visually impaired people with access to geospatial information. In this paper we give an overview of our research on making geographic maps accessible to visually impaired people.
Spatially-coupled Split-component Codes with Iterative Algebraic Decoding
Venue: arXiv cs.IT 2015
Year: 2015

We analyze a class of high performance, low decoding-data-flow error-correcting codes suitable for high bit-rate optical-fiber communication systems. A spatially-coupled split-component ensemble is defined, generalizing from the most important codes of this class, staircase codes and braided block codes, and preserving a deterministic partitioning of component-code bits over code blocks. Our analysis focuses on low-complexity iterative algebraic decoding, which, for the binary erasure channel, is equivalent to a generalization of the peeling decoder. Using the differential equation method, we derive a vector recursion that tracks the expected residual graph evolution throughout the decoding process. The threshold of the recursion is found using potential function analysis. We generalize the analysis to mixture ensembles consisting of more than one type of component code, which provide increased flexibility of ensemble parameters and can improve performance. The analysis extends to the binary symmetric channel by assuming mis-correction-free component-code decoding. Simple upper-bounds on the number of errors correctable by the ensemble are derived. Finally, we analyze the threshold of spatially-coupled split-component ensembles under beyond bounded-distance component decoding.
A Smartphone-Based Acquisition System for Hips Rotation Fluency Assessment
Venue: arXiv cs.CY 2015
Year: 2015

The present contribution is motivated by recent studies on the assessment of the fluency of body movements during complex motor tasks. In particular, we focus on the estimation of the Cartesian kinematic jerk (namely, the derivative of the acceleration) of the hips' orientation during a full three-dimensional movement. The kinematic jerk index is estimated on the basis of gyroscopic signals acquired through a smartphone. A specific free mobile application available for the Android mobile operating system, HyperIMU, is used to acquire the gyroscopic signals and to transmit them to a personal computer via a User Datagram Protocol (UDP) through a wireless network. The personal computer elaborates the acquired data through a MATLAB script, either in real time or offline, and returns the kinematic jerk index associated to a motor task.
CrossCat: A Fully Bayesian Nonparametric Method for Analyzing Heterogeneous, High Dimensional Data
Venue: arXiv cs.AI 2015
Year: 2015

There is a widespread need for statistical methods that can analyze high-dimensional datasets with- out imposing restrictive or opaque modeling assumptions. This paper describes a domain-general data analysis method called CrossCat. CrossCat infers multiple non-overlapping views of the data, each consisting of a subset of the variables, and uses a separate nonparametric mixture to model each view. CrossCat is based on approximately Bayesian inference in a hierarchical, nonparamet- ric model for data tables. This model consists of a Dirichlet process mixture over the columns of a data table in which each mixture component is itself an independent Dirichlet process mixture over the rows; the inner mixture components are simple parametric models whose form depends on the types of data in the table. CrossCat combines strengths of mixture modeling and Bayesian net- work structure learning. Like mixture modeling, CrossCat can model a broad class of distributions by positing latent variables, and produces representations that can be efficiently conditioned and sampled from for prediction. Like Bayesian networks, CrossCat represents the dependencies and independencies between variables, and thus remains accurate when there are multiple statistical signals. Inference is done via a scalable Gibbs sampling scheme; this paper shows that it works well in practice. This paper also includes empirical results on heterogeneous tabular data of up to 10 million cells, such as hospital cost and quality measures, voting records, unemployment rates, gene expression measurements, and images of handwritten digits. CrossCat infers structure that is consistent with accepted findings and common-sense knowledge in multiple domains and yields predictive accuracy competitive with generative, discriminative, and model-free alternatives.
Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals $\mathcal{I}$ over $[0, n]$ with integer coordinates, supporting the following operations: - insert(a, b): add an interval $[a, b]$ to $\mathcal{I}$, provided that $a$ and $b$ are integers in $[0, n]$; - delete(a, b): delete a (previously inserted) interval $[a, b]$ from $\mathcal{I}$; - query(): return the total length of the union of all intervals in $\mathcal{I}$. It is related to the two-dimensional case of Klee's measure problem. We prove that there is a distribution over sequences of operations with $O(n)$ insertions and deletions, and $O(n^{0.01})$ queries, for which any data structure with any constant error probability requires $Ω(n\log n)$ time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson [ToC'07] to speed up a reduction from a new kind of nondeterministic communication games, for which we prove lower bounds. For applications, we prove lower bounds for several dynamic graph problems by reducing them from dynamic interval union.
Q-Networks for Binary Vector Actions
Venue: arXiv cs.NE 2015
Year: 2015

In this paper reinforcement learning with binary vector actions was investigated. We suggest an effective architecture of the neural networks for approximating an action-value function with binary vector actions. The proposed architecture approximates the action-value function by a linear function with respect to the action vector, but is still non-linear with respect to the state input. We show that this approximation method enables the efficient calculation of greedy action selection and softmax action selection. Using this architecture, we suggest an online algorithm based on Q-learning. The empirical results in the grid world and the blocker task suggest that our approximation architecture would be effective for the RL problems with large discrete action sets.
Using Google Ngram Viewer for Scientific Referencing and History of Science
Venue: arXiv cs.DL 2015
Year: 2015

Today, several universal digital libraries exist such as Google Books, Project Gutenberg, Internet Archive libraries, which possess texts from general collections, and many other archives are available, concerning more specific subjects. On the digitalized texts available from these libraries, we can perform several analyses, from those typically used for time-series to those of network theory. For what concerns time-series, an interesting tool provided by Google Books exists, which can help us in bibliographical and reference researches. This tool is the Ngram Viewer, based on yearly count of n-grams. As we will show in this paper, although it seems suitable just for literary works, it can be useful for scientific researches, not only for history of science, but also for acquiring references often unknown to researchers.
Flips in Edge-Labelled Pseudo-Triangulations
Venue: arXiv cs.CG 2015
Year: 2015

We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.