OpenRaiser/Intern-Atlas huggingface dataset:
Faster Small-Constant-Periodic Merging Networks
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth (called a period in this context). In our previous paper entitled Faster 3-Periodic Merging Network we reduced twice the time of merging on $3$-periodic networks, i.e. from $12\log N$ to $6\log N$, compared to the first construction given by Kutyłowski, Loryś and Oesterdikhoff. Note that merging on $2$-periodic networks require linear time. In this paper we extend our construction, which is based on Canfield and Williamson $(\log N)$-periodic sorter, and the analysis from that paper to any period $p \ge 4$. For $p\ge 4$ our $p$-periodic network merges two sorted sequences of length $N/2$ in at most $\frac{2p}{p-2}\log N + p\frac{p-8}{p-2}$ rounds. The previous bound given by Kutyłowski at al. was $\frac{2.25p}{p-2.42}\log N$. That means, for example, that our $4$-periodic merging networks work in time upper-bounded by $4\log N$ and our $6$-periodic ones in time upper-bounded by $3\log N$ compared to the corresponding $5.67\log N$ and $3.8\log N$ previous bounds. Our construction is regular and follows the same periodification schema, whereas some additional techniques were used previously to tune the construction for $p \ge 4$. Moreover, our networks are also periodic sorters and tests on random permutations show that average sorting time is closed to $\log^2 N$.
Opportunities at the Mathematics/Future Cities Interface
Venue: arXiv cs.CY 2014
Year: 2014

We make the case for mathematicians and statisticians to stake their claim in the fast-moving and high-impact research field that is becoming known as Future Cities. After assessing the Future Cities arena, we provide some illustrative challenges where mathematical scientists can make an impact.
Bio-inspired Mechanism and Model Exploration of Software Aging
Venue: arXiv cs.SE 2014
Year: 2014

Software systems situated in network environment may experience performance degradation, availability decrease and even crash during long time running, which is called software aging. This phenomenon has been studied for more than 15 years, but most of the literatures studied software as a black box, none of them uncovered the fundamental and widely accepted mechanism of software aging as far as we know. Through analyzing the characteristics between biological aging and software aging, we find some interesting common points and bridge the gap between these two seemingly unrelated phenomena. The free radical aging theory in biological studies is also applicative to explore the mechanism and model of software aging. This paper finds an equivalent concept named `software free radical' in software aging to free radical in biological aging. In our study, the accumulation of `software free radical' is a root cause of software aging. Using the free radical modeling methodology in biological aging, we give a model for describing the kinetic of software aging based on feedback loops. Although this paper doesn't give enough theoretical proof of the modeling method, the practical results show that the feedback loop model can describe the kinetic of software aging precisely. To further validate the aging mechanism, we propose several software rejuvenation strategies focusing on cleaning the `software free radical'. The results show that software aging can be mitigated effectively by strengthening negative feedback loop or weakening positive feedback loop. This paper is the first try to answer the question `How software ages' through interdisciplinary studies. Leveraging the conclusions in this paper, people can design better software systems or keep their systems at a high performance level during long time running.
On the Sum of Correlated Squared $κ-μ$ Shadowed Random Variables and its Application to Performance Analysis of MRC
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the statistical characterization of the sum of the squared $κ-μ$ shadowed random variables with correlated shadowing components. The probability density function (PDF) of this sum is obtained in the form of a power series. The derived PDF is utilized for obtaining the performance results of the maximal ratio combining (MRC) scheme over correlated $κ-μ$ shadowed fading channels. First, we derive the moment generating function (MGF) of the received signal-to-noise ratio of the MRC receiver. By using the derived MGF expression, the analytical diversity order is obtained; it is deduced on the basis of this analysis that the diversity of the MRC receiver over correlated $κ-μ$ shadowed channels depends upon the number of diversity branches and $μ$ parameter. Further, the analytical average bit error rate of the MRC scheme is also derived, which is applicable for $M$-PSK and $M$-QAM constellations. The Shannon capacity of the correlated $κ-μ$ shadowed channels is also derived in the form of the Meijer-G function.
A Body Area Network through Wireless Technology
Venue: arXiv cs.HC 2014
Year: 2014

