OpenRaiser/Intern-Atlas huggingface dataset:
Heuristic Approaches for Generating Local Process Models through Log Projections
Venue: arXiv cs.LG 2016
Year: 2016

Local Process Model (LPM) discovery is focused on the mining of a set of process models where each model describes the behavior represented in the event log only partially, i.e. subsets of possible events are taken into account to create so-called local process models. Often such smaller models provide valuable insights into the behavior of the process, especially when no adequate and comprehensible single overall process model exists that is able to describe the traces of the process from start to end. The practical application of LPM discovery is however hindered by computational issues in the case of logs with many activities (problems may already occur when there are more than 17 unique activities). In this paper, we explore three heuristics to discover subsets of activities that lead to useful log projections with the goal of speeding up LPM discovery considerably while still finding high-quality LPMs. We found that a Markov clustering approach to create projection sets results in the largest improvement of execution time, with discovered LPMs still being better than with the use of randomly generated activity sets of the same size. Another heuristic, based on log entropy, yields a more moderate speedup, but enables the discovery of higher quality LPMs. The third heuristic, based on the relative information gain, shows unstable performance: for some data sets the speedup and LPM quality are higher than with the log entropy based method, while for other data sets there is no speedup at all.
Essential Properties of Numerical Integration for Time-optimal Trajectory Planning Along a Specified Path
Venue: arXiv cs.RO 2016
Year: 2016

This letter summarizes some known properties and also presents several new properties of the Numerical Integration (NI) method for time-optimal trajectory planning along a specified path. The contribution is that rigorous mathematical proofs of these properties are presented, most of which cannot be found in existing literatures. We first give some properties regarding switch points and accelerating/decelerating curves of the NI method. Then, for the fact that when kinematic constraints are considered, the original version of NI which only considers torque constraints may result in failure of trajectory planning, we give the concrete failure conditions with rigorous mathematical proof. Accordingly, a failure detection algorithm is given in a run-and-test manner. Some simulation results on a unicycle vehicle are provided to verify those presented properties. Note that though those known properties are not discovered first, their mathematical proofs are given first in this letter. The detailed proofs make the theory of NI more complete and help interested readers to gain a thorough understanding of the method.
A Novel Collaborative Cognitive Dynamic Network Architecture
Venue: arXiv cs.GT 2016
Year: 2016

Increasing mobile data demands in current cellular networks and proliferation of advanced handheld devices have given rise to a new generation of dynamic network architectures (DNAs). In a DNA, users share their connectivities and act as access points providing Internet connections for others without additional network infrastructure cost. A large number of users and their dynamic connections make DNA highly adaptive to variations in the network and suitable for low cost ubiquitous Internet connectivity. In this article, we propose a novel collaborative cognitive dynamic network architecture (CDNA) which incorporates cognitive capabilities to exploit underutilized spectrum in a more flexible and intelligent way. The design principles of CDNA are perfectly aligned to the functionality requirements of future 5G wireless networks such as energy and spectrum efficiency, scalability, dynamic reconfigurability, support for multi-hop communications, infrastructure sharing, and multi-operator cooperation. A case study with a new resource allocation problem enabled by CDNA is conducted using matching theory with pricing to illustrate the potential benefits of CDNA for users and operators, tackle user associations for data and spectrum trading with low complexity, and enable self-organizing capabilities. Finally, possible challenges and future research directions are given.
Multi-Message Broadcast in Dynamic Radio Networks
Venue: arXiv cs.DC 2016
Year: 2016

We continue the recent line of research studying information dissemination problems in adversarial dynamic radio networks. We give two generic algorithms which allow to transform generalized version of single-message broadcast algorithms into multi-message broadcast algorithms. Based on these generic algorithms, we obtain multi-message broadcast algorithms for dynamic radio networks for a number of different dynamic network settings. For one of the modeling assumptions, our algorithms are complemented by a lower bound which shows that the upper bound is close to optimal.
Quantifying moral foundations from various topics on Twitter conversations
Venue: arXiv cs.CY 2016
Year: 2016

Moral foundations theory explains variations in moral behavior using innate moral foundations: Care, Fairness, Ingroup, Authority, and Purity, along with experimental supports. However, little is known about the roles of and relationships between those foundations in everyday moral situations. To address these, we quantify moral foundations from a large amount of online conversations (tweets) about moral topics on the social media site Twitter. We measure moral loadings using latent semantic analysis of tweets related to topics on abortion, homosexuality, immigration, religion, and immorality in general, showing how the five moral foundations function in spontaneous conversations about moral violating situations. The results indicate that although the five foundations are mutually related, Purity is the most distinctive foundation and Care is the most dominant foundation in everyday conversations on immorality. Our study shows a new possibility of natural language processing and social big data for moral psychology.
Scalable Construction of Text Indexes
Venue: arXiv cs.DS 2016
Year: 2016

