OpenRaiser/Intern-Atlas huggingface dataset:
Separator-Based Graph Embedding into Multidimensional Grids with Small Edge-Congestion
Venue: arXiv cs.DM 2014
Year: 2014

We study the problem of embedding a guest graph with minimum edge-congestion into a multidimensional grid with the same size as that of the guest graph. Based on a well-known notion of graph separators, we show that an embedding with a smaller edge-congestion can be obtained if the guest graph has a smaller separator, and if the host grid has a higher but constant dimension. Specifically, we prove that any graph with $N$ nodes, maximum node degree $Δ$, and with a node-separator of size $O(n^α)$ ($0\leqα<1$) can be embedded into a grid of a fixed dimension $d\geq 2$ with at least $N$ nodes, with an edge-congestion of $O(Δ)$ if $d>1/(1-α)$, $O(Δ\log N)$ if $d=1/(1-α)$, and $O(ΔN^{α-1+\frac{1}{d}})$ if $d< 1/(1-α)$. This edge-congestion achieves constant ratio approximation if $d>1/(1-α)$, and matches an existential lower bound within a constant factor if $d\leq 1/(1-α)$. Our result implies that if the guest graph has an excluded minor of a fixed size, such as a planar graph, then we can obtain an edge-congestion of $O(Δ\log N)$ for $d=2$ and $O(Δ)$ for any fixed $d\geq 3$. Moreover, if the guest graph has a fixed treewidth, such as a tree, an outerplanar graph, and a series-parallel graph, then we can obtain an edge-congestion of $O(Δ)$ for any fixed $d\geq 2$. To design our embedding algorithm, we introduce edge-separators bounding expansion, such that in partitioning a graph into isolated nodes using edge-separators recursively, the number of outgoing edges from a subgraph to be partitioned in a recursive step is bounded. We present an algorithm to construct an edge-separator with expansion of $O(Δn^α)$ from a node-separator of size $O(n^α)$.
Real-time Topic-aware Influence Maximization Using Preprocessing
Venue: arXiv cs.SI 2014
Year: 2014

Influence maximization is the task of finding a set of seed nodes in a social network such that the influence spread of these seed nodes based on certain influence diffusion model is maximized. Topic-aware influence diffusion models have been recently proposed to address the issue that influence between a pair of users are often topic-dependent and information, ideas, innovations etc. being propagated in networks (referred collectively as items in this paper) are typically mixtures of topics. In this paper, we focus on the topic-aware influence maximization task. In particular, we study preprocessing methods for these topics to avoid redoing influence maximization for each item from scratch. We explore two preprocessing algorithms with theoretical justifications. Our empirical results on data obtained in a couple of existing studies demonstrate that one of our algorithms stands out as a strong candidate providing microsecond online response time and competitive influence spread, with reasonable preprocessing effort.
A survey on tidal analysis and forecasting methods for Tsunami detection
Venue: arXiv cs.CE 2014
Year: 2014

Accurate analysis and forecasting of tidal level are very important tasks for human activities in oceanic and coastal areas. They can be crucial in catastrophic situations like occurrences of Tsunamis in order to provide a rapid alerting to the human population involved and to save lives. Conventional tidal forecasting methods are based on harmonic analysis using the least squares method to determine harmonic parameters. However, a large number of parameters and long-term measured data are required for precise tidal level predictions with harmonic analysis. Furthermore, traditional harmonic methods rely on models based on the analysis of astronomical components and they can be inadequate when the contribution of non-astronomical components, such as the weather, is significant. Other alternative approaches have been developed in the literature in order to deal with these situations and provide predictions with the desired accuracy, with respect also to the length of the available tidal record. These methods include standard high or band pass filtering techniques, although the relatively deterministic character and large amplitude of tidal signals make special techniques, like artificial neural networks and wavelets transform analysis methods, more effective. This paper is intended to provide the communities of both researchers and practitioners with a broadly applicable, up to date coverage of tidal analysis and forecasting methodologies that have proven to be successful in a variety of circumstances, and that hold particular promise for success in the future. Classical and novel methods are reviewed in a systematic and consistent way, outlining their main concepts and components, similarities and differences, advantages and disadvantages.
Variable-Rate Linear Network Error Correction MDS Codes
Venue: arXiv cs.IT 2014
Year: 2014

