OpenRaiser/Intern-Atlas huggingface dataset:
Minimum-Energy Distributed Consensus of Uncertain Agents
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents a consensus algorithm for a multi-agent system where each agent has access to its imperfect own state and neighboring state measurements. The measurements are subject to deterministic disturbances and the proposed algorithm provides a minimum-energy estimate of the measured states which is instrumental in achieving consensus by the nodes. It is shown that the proposed consensus algorithm converges exponentially in the absence of disturbances, and its performance under bounded continuous disturbances is investigated as well. The convergence performance of the proposed method is further studied using simulations where we show that consensus is achieved despite using large measurement errors.
Greedy Sparse Signal Recovery with Tree Pruning
Venue: arXiv cs.IT 2014
Year: 2014

Recently, greedy algorithm has received much attention as a cost-effective means to reconstruct the sparse signals from compressed measurements. Much of previous work has focused on the investigation of a single candidate to identify the support (index set of nonzero elements) of the sparse signals. Well-known drawback of the greedy approach is that the chosen candidate is often not the optimal solution due to the myopic decision in each iteration. In this paper, we propose a greedy sparse recovery algorithm investigating multiple promising candidates via the tree search. Two key ingredients of the proposed algorithm, referred to as the matching pursuit with a tree pruning (TMP), to achieve efficiency in the tree search are the {\it pre-selection} to put a restriction on columns of the sensing matrix to be investigated and the {\it tree pruning} to eliminate unpromising paths from the search tree. In our performance guarantee analysis and empirical simulations, we show that TMP is effective in recovering sparse signals in both noiseless and noisy scenarios.
Multiple-access Fading Channel with Wireless Power Transfer and Energy Harvesting
Venue: arXiv cs.IT 2014
Year: 2014

We consider the achievable average rates of a multiple-access system, which consists of N energy-harvesting users (EHUs) that transmit information over a block fading multiple-access channel (MAC) and a base station (BS) that broadcasts radio frequency (RF) energy to the EHUs for wireless power transfer. The information (over the uplink) and power (over the downlink) can be transmitted either in time division duplex or frequency division duplex. For the case when the EHUs battery capacities and the number of transmission slots are both infinite, we determine the optimal power allocation for the BS and the optimal rates and power allocations for the EHUs that maximize the achievable rate region of the MAC. The resulting online solution is asymptotically optimal, and also applicable for a finite number of transmission slots and finite battery capacities.
On the Impact of Multiobjective Scalarizing Functions
Venue: arXiv cs.AI 2014
Year: 2014

Recently, there has been a renewed interest in decomposition-based approaches for evolutionary multiobjective optimization. However, the impact of the choice of the underlying scalarizing function(s) is still far from being well understood. In this paper, we investigate the behavior of different scalarizing functions and their parameters. We thereby abstract firstly from any specific algorithm and only consider the difficulty of the single scalarized problems in terms of the search ability of a (1+lambda)-EA on biobjective NK-landscapes. Secondly, combining the outcomes of independent single-objective runs allows for more general statements on set-based performance measures. Finally, we investigate the correlation between the opening angle of the scalarizing function's underlying contour lines and the position of the final solution in the objective space. Our analysis is of fundamental nature and sheds more light on the key characteristics of multiobjective scalarizing functions.
Intel Cilk Plus for Complex Parallel Algorithms: "Enormous Fast Fourier Transform" (EFFT) Library
Venue: arXiv cs.MS 2014
Year: 2014

In this paper we demonstrate the methodology for parallelizing the computation of large one-dimensional discrete fast Fourier transforms (DFFTs) on multi-core Intel Xeon processors. DFFTs based on the recursive Cooley-Tukey method have to control cache utilization, memory bandwidth and vector hardware usage, and at the same time scale across multiple threads or compute nodes. Our method builds on single-threaded Intel Math Kernel Library (MKL) implementation of DFFT, and uses the Intel Cilk Plus framework for thread parallelism. We demonstrate the ability of Intel Cilk Plus to handle parallel recursion with nested loop-centric parallelism without tuning the code to the number of cores or cache metrics. The result of our work is a library called EFFT that performs 1D DFTs of size 2^N for N>=21 faster than the corresponding Intel MKL parallel DFT implementation by up to 1.5x, and faster than FFTW by up to 2.5x. The code of EFFT is available for free download under the GPLv3 license. This work provides a new efficient DFFT implementation, and at the same time demonstrates an educational example of how computer science problems with complex parallel patterns can be optimized for high performance using the Intel Cilk Plus framework.
Attributes for Causal Inference in Longitudinal Observational Databases
Venue: arXiv cs.CE 2014
Year: 2014