The suffix array is the key to efficient solutions for myriads of string processing problems in different applications domains, like data compression, data mining, or Bioinformatics. With the rapid growth of available data, suffix array construction algorithms had to be adapted to advanced computational models such as external memory and distributed computing. In this article, we present five suffix array construction algorithms utilizing the new algorithmic big data batch processing framework Thrill, which allows us to process input sizes in orders of magnitude that have not been considered before.
Learning Low Dimensional Convolutional Neural Networks for High-Resolution Remote Sensing Image Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

Learning powerful feature representations for image retrieval has always been a challenging task in the field of remote sensing. Traditional methods focus on extracting low-level hand-crafted features which are not only time-consuming but also tend to achieve unsatisfactory performance due to the content complexity of remote sensing images. In this paper, we investigate how to extract deep feature representations based on convolutional neural networks (CNN) for high-resolution remote sensing image retrieval (HRRSIR). To this end, two effective schemes are proposed to generate powerful feature representations for HRRSIR. In the first scheme, the deep features are extracted from the fully-connected and convolutional layers of the pre-trained CNN models, respectively; in the second scheme, we propose a novel CNN architecture based on conventional convolution layers and a three-layer perceptron. The novel CNN model is then trained on a large remote sensing dataset to learn low dimensional features. The two schemes are evaluated on several public and challenging datasets, and the results indicate that the proposed schemes and in particular the novel CNN are able to achieve state-of-the-art performance.
Lower bounds for CSP refutation by SDP hierarchies
Venue: arXiv cs.CC 2016
Year: 2016

For a $k$-ary predicate $P$, a random instance of CSP$(P)$ with $n$ variables and $m$ constraints is unsatisfiable with high probability when $m \gg n$. The natural algorithmic task in this regime is \emph{refutation}: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP$(P)$ using an SDP is determined by a parameter $\mathrm{cmplx}(P)$, the smallest $t$ for which there does not exist a $t$-wise uniform distribution over satisfying assignments to $P$. In particular they show that random instances of CSP$(P)$ with $m \gg n^{\mathrm{cmplx(P)}/2}$ can be refuted efficiently using an SDP. In this work, we give evidence that $n^{\mathrm{cmplx}(P)/2}$ constraints are also \emph{necessary} for refutation using SDPs. Specifically, we show that if $P$ supports a $(t-1)$-wise uniform distribution over satisfying assignments, then the Sherali-Adams$_+$ and Lovász-Schrijver$_+$ SDP hierarchies cannot refute a random instance of CSP$(P)$ in polynomial time for any $m \leq n^{t/2-ε}$.
Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
Venue: arXiv cs.LG 2016
Year: 2016

Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessian sketch is an optimization process with preconditioning, and develop accelerated iterative Hessian sketch via the searching the conjugate direction; we then establish primal-dual connections between the Hessian sketch and dual random projection, and apply the preconditioned conjugate gradient approach on the dual problem, which leads to the accelerated iterative dual random projection methods. Finally to tackle the challenges from both large sample size and high-dimensionality, we propose the primal-dual sketch, which iteratively sketches the primal and dual formulations. We show that using a logarithmic number of calls to solvers of small scale problem, primal-dual sketch is able to recover the optimum of the original problem up to arbitrary precision. The proposed algorithms are validated via extensive experiments on synthetic and real data sets which complements our theoretical results.
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
Venue: arXiv cs.DS 2016
Year: 2016

We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exactly using sublinear space is not possible in such a setting, one can still hope for a good approximation guarantee. Our contribution is twofold. First, we provide lower bounds on the space requirements for randomized approximation algorithms processing inputs of length $n$. We rule out Las Vegas algorithms, as they cannot achieve sublinear space complexity. For Monte Carlo algorithms, we prove a lower bounds of $Ω( M \log\min\{|Σ|,M\})$ bits of memory; here $M=n/E$ for approximating the answer with additive error $E$, and $M= \frac{\log n}{\log (1+\varepsilon)}$ for approximating the answer with multiplicative error $(1 + \varepsilon)$. Second, we design three real-time algorithms for this problem. Our Monte Carlo approximation algorithms for both additive and multiplicative versions of the problem use $O(M)$ words of memory. Thus the obtained lower bounds are asymptotically tight up to a logarithmic factor. The third algorithm is deterministic and finds a longest palindrome exactly if it is short. This algorithm can be run in parallel with a Monte Carlo algorithm to obtain better results in practice. Overall, both the time and space complexity of finding a longest palindrome in a stream are essentially settled.
Tangled Splines
Venue: arXiv cs.CV 2016
Year: 2016

