OpenRaiser/Intern-Atlas huggingface dataset:
xDGP: A Dynamic Graph Processing System with Adaptive Partitioning
Venue: arXiv cs.DC 2013
Year: 2013

Many real-world systems, such as social networks, rely on mining efficiently large graphs, with hundreds of millions of vertices and edges. This volume of information requires partitioning the graph across multiple nodes in a distributed system. This has a deep effect on performance, as traversing edges cut between partitions incurs a significant performance penalty due to the cost of communication. Thus, several systems in the literature have attempted to improve computational performance by enhancing graph partitioning, but they do not support another characteristic of real-world graphs: graphs are inherently dynamic, their topology evolves continuously, and subsequently the optimum partitioning also changes over time. In this work, we present the first system that dynamically repartitions massive graphs to adapt to structural changes. The system optimises graph partitioning to prevent performance degradation without using data replication. The system adopts an iterative vertex migration algorithm that relies on local information only, making complex coordination unnecessary. We show how the improvement in graph partitioning reduces execution time by over 50%, while adapting the partitioning to a large number of changes to the graph in three real-world scenarios.
Minutiae Based Thermal Human Face Recognition using Label Connected Component Algorithm
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, a thermal infra red face recognition system for human identification and verification using blood perfusion data and back propagation feed forward neural network is proposed. The system consists of three steps. At the very first step face region is cropped from the colour 24-bit input images. Secondly face features are extracted from the croped region, which will be taken as the input of the back propagation feed forward neural network in the third step and classification and recognition is carried out. The proposed approaches are tested on a number of human thermal infra red face images created at our own laboratory. Experimental results reveal the higher degree performance
Achieving High Performance with Unified Residual Evaluation
Venue: arXiv cs.MS 2013
Year: 2013

We examine residual evaluation, perhaps the most basic operation in numerical simulation. By raising the level of abstraction in this operation, we can eliminate specialized code, enable optimization, and greatly increase the extensibility of existing code.
Hereditary Substitution for the λΔ-Calculus
Venue: arXiv cs.LO 2013
Year: 2013

Hereditary substitution is a form of type-bounded iterated substitution, first made explicit by Watkins et al. and Adams in order to show normalization of proof terms for various constructive logics. This paper is the first to apply hereditary substitution to show normalization of a type theory corresponding to a non-constructive logic, namely the lambda-Delta calculus as formulated by Rehof. We show that there is a non-trivial extension of the hereditary substitution function of the simply-typed lambda calculus to one for the lambda-Delta calculus. Then hereditary substitution is used to prove normalization.
Induction by Coinduction and Control Operators in Call-by-Name
Venue: arXiv cs.LO 2013
Year: 2013

This paper studies emulation of induction by coinduction in a call-by-name language with control operators. Since it is known that call-by-name programming languages with control operators cannot have general initial algebras, interaction of induction and control operators is often restricted to effect-free functions. We show that some class of such restricted inductive types can be derived from full coinductive types by the power of control operators. As a typical example of our results, the type of natural numbers is represented by the type of streams. The underlying idea is a counterpart of the fact that some coinductive types can be expressed by inductive types in call-by-name pure language without side-effects.
How to Obtain Computational Completeness in P Systems with One Catalyst
Venue: arXiv cs.FL 2013
Year: 2013

Whether P systems with only one catalyst can already be computationally complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rewriting rules from one set of a finite number of sets of multiset rewriting rules allows for obtaining computational completeness with one catalyst and only one membrane. If the targets are used for choosing the multiset of rules to be applied, for getting computational completeness with only one catalyst more than one membrane is needed. If the available sets of rules change periodically with time, computational completeness can be obtained with one catalyst in one membrane. Moreover, we also improve existing computational completeness results for P systems with mobile catalysts and for P systems with membrane creation.
Hyperbolic tilings and formal language theory
Venue: arXiv cs.FL 2013
Year: 2013

In this paper, we try to give the appropriate class of languages to which belong various objects associated with tessellations in the hyperbolic plane.
On a Family of Circulant Matrices for Quasi-Cyclic Low-Density Generator Matrix Codes
Venue: arXiv cs.IT 2013
Year: 2013

We present a new class of sparse and easily invertible circulant matrices that can have a sparse inverse though not being permutation matrices. Their study is useful in the design of quasi-cyclic low-density generator matrix codes, that are able to join the inner structure of quasi-cyclic codes with sparse generator matrices, so limiting the number of elementary operations needed for encoding. Circulant matrices of the proposed class permit to hit both targets without resorting to identity or permutation matrices that may penalize the code minimum distance and often cause significant error floors.
From Instantly Decodable to Random Linear Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