In network communication, the source often transmits messages at several different information rates within a session. How to deal with information transmission and network error correction simultaneously under different rates is introduced in this paper as a variable-rate network error correction problem. Apparently, linear network error correction MDS codes are expected to be used for these different rates. For this purpose, designing a linear network error correction MDS code based on the existing results for each information rate is an efficient solution. In order to solve the problem more efficiently, we present the concept of variable-rate linear network error correction MDS codes, that is, these linear network error correction MDS codes of different rates have the same local encoding kernel at each internal node. Further, we propose an approach to construct such a family of variable-rate network MDS codes and give an algorithm for efficient implementation. This approach saves the storage space for each internal node, and resources and time for the transmission on networks. Moreover, the performance of our proposed algorithm is analyzed, including the field size, the time complexity, the encoding complexity at the source node, and the decoding methods. Finally, a random method is introduced for constructing variable-rate network MDS codes and we obtain a lower bound on the success probability of this random method, which shows that this probability will approach to one as the base field size goes to infinity.
Particle methods enable fast and simple approximation of Sobolev gradients in image segmentation
Venue: arXiv cs.CV 2014
Year: 2014

Bio-image analysis is challenging due to inhomogeneous intensity distributions and high levels of noise in the images. Bayesian inference provides a principled way for regularizing the problem using prior knowledge. A fundamental choice is how one measures "distances" between shapes in an image. It has been shown that the straightforward geometric L2 distance is degenerate and leads to pathological situations. This is avoided when using Sobolev gradients, rendering the segmentation problem less ill-posed. The high computational cost and implementation overhead of Sobolev gradients, however, have hampered practical applications. We show how particle methods as applied to image segmentation allow for a simple and computationally efficient implementation of Sobolev gradients. We show that the evaluation of Sobolev gradients amounts to particle-particle interactions along the contour in an image. We extend an existing particle-based segmentation algorithm to using Sobolev gradients. Using synthetic and real-world images, we benchmark the results for both 2D and 3D images using piecewise smooth and piecewise constant region models. The present particle approximation of Sobolev gradients is 2.8 to 10 times faster than the previous reference implementation, but retains the known favorable properties of Sobolev gradients. This speedup is achieved by using local particle-particle interactions instead of solving a global Poisson equation at each iteration. The computational time per iteration is higher for Sobolev gradients than for L2 gradients. Since Sobolev gradients precondition the optimization problem, however, a smaller number of overall iterations may be necessary for the algorithm to converge, which can in some cases amortize the higher per-iteration cost.
A Back-to-Basics Empirical Study of Priority Queues
Venue: arXiv cs.DS 2014
Year: 2014

The theory community has proposed several new heap variants in the recent past which have remained largely untested experimentally. We take the field back to the drawing board, with straightforward implementations of both classic and novel structures using only standard, well-known optimizations. We study the behavior of each structure on a variety of inputs, including artificial workloads, workloads generated by running algorithms on real map data, and workloads from a discrete event simulator used in recent systems networking research. We provide observations about which characteristics are most correlated to performance. For example, we find that the L1 cache miss rate appears to be strongly correlated with wallclock time. We also provide observations about how the input sequence affects the relative performance of the different heap variants. For example, we show (both theoretically and in practice) that certain random insertion-deletion sequences are degenerate and can lead to misleading results. Overall, our findings suggest that while the conventional wisdom holds in some cases, it is sorely mistaken in others.
A Proposed Improvement Equalizer for Telephone and Mobile Circuit Channels
Venue: arXiv cs.IT 2014
Year: 2014

In the transmission of digital data at a relatively high rate over a particular band limited channel, it is normally necessary to employ an equalizer at the receiver in order to correct the signal distortion introduced by the channel .ISI (inter symbol interference) leads to large error probability if it is not suppressed .The possible solutions for coping with ISI such as equalization technique. Maximum Likelihood Sequence Estimation (MLSE) implemented with Viterbi algorithm is the optimal equalizer for this ISI problem sense it minimizes the sequence of error rate. This estimator involves a very considerable amount of equipment complexity especially when detecting a multilevel digital signal having large alphabet, and/or operating under a channel with long impulse response, this arises a need to develop detection algorithms with reduced complexity without losing the performance. The aim of this work is to study the various ways to remove the ISI, concentrating on the decision-based algorithms (DFE, MLSE, and near MLSE), analyzing the difference between them from both performance and complexity point of view. An Improved non linear equalizer with Perturbation algorithm has been suggested which trying to enhance the performance and reduce the computational complexity by comparing it with the other existing detection algorithms.
An extended isogeometric analysis for vibration of cracked FGM plates using higher-order shear deformation theory
Venue: arXiv cs.CE 2014
Year: 2014