Extracting shape information from object bound- aries is a well studied problem in vision, and has found tremen- dous use in applications like object recognition. Conversely, studying the space of shapes represented by curves satisfying certain constraints is also intriguing. In this paper, we model and analyze the space of shapes represented by a 3D curve (space curve) formed by connecting n pieces of quarter of a unit circle. Such a space curve is what we call a Tangle, the name coming from a toy built on the same principle. We provide two models for the shape space of n-link open and closed tangles, and we show that tangles are a subset of trigonometric splines of a certain order. We give algorithms for curve approximation using open/closed tangles, computing geodesics on these shape spaces, and to find the deformation that takes one given tangle to another given tangle, i.e., the Log map. The algorithms provided yield tangles upto a small and acceptable tolerance, as shown by the results given in the paper.
Model Driven Web Application Development With Agile Practices
Venue: arXiv cs.SE 2016
Year: 2016

Model driven development is an effective method due to its benefits such as code transformation, increasing productivity and reducing human based error possibilities. Meanwhile, agile software development increases the software flexibility and customer satisfaction by using iterative method. Can these two development approaches be combined to develop web applications efficiently? What are the challenges and what are the benefits of this approach? In this paper, we answer these two crucial problems; combining model driven development and agile software development results in not only fast development and easiness of the user interface design but also efficient job tracking. We also defined an agile model based approach for web applications whose implementation study has been carried out to support the answers we gave these two crucial problems.
Proposal for Automatic License and Number Plate Recognition System for Vehicle Identification
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose an automatic and mechanized license and number plate recognition (LNPR) system which can extract the license plate number of the vehicles passing through a given location using image processing algorithms. No additional devices such as GPS or radio frequency identification (RFID) need to be installed for implementing the proposed system. Using special cameras, the system takes pictures from each passing vehicle and forwards the image to the computer for being processed by the LPR software. Plate recognition software uses different algorithms such as localization, orientation, normalization, segmentation and finally optical character recognition (OCR). The resulting data is applied to compare with the records on a database. Experimental results reveal that the presented system successfully detects and recognizes the vehicle number plate on real images. This system can also be used for security and traffic control.
Implementing High-Order FIR Filters in FPGAs
Venue: arXiv cs.DC 2016
Year: 2016

Contemporary field-programmable gate arrays (FPGAs) are predestined for the application of finite impulse response (FIR) filters. Their embedded digital signal processing (DSP) blocks for multiply-accumulate operations enable efficient fixed-point computations, in cases where the filter structure is accurately mapped to the dedicated hardware architecture. This brief presents a generic systolic structure for high-order FIR filters, efficiently exploiting the hardware resources of an FPGA in terms of routability and timing. Although this seems to be an easily implementable task, the synthesizing tools require an adaptation of the straightforward digital filter implementation for an optimal mapping. Using the example of a symmetric FIR filter with 90 taps, we demonstrate the performance of the proposed structure with FPGAs from Xilinx and Altera. The implementation utilizes less than 1% of slice logic and runs at clock frequencies up to 526 MHz. Moreover, an enhancement of the structure ultimately provides an extended dynamic range for the quantized coefficients without the costs of additional slice logic.
Restoring STM images via Sparse Coding: noise and artifact removal
Venue: arXiv cs.CV 2016
Year: 2016

In this article, we present a denoising algorithm to improve the interpretation and quality of scanning tunneling microscopy (STM) images. Given the high level of self-similarity of STM images, we propose a denoising algorithm by reformulating the true estimation problem as a sparse regression, often termed sparse coding. We introduce modifications to the algorithm to cope with the existence of artifacts, mainly dropouts, which appear in a structured way as consecutive line segments on the scanning direction. The resulting algorithm treats the artifacts as missing data, and the estimated values outperform those algorithms that substitute the outliers by a local filtering. We provide code implementations for both Matlab and Gwyddion.
Multi-scale computational homogenisation to predict the long-term durability of composite structures
Venue: arXiv cs.CE 2016
Year: 2016