The pharmaceutical industry is plagued by the problem of side effects that can occur anytime a prescribed medication is ingested. There has been a recent interest in using the vast quantities of medical data available in longitudinal observational databases to identify causal relationships between drugs and medical events. Unfortunately the majority of existing post marketing surveillance algorithms measure how dependant or associated an event is on the presence of a drug rather than measuring causality. In this paper we investigate potential attributes that can be used in causal inference to identify side effects based on the Bradford-Hill causality criteria. Potential attributes are developed by considering five of the causality criteria and feature selection is applied to identify the most suitable of these attributes for detecting side effects. We found that attributes based on the specificity criterion may improve side effect signalling algorithms but the experiment and dosage criteria attributes investigated in this paper did not offer sufficient additional information.
Homotopy Bisimilarity for Higher-Dimensional Automata
Venue: arXiv cs.LO 2014
Year: 2014

We introduce a new category of higher-dimensional automata in which the morphisms are functional homotopy simulations, i.e. functional simulations up to concurrency of independent events. For this, we use unfoldings of higher-dimensional automata into higher-dimensional trees. Using a notion of open maps in this category, we define homotopy bisimilarity. We show that homotopy bisimilarity is equivalent to a straight-forward generalization of standard bisimilarity to higher dimensions, and that it is finer than split bisimilarity and incomparable with history-preserving bisimilarity.
Capturing "attrition intensifying" structural traits from didactic interaction sequences of MOOC learners
Venue: arXiv cs.CY 2014
Year: 2014

This work is an attempt to discover hidden structural configurations in learning activity sequences of students in Massive Open Online Courses (MOOCs). Leveraging combined representations of video clickstream interactions and forum activities, we seek to fundamentally understand traits that are predictive of decreasing engagement over time. Grounded in the interdisciplinary field of network science, we follow a graph based approach to successfully extract indicators of active and passive MOOC participation that reflect persistence and regularity in the overall interaction footprint. Using these rich educational semantics, we focus on the problem of predicting student attrition, one of the major highlights of MOOC literature in the recent years. Our results indicate an improvement over a baseline ngram based approach in capturing "attrition intensifying" features from the learning activities that MOOC learners engage in. Implications for some compelling future research are discussed.
Computing the Least-core and Nucleolus for Threshold Cardinality Matching Games
Venue: arXiv cs.GT 2014
Year: 2014

Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. \emph{Core}, \emph{least-core} and \emph{nucleolus} are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues on the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph $G=(V,E)$ and a threshold $T$, in which the player set is $V$ and the profit of a coalition $S\subseteq V$ is 1 if the size of a maximum matching in $G[S]$ meets or exceeds $T$, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial time solvable. We also provide a general characterization of the least core for a large class of TCMG. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold $T$ equals $1$. When the threshold $T$ is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.
Online Privacy as a Collective Phenomenon
Venue: arXiv cs.CY 2014
Year: 2014

The problem of online privacy is often reduced to individual decisions to hide or reveal personal information in online social networks (OSNs). However, with the increasing use of OSNs, it becomes more important to understand the role of the social network in disclosing personal information that a user has not revealed voluntarily: How much of our private information do our friends disclose about us, and how much of our privacy is lost simply because of online social interaction? Without strong technical effort, an OSN may be able to exploit the assortativity of human private features, this way constructing shadow profiles with information that users chose not to share. Furthermore, because many users share their phone and email contact lists, this allows an OSN to create full shadow profiles for people who do not even have an account for this OSN. We empirically test the feasibility of constructing shadow profiles of sexual orientation for users and non-users, using data from more than 3 Million accounts of a single OSN. We quantify a lower bound for the predictive power derived from the social network of a user, to demonstrate how the predictability of sexual orientation increases with the size of this network and the tendency to share personal information. This allows us to define a privacy leak factor that links individual privacy loss with the decision of other individuals to disclose information. Our statistical analysis reveals that some individuals are at a higher risk of privacy loss, as prediction accuracy increases for users with a larger and more homogeneous first- and second-order neighborhood of their social network. While we do not provide evidence that shadow profiles exist at all, our results show that disclosing of private information is not restricted to an individual choice, but becomes a collective decision that has implications for policy and privacy regulation.
Accuracy Improvement of Robot-Based Milling Using an Enhanced Manipulator Model
Venue: arXiv cs.RO 2014
Year: 2014