A physiological signal monitoring system and alerting system using wireless technology is presented. The two types of physiological signal monitoring are captured from the body through leads and using the radio-frequency transmitting and receiving module the data are interfaced to computer systems. Furthering using a developed user interface module the captured signals are analyzed for checking abnormality. Any significant recordings are transmitted to the physicians hand phone by using external serial SMS modem. ECG signal de-noising is conducted by using low-pass and high-pass filters. EEG signals de-noising is conducted by using band-pass filters set. A comparative evaluation of the module with the manual recording shows encouraging results. The ECG and EEG pattern are presented in this paper.
A Martingale Approach to Detect Peak of News in Social Network
Venue: arXiv cs.SI 2014
Year: 2014

Nowadays, social medias such as Twitter, Memetracker and Blogs have become powerful tools to propagate information. They facilitate quick dissemination sequence of information such as news article, blog posts, user's interests and thoughts through large scale. Providing strong means to analyzing social networks structure and how information diffuse through them is essential. Many recent studies emphasize on modeling information diffusion and their patterns to gain some useful knowledge. In this paper, we propose a statistical approach to online detect peak points of news when spread over social networks, to the best of our knowledge has never investigated before. The proposed model use martingale approach to predict peak points when news reached the peak of its popularity. Experimental results on real datasets show good performance of our approach to online detect these peak points.
Consensus in multi-agent systems with non-periodic sampled-data exchange and uncertain network topology
Venue: arXiv cs.SY 2014
Year: 2014

In this paper consensus in second-order multi-agent systems with a non-periodic sampled-data exchange among agents is investigated. The sampling is random with bounded inter-sampling intervals. It is assumed that each agent has exact knowledge of its own state at any time instant. The considered local interaction rule is PD-type. Sufficient conditions for stability of the consensus protocol to a time-invariant value are derived based on LMIs. Such conditions only require the knowledge of the connectivity of the graph modeling the network topology. Numerical simulations are presented to corroborate the theoretical results.
An ontology-based approach to the optimization of non-binary (2,v)-regular LDPC codes
Venue: arXiv cs.IT 2014
Year: 2014

A non-binary (2,v)-regular LDPC code is defined by a parity-check matrix with column weight 2 and row weight v. In this report, we give an ontology-based approach to the optimization for this class of codes. All possible inter-connected cycle patterns that lead to low symbol-weight codewords are identified to put together the ontology. The optimization goal is to improve the distance property of equivalent binary images. Using the proposed method, the estimation and optimization of bit-distance spectrum becomes easily handleable. Three codes in the CCSDS recommendation are analyzed and several codes with good minimum bit-distance are designed.
Recommendation Subgraphs for Web Discovery
Venue: arXiv cs.IR 2014
Year: 2014

Recommendations are central to the utility of many websites including YouTube, Quora as well as popular e-commerce stores. Such sites typically contain a set of recommendations on every product page that enables visitors to easily navigate the website. Choosing an appropriate set of recommendations at each page is one of the key features of backend engines that have been deployed at several e-commerce sites. Specifically at BloomReach, an engine consisting of several independent components analyzes and optimizes its clients' websites. This paper focuses on the structure optimizer component which improves the website navigation experience that enables the discovery of novel content. We begin by formalizing the concept of recommendations used for discovery. We formulate this as a natural graph optimization problem which in its simplest case, reduces to a bipartite matching problem. In practice, solving these matching problems requires superlinear time and is not scalable. Also, implementing simple algorithms is critical in practice because they are significantly easier to maintain in production. This motivated us to analyze three methods for solving the problem in increasing order of sophistication: a sampling algorithm, a greedy algorithm and a more involved partitioning based algorithm. We first theoretically analyze the performance of these three methods on random graph models characterizing when each method will yield a solution of sufficient quality and the parameter ranges when more sophistication is needed. We complement this by providing an empirical analysis of these algorithms on simulated and real-world production data. Our results confirm that it is not always necessary to implement complicated algorithms in the real-world and that very good practical results can be obtained by using heuristics that are backed by the confidence of concrete theoretical guarantees.
On Vertex Attack Tolerance in Regular Graphs
Venue: arXiv cs.DM 2014
Year: 2014