A coupled hygro-thermo-mechanical computational model is proposed for fibre reinforced polymers, formulated within the framework of Computational Homogenisation (CH). At each macrostructure Gauss point, constitutive matrices for thermal, moisture transport and mechanical responses are calculated from CH of the underlying representative volume element (RVE). A degradation model, developed from experimental data relating evolution of mechanical properties over time for a given exposure temperature and moisture concentration is also developed and incorporated in the proposed computational model. A unified approach is used to impose the RVE boundary conditions, which allows convenient switching between linear Dirichlet, uniform Neumann and periodic boundary conditions. A plain weave textile composite RVE consisting of yarns embedded in a matrix is considered in this case. Matrix and yarns are considered as isotropic and transversely isotropic materials respectively. Furthermore, the computational framework utilises hierarchic basis functions and designed to take advantage of distributed memory high-performance computing.
Quantum automata cannot detect biased coins, even in the limit
Venue: arXiv cs.CC 2016
Year: 2016

Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in accepting states, on average, given an infinite sequence of tosses. We answer this question negatively.
A Paradigm for Situated and Goal-Driven Language Learning
Venue: arXiv cs.CL 2016
Year: 2016

A distinguishing property of human intelligence is the ability to flexibly use language in order to communicate complex ideas with other humans in a variety of contexts. Research in natural language dialogue should focus on designing communicative agents which can integrate themselves into these contexts and productively collaborate with humans. In this abstract, we propose a general situated language learning paradigm which is designed to bring about robust language agents able to cooperate productively with humans.
A low-cost indoor and outdoor terrestrial autonomous navigation model
Venue: arXiv cs.HC 2016
Year: 2016

In this paper, a method for low-cost system design oriented to indoor and outdoor autonomous navigation is illustrated. In order to provide a motivation for the solution here presented, a brief discussion of the typical drawbacks of state-of-the-art technologies is reported. Finally, an application of such a method for the design of a navigation system for blindfolded people is shown.
Structure Properties of Koch Networks Based on Networks Dynamical Systems
Venue: arXiv cs.SI 2016
Year: 2016

We introduce an informative labeling algorithm for the vertices of a family of Koch networks. Each of the labels is consisted of two parts, the precise position and the time adding to Koch networks. The shortest path routing between any two vertices is determined only on the basis of their labels, and the routing is calculated only by few computations. The rigorous solutions of betweenness centrality for every node and edge are also derived by the help of their labels. Furthermore, the community structure in Koch networks is studied by the current and voltage characteristics of its resistor networks.
Generating captions without looking beyond objects
Venue: arXiv cs.CV 2016
Year: 2016

This paper explores new evaluation perspectives for image captioning and introduces a noun translation task that achieves comparative image caption generation performance by translating from a set of nouns to captions. This implies that in image captioning, all word categories other than nouns can be evoked by a powerful language model without sacrificing performance on n-gram precision. The paper also investigates lower and upper bounds of how much individual word categories in the captions contribute to the final BLEU score. A large possible improvement exists for nouns, verbs, and prepositions.
Semi-supervised Discovery of Informative Tweets During the Emerging Disasters
Venue: arXiv cs.CL 2016
Year: 2016

The first objective towards the effective use of microblogging services such as Twitter for situational awareness during the emerging disasters is discovery of the disaster-related postings. Given the wide range of possible disasters, using a pre-selected set of disaster-related keywords for the discovery is suboptimal. An alternative that we focus on in this work is to train a classifier using a small set of labeled postings that are becoming available as a disaster is emerging. Our hypothesis is that utilizing large quantities of historical microblogs could improve the quality of classification, as compared to training a classifier only on the labeled data. We propose to use unlabeled microblogs to cluster words into a limited number of clusters and use the word clusters as features for classification. To evaluate the proposed semi-supervised approach, we used Twitter data from 6 different disasters. Our results indicate that when the number of labeled tweets is 100 or less, the proposed approach is superior to the standard classification based on the bag or words feature representation. Our results also reveal that the choice of the unlabeled corpus, the choice of word clustering algorithm, and the choice of hyperparameters can have a significant impact on the classification accuracy.
RAVEN X High Performance Data Mining Toolbox for Bioacoustic Data Analysis
Venue: arXiv cs.SD 2016
Year: 2016

Objective of this work is to integrate high performance computing (HPC) technologies and bioacoustics data-mining capabilities by offering a MATLAB-based toolbox called Raven-X. Raven-X will provide a hardware-independent solution, for processing large acoustic datasets - the toolkit will be available to the community at no cost. This goal will be achieved by leveraging prior work done which successfully deployed MATLAB based HPC tools within Cornell University's Bioacoustics Research Program (BRP). These tools enabled commonly available multi-core computers to process data at accelerated rates to detect and classify whale sounds in large multi-channel sound archives. Through this collaboration, we will expand on this effort which was featured through Mathworks research and industry forums incorporate new cutting-edge detectors and classifiers, and disseminate Raven-X to the broader bioacoustics community.