The paper is devoted to the accuracy improvement of robot-based milling by using an enhanced manipulator model that takes into account both geometric and elastostatic factors. Particular attention is paid to the model parameters identification accuracy. In contrast to other works, the proposed approach takes into account impact of the gravity compensator and link weights on the manipulator elastostatic properties. In order to improve the identification accuracy, the industry oriented performance measure is used to define optimal measurement configurations and an enhanced partial pose measurement method is applied for the identification of the model parameters. The advantages of the developed approach are confirmed by experimental results that deal with the elastostatic calibration of a heavy industrial robot used for milling. The achieved accuracy improvement factor is about 2.4.
Neighborhood Selection and Rules Identification for Cellular Automata: A Rough Sets Approach
Venue: arXiv cs.AI 2014
Year: 2014

In this paper a method is proposed which uses data mining techniques based on rough sets theory to select neighborhood and determine update rule for cellular automata (CA). According to the proposed approach, neighborhood is detected by reducts calculations and a rule-learning algorithm is applied to induce a set of decision rules that define the evolution of CA. Experiments were performed with use of synthetic as well as real-world data sets. The results show that the introduced method allows identification of both deterministic and probabilistic CA-based models of real-world phenomena.
A direct proof for Lovett's bound on the communication complexity of low rank matrices
Venue: arXiv cs.CC 2014
Year: 2014

The log-rank conjecture in communication complexity suggests that the deterministic communication complexity of any Boolean rank-r function is bounded by polylog(r). Recently, major progress was made by Lovett who proved that the communication complexity is bounded by O(r^1/2 * log r). Lovett's proof is based on known estimates on the discrepancy of low-rank matrices. We give a simple, direct proof based on a hyperplane rounding argument that in our opinion sheds more light on the reason why a root factor suffices and what is necessary to improve on this factor.
Truth Discovery Algorithms: An Experimental Evaluation
Venue: arXiv cs.DB 2014
Year: 2014

A fundamental problem in data fusion is to determine the veracity of multi-source data in order to resolve conflicts. While previous work in truth discovery has proved to be useful in practice for specific settings, sources' behavior or data set characteristics, there has been limited systematic comparison of the competing methods in terms of efficiency, usability, and repeatability. We remedy this deficit by providing a comprehensive review of 12 state-of-the art algorithms for truth discovery. We provide reference implementations and an in-depth evaluation of the methods based on extensive experiments on synthetic and real-world data. We analyze aspects of the problem that have not been explicitly studied before, such as the impact of initialization and parameter setting, convergence, and scalability. We provide an experimental framework for extensively comparing the methods in a wide range of truth discovery scenarios where source coverage, numbers and distributions of conflicts, and true positive claims can be controlled and used to evaluate the quality and performance of the algorithms. Finally, we report comprehensive findings obtained from the experiments and provide new insights for future research.
Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees
Venue: arXiv cs.DS 2014
Year: 2014

In a directed graph $G$ with non-correlated edge lengths and costs, the \emph{network design problem with bounded distances} asks for a cost-minimal spanning subgraph subject to a length bound for all node pairs. We give a bi-criteria $(2+\varepsilon,O(n^{0.5+\varepsilon}))$-approximation for this problem. This improves on the currently best known linear approximation bound, at the cost of violating the distance bound by a factor of at most~$2+\varepsilon$. In the course of proving this result, the related problem of \emph{directed shallow-light Steiner trees} arises as a subproblem. In the context of directed graphs, approximations to this problem have been elusive. We present the first non-trivial result by proposing a $(1+\varepsilon,O(|R|^{\varepsilon}))$-ap\-proxi\-ma\-tion, where $R$ are the terminals. Finally, we show how to apply our results to obtain an $(α+\varepsilon,O(n^{0.5+\varepsilon}))$-approximation for \emph{light-weight directed $α$-spanners}. For this, no non-trivial approximation algorithm has been known before. All running times depends on $n$ and $\varepsilon$ and are polynomial in $n$ for any fixed $\varepsilon>0$.
A Single-Processor Approach to Speech Processing Pipeline of Bilateral Cochlear Implants
Venue: arXiv cs.SD 2014
Year: 2014

This dissertation covers a single-processor approach to the speech processing pipeline of bilateral Cochlear Implants (CIs). The use of only a single processor to provide binaural stimulation signals overcomes the synchronization problem, which is an existing challenging problem in the deployment of bilateral CI devices. The developed single-processor speech processing pipeline provides CI users with a sense of directionality. Its non-synchronization feature as well as low computational and memory requirements make it a suitable solution for actual deployment. A speech enhancement framework is developed that incorporates different non-Euclidean speech distortion criteria and different noise environments. This framework not only allows the design of environment-optimized parameters but also enables a user-specific solution where the anthropometric measurements of an individual user are incorporated into the training process to obtain individualized bilateral parameters. The developed techniques are primarily meant for bilateral CIs, however, they are general purpose in the sense that they are also applicable to binaural hearing aids, bimodal devices having hearing aid in one ear and cochlear implant in the other ear as well as dual-channel speech enhancement applications. Extensive experiments have shown the effectiveness of the developed solution in six commonly encountered noise environments compared to a similar one-channel pipeline when using two separate processors or when using independent sequential processing.
Modeling Language Variability
Venue: arXiv cs.SE 2014
Year: 2014