We have previously introduced vertex attack tolerance (VAT), denoted mathematically as $τ(G) = \min_{S \subset V} \frac{|S|}{|V-S-C_{max}(V-S)|+1}$ where $C_{max}(V-S)$ is the largest connected component in $V-S$, as an appropriate mathematical measure of resilience in the face of targeted node attacks for arbitrary degree networks. A part of the motivation for VAT was the observation that, whereas conductance, $Φ(G)$, captures both edge based and node based resilience for regular graphs, conductance fails to capture node based resilience for heterogeneous degree distributions. We had previously demonstrated an upper bound on VAT via conductance for the case of $d$-regular graphs $G$ as follows: $τ(G) \le dΦ(G)$ if $Φ(G) \le \frac{1}{d^2}$ and $τ(G) \le d^2Φ(G)$ otherwise. In this work, we provide a new matching lower bound: $τ(G) \ge \frac{1}{d}Φ(G)$. The lower and upper bound combined show that $τ(G) = Θ(Φ(G))$ for regular constant degree $d$ and yield spectral bounds as corollaries.
Assessment of classification techniques on predicting success or failure of Software reusability
Venue: arXiv cs.SE 2014
Year: 2014

Assessment of classification techniques on predicting success or failure of Software reusability
A Framework for Automated Competitive Analysis of On-line Scheduling of Firm-Deadline Tasks
Venue: arXiv cs.DS 2014
Year: 2014

We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including $D^{over}$, that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.
Modal Object Diagrams
Venue: arXiv cs.SE 2014
Year: 2014

While object diagrams (ODs) are widely used as a means to document object-oriented systems, they are expressively weak, as they are limited to describe specific possible snapshots of the system at hand. In this paper we introduce modal object diagrams (MODs), which extend the classical OD language with positive/negative and example/invariant modalities. The extended language allows the designer to specify not only positive example models but also negative examples, ones that the system should not allow, positive invariants, ones that all system's snapshots should include, and negative invariants, ones that no system snapshot is allowed to include. Moreover, as a primary application of the extended language we provide a formal verification technique that decides whether a given class diagram satisfies (i.e., models) a multi-modal object diagrams specification. In case of a negative answer, the technique outputs relevant counterexample object models, as applicable. The verification is based on a reduction to Alloy. The ideas are implemented in a prototype Eclipse plug-in. Examples show the usefulness of the extended language in specifying structural requirements of object-oriented systems in an intuitive yet expressive way.
An Operational Semantics for Activity Diagrams using SMV
Venue: arXiv cs.SE 2014
Year: 2014

This document defines an operational semantics for activity diagrams (ADs) using a translation to SMV. The translation is inspired by the work of Eshuis [Esh06] and extends it with support for data. Each execution step of the SMV module obtained from an AD represents an executed action of this AD with interleaved execution of concurrent branches. An implementation of the given translation was used in the context of semantic differencing for ADs [MRR11]. We define the translation and give two examples, showing ADs and their complete representation in SMV.
MontiCore: a Framework for Compositional Development of Domain Specific Languages
Venue: arXiv cs.SE 2014
Year: 2014

Domain specific languages (DSLs) are increasingly used today. Coping with complex language definitions, evolving them in a structured way, and ensuring their error freeness are the main challenges of DSL design and implementation. The use of modular language definitions and composition operators are therefore inevitable in the independent development of language components. In this article, we discuss these arising issues by describing a framework for the compositional development of textual DSLs and their supporting tools. We use a redundance-free definition of a readable concrete syntax and a comprehensible abstract syntax as both representations significantly overlap in their structure. For enhancing the usability of the abstract syntax, we added concepts like associations and inheritance to a grammar- based definition in order to build up arbitrary graphs (as known from metamodeling). Two modularity concepts, grammar inheritance and embedding, are discussed. They permit compositional language definition and thus simplify the extension of languages based on already existing ones. We demonstrate that compositional engineering of new languages is a useful concept when project-individual DSLs with appropriate tool support are defined.
Symbolic regression of generative network models
Venue: arXiv cs.NE 2014
Year: 2014

Networks are a powerful abstraction with applicability to a variety of scientific fields. Models explaining their morphology and growth processes permit a wide range of phenomena to be more systematically analysed and understood. At the same time, creating such models is often challenging and requires insights that may be counter-intuitive. Yet there currently exists no general method to arrive at better models. We have developed an approach to automatically detect realistic decentralised network growth models from empirical data, employing a machine learning technique inspired by natural selection and defining a unified formalism to describe such models as computer programs. As the proposed method is completely general and does not assume any pre-existing models, it can be applied "out of the box" to any given network. To validate our approach empirically, we systematically rediscover pre-defined growth laws underlying several canonical network generation models and credible laws for diverse real-world networks. We were able to find programs that are simple enough to lead to an actual understanding of the mechanisms proposed, namely for a simple brain and a social network.
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots
Venue: arXiv cs.RO 2014
Year: 2014