Our primary goal in this paper is to traverse the performance gap between two linear network coding schemes: random linear network coding (RLNC) and instantly decodable network coding (IDNC) in terms of throughput and decoding delay. We first redefine the concept of packet generation and use it to partition a block of partially-received data packets in a novel way, based on the coding sets in an IDNC solution. By varying the generation size, we obtain a general coding framework which consists of a series of coding schemes, with RLNC and IDNC identified as two extreme cases. We then prove that the throughput and decoding delay performance of all coding schemes in this coding framework are bounded between the performance of RLNC and IDNC and hence throughput-delay tradeoff becomes possible. We also propose implementations of this coding framework to further improve its throughput and decoding delay performance, to manage feedback frequency and coding complexity, or to achieve in-block performance adaption. Extensive simulations are then provided to verify the performance of the proposed coding schemes and their implementations.
On the Stability Region of a Relay-Assisted Multiple Access Scheme
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we study the impact of a relay node in a two-user network. We assume a random access collision channel model with erasures. In particular we obtain an inner and an outer bound for the stability region.
Ordered Probability Mass Function
Venue: arXiv cs.DM 2013
Year: 2013

Suppose that in the four tests Alice's scores are 90, 95, 85, 90, and Bob's scores are 85, 95, 90, 90. How to evaluate their scores? In this paper, we introduce the concept of ordered probability mass function which can be used to find a probability mass function with smaller variance. More interestingly, we can use it to distinguish sequences of positive numbers statistically.
Improvements to deep convolutional neural networks for LVCSR
Venue: arXiv cs.LG 2013
Year: 2013

Deep Convolutional Neural Networks (CNNs) are more powerful than Deep Neural Networks (DNN), as they are able to better reduce spectral variation in the input signal. This has also been confirmed experimentally, with CNNs showing improvements in word error rate (WER) between 4-12% relative compared to DNNs across a variety of LVCSR tasks. In this paper, we describe different methods to further improve CNN performance. First, we conduct a deep analysis comparing limited weight sharing and full weight sharing with state-of-the-art features. Second, we apply various pooling strategies that have shown improvements in computer vision to an LVCSR speech task. Third, we introduce a method to effectively incorporate speaker adaptation, namely fMLLR, into log-mel features. Fourth, we introduce an effective strategy to use dropout during Hessian-free sequence training. We find that with these improvements, particularly with fMLLR and dropout, we are able to achieve an additional 2-3% relative improvement in WER on a 50-hour Broadcast News task over our previous best CNN baseline. On a larger 400-hour BN task, we find an additional 4-5% relative improvement over our previous best CNN baseline.
An Aggregation Technique For Large-Scale PEPA Models With Non-Uniform Populations
Venue: arXiv cs.PF 2013
Year: 2013

Performance analysis based on modelling consists of two major steps: model construction and model analysis. Formal modelling techniques significantly aid model construction but can exacerbate model analysis. In particular, here we consider the analysis of large-scale systems which consist of one or more entities replicated many times to form large populations. The replication of entities in such models can cause their state spaces to grow exponentially to the extent that their exact stochastic analysis becomes computationally expensive or even infeasible. In this paper, we propose a new approximate aggregation algorithm for a class of large-scale PEPA models. For a given model, the method quickly checks if it satisfies a syntactic condition, indicating that the model may be solved approximately with high accuracy. If so, an aggregated CTMC is generated directly from the model description. This CTMC can be used for efficient derivation of an approximate marginal probability distribution over some of the model's populations. In the context of a large-scale client-server system, we demonstrate the usefulness of our method.
Quasi-Cyclic Codes Over Finite Chain Rings
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we mainly consider quasi-cyclic (QC) codes over finite chain rings. We study module structures and trace representations of QC codes, which lead to some lower bounds on the minimum Hamming distance of QC codes. Moreover, we investigate the structural properties of 1-generator QC codes. Under some conditions, we discuss the enumeration of 1-generator QC codes and describe how to obtain the one and only one generator for each 1-generator QC code.
Power Efficient MISO Beamforming for Secure Layered Transmission
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies secure layered video transmission in a multiuser multiple-input single-output (MISO) beamforming downlink communication system. The power allocation algorithm design is formulated as a non-convex optimization problem for minimizing the total transmit power while guaranteeing a minimum received signal-to-interference-plus-noise ratio (SINR) at the desired receiver. In particular, the proposed problem formulation takes into account the self-protecting architecture of layered transmission and artificial noise generation to prevent potential information eavesdropping. A semi-definite programming (SDP) relaxation based power allocation algorithm is proposed to obtain an upper bound solution. A sufficient condition for the global optimal solution is examined to reveal the tightness of the upper bound solution. Subsequently, two suboptimal power allocation schemes with low computational complexity are proposed for enabling secure layered video transmission. Simulation results demonstrate significant transmit power savings achieved by the proposed algorithms and layered transmission compared to the baseline schemes.
Flashmon V2: Monitoring Raw NAND Flash Memory I/O Requests on Embedded Linux
Venue: arXiv cs.OS 2013
Year: 2013