A systematic way of defining variants of a modeling language is useful for adapting the language to domain or project specific needs. Variants can be obtained by adapting the syntax or semantics of the language. In this paper, we take a formal approach to define modeling language variability and show how this helps to reason about language variants, models, and their semantics formally. We introduce the notion of semantic language refinement meaning that one semantics variant is implied by another. Leaving open all variation points that a modeling language offers yields the notion of the inner semantics of that language. Properties of the modeling language which do not depend on the selection of specific variants are called invariant language properties with respect to a variation point. These properties consequently follow from the inner semantics of a model or language.
Measuring the Ability to Form a Product Line from Existing Products
Venue: arXiv cs.SE 2014
Year: 2014

A product line approach can save valuable resources by reusing artifacts. Especially for software artifacts, the reuse of existing components is highly desirable. In recent literature, the creation of software product lines is mainly proposed from a top-down point of view regarding features which are visible by customers. In practice, however, the design for a product line often arises from one or few existing products that descend from a very first product starting with copy-paste and evolving individually. In this contribution, we propose the theoretical basis to derive a set of metrics for evaluating similar software products in an objective manner. These metrics are used to evaluate the set of product's ability to form a product line.
Variability within Modeling Language Definitions
Venue: arXiv cs.SE 2014
Year: 2014

We present a taxonomy of the variability mechanisms offered by modeling languages. The definition of a formal language encompasses a syntax and a semantic domain as well as the mapping that relates them, thus language variabilities are classified according to which of those three pillars they address. This work furthermore proposes a framework to explicitly document and manage the variation points and their corresponding variants of a variable modeling language. The framework enables the systematic study of various kinds of variabilities and their interdependencies. Moreover, it allows a methodical customization of a language, for example, to a given application domain. The taxonomy of variability is explicitly of interest for the UML to provide a more precise understanding of its variation points.
Limitations of Agile Software Processes
Venue: arXiv cs.SE 2014
Year: 2014

Software developers and project managers are struggling to assess the appropriateness of agile processes to their development environments. This paper identifies limitations that apply to many of the published agile processes in terms of the types of projects in which their application may be problematic.
A New Skill Based Robot Programming Language Using UML/P Statecharts
Venue: arXiv cs.SE 2014
Year: 2014

This paper introduces the new robot programming language LightRocks (Light Weight Robot Coding for Skills), a domain specific language (DSL) for robot programming. The language offers three different level of abstraction for robot programming. On lowest level skills are coded by domain experts. On a more abstract level these skills are supposed to be combined by shop floor workers or technicians to define tasks. The language is designed to allow as much flexibility as necessary on the lowest level of abstraction and is kept as simple as possible with the more abstract layers. A Statechart like model is used to describe the different levels of detail. For this we apply the UML/P and the language workbench MontiCore. To this end we are able to generate code while hiding controller specific implementation details. In addition the development in LightRocks is supported by a generic graphical editor implemented as an Eclipse plugin.
Model Transformations in Practice Workshop (MTiP)
Venue: arXiv cs.SE 2014
Year: 2014

Model Transformations in Practice (MTiP) 2005 was a workshop which provided a forum for the model transformation community to discuss practical model transformation issues. Although many different model transformation approaches have been proposed and explored in recent years, there has been little work on comparing and contrasting various approaches. Without such comparisons, it is hard to assess new model transformation approaches such as the upcoming OMG MOF/QVT recommendation, or to discern sensible future paths for the area. Our aims with the workshop were to create a forum that would help lead to an increased understanding of the relative merits of different model transformation techniques and approaches. A more advanced understanding of such merits is of considerable benefit to both the model transformation and wider modelling communities.
Model-Driven Development of Complex Software: A Research Roadmap
Venue: arXiv cs.SE 2014
Year: 2014

The term Model-Driven Engineering (MDE) is typically used to describe software development approaches in which abstract models of software systems are created and systematically transformed to concrete implementations. In this paper we give an overview of current research in MDE and discuss some of the major challenges that must be tackled in order to realize the MDE vision of software development. We argue that full realizations of the MDE vision may not be possible in the near to medium-term primarily because of the wicked problems involved. On the other hand, attempting to realize the vision will provide insights that can be used to significantly reduce the gap between evolving software complexity and the technologies used to manage complexity.