An important capability of autonomous multi-robot systems is to prevent collision among the individual robots. One approach to this problem is to plan conflict-free trajectories and let each of the robots follow its pre-planned trajectory. A widely used practical method for multi-robot trajectory planning is prioritized planning, which has been shown to be effective in practice, but is in general incomplete. Formal analysis of instances that are provably solvable by prioritized planning is still missing. Moreover, prioritized planning is a centralized algorithm, which may be in many situations undesirable. In this paper we a) propose a revised version of prioritized planning and characterize the class of instances that are provably solvable by the algorithm and b) propose an asynchronous decentralized variant of prioritized planning, which maintains the desirable properties of the centralized version and in the same time exploits the distributed computational power of the individual robots, which in most situations allows to find the joint trajectories faster. The experimental evaluation performed on real-world indoor maps shows that a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized algorithm provides solution faster than the previously proposed synchronized decentralized algorithm.
Augmenting recommendation systems using a model of semantically-related terms extracted from user behavior
Venue: arXiv cs.IR 2014
Year: 2014

Common difficulties like the cold-start problem and a lack of sufficient information about users due to their limited interactions have been major challenges for most recommender systems (RS). To overcome these challenges and many similar ones that result in low accuracy (precision and recall) recommendations, we propose a novel system that extracts semantically-related search keywords based on the aggregate behavioral data of many users. These semantically-related search keywords can be used to substantially increase the amount of knowledge about a specific user's interests based upon even a few searches and thus improve the accuracy of the RS. The proposed system is capable of mining aggregate user search logs to discover semantic relationships between key phrases in a manner that is language agnostic, human understandable, and virtually noise-free. These semantically related keywords are obtained by looking at the links between queries of similar users which, we believe, represent a largely untapped source for discovering latent semantic relationships between search terms.
Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures
Venue: arXiv cs.LG 2014
Year: 2014

Model-based methods and deep neural networks have both been tremendously successful paradigms in machine learning. In model-based methods, problem domain knowledge can be built into the constraints of the model, typically at the expense of difficulties during inference. In contrast, deterministic deep neural networks are constructed in such a way that inference is straightforward, but their architectures are generic and it is unclear how to incorporate knowledge. This work aims to obtain the advantages of both approaches. To do so, we start with a model-based approach and an associated inference algorithm, and \emph{unfold} the inference iterations as layers in a deep network. Rather than optimizing the original model, we \emph{untie} the model parameters across layers, in order to create a more powerful network. The resulting architecture can be trained discriminatively to perform accurate inference within a fixed network size. We show how this framework allows us to interpret conventional networks as mean-field inference in Markov random fields, and to obtain new architectures by instead using belief propagation as the inference algorithm. We then show its application to a non-negative matrix factorization model that incorporates the problem-domain knowledge that sound sources are additive. Deep unfolding of this model yields a new kind of non-negative deep neural network, that can be trained using a multiplicative backpropagation-style update algorithm. We present speech enhancement experiments showing that our approach is competitive with conventional neural networks despite using far fewer parameters.
High-Level Requirements Management and Complexity Costs in Automotive Development Projects: A Problem Statement
Venue: arXiv cs.SE 2014
Year: 2014

Effective requirements management plays an important role when it comes to the support of product development teams in the automotive industry. A precise positioning of new cars in the market is based on features and characteristics described as requirements as well as on costs and profits. [Question/problem] However, introducing or changing requirements does not only impact the product and its parts, but may lead to overhead costs in the OEM due to increased complexity. The raised overhead costs may well exceed expected gains or costs from the changed requirements. [Principal ideas/results] By connecting requirements with direct and overhead costs, decision making based on requirements could become more valuable. [Contribution] This problem statement results from a detailed examination of the effects of requirements management practices on process complexity and vice versa as well as on how today's requirements management tools assist in this respect. We present findings from a joined research project of RWTH Aachen University and Volkswagen
Combining the analytical hierarchy process and the genetic algorithm to solve the timetable problem
Venue: arXiv cs.AI 2014
Year: 2014

The main problems of school course timetabling are time, curriculum, and classrooms. In addition there are other problems that vary from one institution to another. This paper is intended to solve the problem of satisfying the teachers preferred schedule in a way that regards the importance of the teacher to the supervising institute, i.e. his score according to some criteria. Genetic algorithm (GA) has been presented as an elegant method in solving timetable problem (TTP) in order to produce solutions with no conflict. In this paper, we consider the analytic hierarchy process (AHP) to efficiently obtain a score for each teacher, and consequently produce a GA-based TTP solution that satisfies most of the teachers preferences.