A novel and effective formulation that combines the eXtended IsoGeometric Approach (XIGA) and Higher-order Shear Deformation Theory (HSDT) is proposed to study the free vibration of cracked Functionally Graded Material (FGM) plates. Herein, the general HSDT model with five unknown variables per node is applied for calculating the stiffness matrix without needing Shear Correction Factor (SCF). In order to model the discontinuous and singular phenomena in the cracked plates, IsoGeometric Analysis (IGA) utilizing the Non-Uniform Rational B-Spline (NURBS) functions is incorporated with enrichment functions through the partition of unity method. NURBS basis functions with their inherent arbitrary high order smoothness permit the C1 requirement of the HSDT model. The material properties of the FGM plates vary continuously through the plate thickness according to an exponent function. The effects of gradient index, crack length, crack location, length to thickness on the natural frequencies and mode shapes of simply supported and clamped FGM plate are studied. Numerical examples are provided to show excellent performance of the proposed method compared with other published solutions in the literature.
Isogeometric finite element analysis of laminated composite plates based on a four variable refined plate theory
Venue: arXiv cs.CE 2014
Year: 2014

In this paper, a novel and effective formulation based on isogeometric approach (IGA) and Refined Plate Theory (RPT) is proposed to study the behavior of laminated composite plates. Using many kinds of higher-order distributed functions, RPT model naturally satisfies the traction-free boundary conditions at plate surfaces and describes the non-linear distribution of shear stresses without requiring shear correction factor (SCF). IGA utilizes the basis functions, namely B-splines or non-uniform rational B-splines (NURBS), which achieve easily the smoothness of any arbitrary order. It hence satisfies the C1 requirement of the RPT model. The static, dynamic and buckling analysis of rectangular plates is investigated for different boundary conditions. Numerical results show high effectiveness of the present formulation.
Summarisation of Short-Term and Long-Term Videos using Texture and Colour
Venue: arXiv cs.CV 2014
Year: 2014

We present a novel approach to video summarisation that makes use of a Bag-of-visual-Textures (BoT) approach. Two systems are proposed, one based solely on the BoT approach and another which exploits both colour information and BoT features. On 50 short-term videos from the Open Video Project we show that our BoT and fusion systems both achieve state-of-the-art performance, obtaining an average F-measure of 0.83 and 0.86 respectively, a relative improvement of 9% and 13% when compared to the previous state-of-the-art. When applied to a new underwater surveillance dataset containing 33 long-term videos, the proposed system reduces the amount of footage by a factor of 27, with only minor degradation in the information content. This order of magnitude reduction in video data represents significant savings in terms of time and potential labour cost when manually reviewing such footage.
On the Behavioral Interpretation of System-Environment Fit and Auto-Resilience
Venue: arXiv cs.OH 2014
Year: 2014

Already 71 years ago Rosenblueth, Wiener, and Bigelow introduced the concept of the "behavioristic study of natural events" and proposed a classification of systems according to the quality of the behaviors they are able to exercise. In this paper we consider the problem of the resilience of a system when deployed in a changing environment, which we tackle by considering the behaviors both the system organs and the environment mutually exercise. We then introduce a partial order and a metric space for those behaviors, and we use them to define a behavioral interpretation of the concept of system-environment fit. Moreover we suggest that behaviors based on the extrapolation of future environmental requirements would allow systems to proactively improve their own system-environment fit and optimally evolve their resilience. Finally we describe how we plan to express a complex optimization strategy in terms of the concepts introduced in this paper.
Verbesserung von OS- und Service-Fingerprinting mittels Fuzzing
Venue: arXiv cs.CR 2014
Year: 2014

Fingerprinting of services and operating systems is an essential part of penetration tests. In order to successfully penetrate the computing system's security measurements, preexisting fingerprinting methods are described and the paradigm of fingerprinting with mutation-based fuzzing is established. A case study about operating system and FTP server fingerprinting is presented whereby the feasibility of the approach is demonstrated. The research results show that the developed tools can be used for even more precise fingerprinting than the preexisting tools.
Timed Soft Concurrent Constraint Programs: An Interleaved and a Parallel Approach
Venue: arXiv cs.PL 2014
Year: 2014

We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: the computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker which distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold which is used to determine their success or suspension. In the paper we provide a language to describe the agents behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions both on preference values and time events may benefit from this language. To appear in Theory and Practice of Logic Programming (TPLP).
Unary Pushdown Automata and Straight-Line Programs
Venue: arXiv cs.FL 2014
Year: 2014