This paper presents Flashmon version 2, a tool for monitoring embedded Linux NAND flash memory I/O requests. It is designed for embedded boards based devices containing raw flash chips. Flashmon is a kernel module and stands for "flash monitor". It traces flash I/O by placing kernel probes at the NAND driver level. It allows tracing at runtime the 3 main flash operations: page reads / writes and block erasures. Flashmon is (1) generic as it was successfully tested on the three most widely used flash file systems that are JFFS2, UBIFS and YAFFS, and several NAND chip models. Moreover, it is (2) non intrusive, (3) has a controllable memory footprint, and (4) exhibits a low overhead (<6%) on the traced system. Finally, it is (5) simple to integrate and used as a standalone module or as a built-in function / module in existing kernel sources. Monitoring flash memory operations allows a better understanding of existing flash management systems by studying and analyzing their behavior. Moreover it is useful in development phase for prototyping and validating new solutions.
DUNE as an Example of Sustainable Open Source Scientific Software Development
Venue: arXiv cs.MS 2013
Year: 2013

In this paper we describe how DUNE, an open source scientific software framework, is developed. Having a sustainable software framework for the solution of partial differential equations is the main driver of DUNE's development. We take a look how DUNE strives to stay sustainable software.
Web Standards as Standard Pieces in Robotics
Venue: arXiv cs.SY 2013
Year: 2013

Modern robotics often involves the use of web technologies as a means to cope with the complexity of design and operation. Many of these technologies have been formalized into standards, which are often avoided by those in robotics and controls because of a sometimes warranted fear that "the web" is too slow, or too uncertain for meaningful control applications. In this work we argue that while web technologies may not be applicable for all control, they should not be dismissed outright because they can provide critical help with system integration. Web technologies have also advanced significantly over the past decade. We present the details of an application of a web server to perform open and close-loop control (between 3Hz and 1kHz) over a variety of different network topologies. In our study we also consider the impact of a web browser to implement the control of the plant. Our results confirm that meaningful control can be performed using web technologies, and also highlight design choices that can limit their applicability.
Desktop and Mobile Web Page Comparison: Characteristics, Trends, and Implications
Venue: arXiv cs.HC 2013
Year: 2013

The broad proliferation of mobile devices in recent years has drastically changed the means of accessing the World Wide Web. Describing a shift away from the desktop computer era for content consumption, predictions indicate that the main access of web-based content will come from mobile devices. Concurrently, the manner of content presentation has changed as well; web artifacts are allowing for richer media and higher levels of user interaction which is enabled through increasing access networks speeds. This article provides an overview of more than two years of high level web page characteristics by comparing the desktop and mobile client versions. Our study is the first long-term evaluation of differences as seen by desktop and mobile web browser clients. We showcase the main differentiating factors with respect to the number of web page object requests, their sizes, relationships, and web page object caching. We additionally highlight long-term trends and discuss their future implications.
Parallel-in-time method for calculation of long-range electrostatic interactions
Venue: arXiv cs.NA 2013
Year: 2013