We consider decision problems for deterministic pushdown automata over a unary alphabet (udpda, for short). Udpda are a simple computation model that accept exactly the unary regular languages, but can be exponentially more succinct than finite-state automata. We complete the complexity landscape for udpda by showing that emptiness (and thus universality) is P-hard, equivalence and compressed membership problems are P-complete, and inclusion is coNP-complete. Our upper bounds are based on a translation theorem between udpda and straight-line programs over the binary alphabet (SLPs). We show that the characteristic sequence of any udpda can be represented as a pair of SLPs---one for the prefix, one for the lasso---that have size linear in the size of the udpda and can be computed in polynomial time. Hence, decision problems on udpda are reduced to decision problems on SLPs. Conversely, any SLP can be converted in logarithmic space into a udpda, and this forms the basis for our lower bound proofs. We show coNP-hardness of the ordered matching problem for SLPs, from which we derive coNP-hardness for inclusion. In addition, we complete the complexity landscape for unary nondeterministic pushdown automata by showing that the universality problem is $Π_2 \mathrm P$-hard, using a new class of integer expressions. Our techniques have applications beyond udpda. We show that our results imply $Π_2 \mathrm P$-completeness for a natural fragment of Presburger arithmetic and coNP lower bounds for compressed matching problems with one-character wildcards.
We Tweet Like We Talk and Other Interesting Observations: An Analysis of English Communication Modalities
Venue: arXiv cs.CL 2014
Year: 2014

Modalities of communication for human beings are gradually increasing in number with the advent of new forms of technology. Many human beings can readily transition between these different forms of communication with little or no effort, which brings about the question: How similar are these different communication modalities? To understand technology$\text{'}$s influence on English communication, four different corpora were analyzed and compared: Writing from Books using the 1-grams database from the Google Books project, Twitter, IRC Chat, and transcribed Talking. Multi-word confusion matrices revealed that Talking has the most similarity when compared to the other modes of communication, while 1-grams were the least similar form of communication analyzed. Based on the analysis of word usage, word usage frequency distributions, and word class usage, among other things, Talking is also the most similar to Twitter and IRC Chat. This suggests that communicating using Twitter and IRC Chat evolved from Talking rather than Writing. When we communicate online, even though we are writing, we do not Tweet or Chat how we write books; we Tweet and Chat how we Speak. Nonfiction and Fiction writing were clearly differentiable from our analysis with Twitter and Chat being much more similar to Fiction than Nonfiction writing. These hypotheses were then tested using author and journalists Cory Doctorow. Mr. Doctorow$\text{'}$s Writing, Twitter usage, and Talking were all found to have very similar vocabulary usage patterns as the amalgamized populations, as long as the writing was Fiction. However, Mr. Doctorow$\text{'}$s Nonfiction writing is different from 1-grams and other collected Nonfiction writings. This data could perhaps be used to create more entertaining works of Nonfiction.
Multi-Shot Person Re-Identification via Relational Stein Divergence
Venue: arXiv cs.CV 2014
Year: 2014

Person re-identification is particularly challenging due to significant appearance changes across separate camera views. In order to re-identify people, a representative human signature should effectively handle differences in illumination, pose and camera parameters. While general appearance-based methods are modelled in Euclidean spaces, it has been argued that some applications in image and video analysis are better modelled via non-Euclidean manifold geometry. To this end, recent approaches represent images as covariance matrices, and interpret such matrices as points on Riemannian manifolds. As direct classification on such manifolds can be difficult, in this paper we propose to represent each manifold point as a vector of similarities to class representers, via a recently introduced form of Bregman matrix divergence known as the Stein divergence. This is followed by using a discriminative mapping of similarity vectors for final classification. The use of similarity vectors is in contrast to the traditional approach of embedding manifolds into tangent spaces, which can suffer from representing the manifold structure inaccurately. Comparative evaluations on benchmark ETHZ and iLIDS datasets for the person re-identification task show that the proposed approach obtains better performance than recent techniques such as Histogram Plus Epitome, Partial Least Squares, and Symmetry-Driven Accumulation of Local Features.
A Novel Method for Vectorization
Venue: arXiv cs.CV 2014
Year: 2014

Vectorization of images is a key concern uniting computer graphics and computer vision communities. In this paper we are presenting a novel idea for efficient, customizable vectorization of raster images, based on Catmull Rom spline fitting. The algorithm maintains a good balance between photo-realism and photo abstraction, and hence is applicable to applications with artistic concerns or applications where less information loss is crucial. The resulting algorithm is fast, parallelizable and can satisfy general soft realtime requirements. Moreover, the smoothness of the vectorized images aesthetically outperforms outputs of many polygon-based methods
Knowledge-Aided Reweighted Belief Propagation LDPC Decoding using Regular and Irregular Designs
Venue: arXiv cs.IT 2014
Year: 2014

In this paper a new message passing algorithm, which takes advantage of both tree-based re-parameterization and the knowledge of short cycles, is introduced for the purpose of decoding LDPC codes with short block lengths. The proposed algorithm is called variable factor appearance probability belief propagation (VFAP-BP) algorithm and is suitable for wireless communications applications, where both good decoding performance and low-latency are expected. Our simulation results show that the VFAP-BP algorithm outperforms the standard BP algorithm and requires a significantly smaller number of iterations than existing algorithms when decoding both regular and irregular LDPC codes.