Large molecular dynamics simulations (millions of atoms, tens of microseconds, thousands of processors) hit the strong scalability wall: simulation on twice as many processors does not take half the time. Inspired by large N-body space simulations, we suggest to calculate the bottleneck---the long-range interactions---parallel in time. This technical report aims to present the combination of parareal method and multilevel summation method. We thoroughly describe both methods and reasons for their particular combination. We also propose several optimizations that should provide the acceleration by an order of magnitude.
Evolution of the Chilean Web: A Larger Study
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we extend our previous and only study on the dynamics of the Chilean Web. This new study doubles the time period and to the best of our knowledge is the only study of its type known about any country in the Web. The new results corroborate the trends found before, in particular the exponential growth of the Web, and reinforce the conclusion that the Web is more chaotic than we would like. Hence, modeling most Web characteristics is not trivial.
The Swap Matching Problem Revisited
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we revisit the much studied problem of Pattern Matching with Swaps (Swap Matching problem, for short). We first present a graph-theoretic model, which opens a new and so far unexplored avenue to solve the problem. Then, using the model, we devise two efficient algorithms to solve the swap matching problem. The resulting algorithms are adaptations of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, both the algorithms run in linear time considering a fixed alphabet.
Submodular Maximization Meets Streaming: Matchings, Matroids, and More
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM), which is in turn a generalization of maximum cardinality matching (MCM). We give two incomparable algorithms for this problem with space usage falling in the semi-streaming range---they store only $O(n)$ edges, using $O(n\log n)$ working memory---that achieve approximation ratios of $7.75$ in a single pass and $(3+ε)$ in $O(ε^{-3})$ passes respectively. The operations of these algorithms mimic those of Zelke's and McGregor's respective algorithms for MWM; the novelty lies in the analysis for the MSM setting. In fact we identify a general framework for MWM algorithms that allows this kind of adaptation to the broader setting of MSM. In the sequel, we give generalizations of these results where the maximization is over "independent sets" in a very general sense. This generalization captures hypermatchings in hypergraphs as well as independence in the intersection of multiple matroids.
Exploring the Boundaries of Monad Tensorability on Set
Venue: arXiv cs.LO 2013
Year: 2013

We study a composition operation on monads, equivalently presented as large equational theories. Specifically, we discuss the existence of tensors, which are combinations of theories that impose mutual commutation of the operations from the component theories. As such, they extend the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts; in particular, in the semantics of programming languages, the monad transformer for global state is given by a tensor. We present two main results: we show that the tensor of two monads need not in general exist by presenting two counterexamples, one of them involving finite powerset (i.e. the theory of join semilattices); this solves a somewhat long-standing open problem, and contrasts with recent results that had ruled out previously expected counterexamples. On the other hand, we show that tensors with bounded powerset monads do exist from countable powerset upwards.
Exponentially Fast Parameter Estimation in Networks Using Distributed Dual Averaging
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we present an optimization-based view of distributed parameter estimation and observational social learning in networks. Agents receive a sequence of random, independent and identically distributed (i.i.d.) signals, each of which individually may not be informative about the underlying true state, but the signals together are globally informative enough to make the true state identifiable. Using an optimization-based characterization of Bayesian learning as proximal stochastic gradient descent (with Kullback-Leibler divergence from a prior as a proximal function), we show how to efficiently use a distributed, online variant of Nesterov's dual averaging method to solve the estimation with purely local information. When the true state is globally identifiable, and the network is connected, we prove that agents eventually learn the true parameter using a randomized gossip scheme. We demonstrate that with high probability the convergence is exponentially fast with a rate dependent on the KL divergence of observations under the true state from observations under the second likeliest state. Furthermore, our work also highlights the possibility of learning under continuous adaptation of network which is a consequence of employing constant, unit stepsize for the algorithm.
Polynomial Path Orders
Venue: arXiv cs.LO 2013
Year: 2013

This paper is concerned with the complexity analysis of constructor term rewrite systems and its ramification in implicit computational complexity. We introduce a path order with multiset status, the polynomial path order POP*, that is applicable in two related, but distinct contexts. On the one hand POP* induces polynomial innermost runtime complexity and hence may serve as a syntactic, and fully automatable, method to analyse the innermost runtime complexity of term rewrite systems. On the other hand POP* provides an order-theoretic characterisation of the polytime computable functions: the polytime computable functions are exactly the functions computable by an orthogonal constructor TRS compatible with POP*.
The Google Scholar Experiment: how to index false papers and manipulate bibliometric indicators
Venue: arXiv cs.DL 2013
Year: 2013

Google Scholar has been well received by the research community. Its promises of free, universal and easy access to scientific literature as well as the perception that it covers better than other traditional multidisciplinary databases the areas of the Social Sciences and the Humanities have contributed to the quick expansion of Google Scholar Citations and Google Scholar Metrics: two new bibliometric products that offer citation data at the individual level and at journal level. In this paper we show the results of a experiment undertaken to analyze Google Scholar's capacity to detect citation counting manipulation. For this, six documents were uploaded to an institutional web domain authored by a false researcher and referencing all the publications of the members of the EC3 research group at the University of Granada. The detection of Google Scholar of these papers outburst the citations included in the Google Scholar Citations profiles of the authors. We discuss the effects of such outburst and how it could affect the future development of such products not only at individual level but also at journal level, especially if Google Scholar persists with its lack of transparency.