OpenRaiser/Intern-Atlas huggingface dataset:
Lempel Ziv Computation In Small Space (LZ-CISS)
Venue: arXiv cs.DS 2015
Year: 2015

For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using $(1+ε) n \lg n + O(n)$ bits (for any positive constant $ε\le 1$) working space (including the space for the output) for any text of size \$n\$ over an integer alphabet in $O(n / ε^{2})$ time.
LazyCtrl: Scalable Network Control for Cloud Data Centers
Venue: arXiv cs.NI 2015
Year: 2015

The advent of software defined networking enables flexible, reliable and feature-rich control planes for data center networks. However, the tight coupling of centralized control and complete visibility leads to a wide range of issues among which scalability has risen to prominence. To address this, we present LazyCtrl, a novel hybrid control plane design for data center networks where network control is carried out by distributed control mechanisms inside independent groups of switches while complemented with a global controller. Our design is motivated by the observation that data center traffic is usually highly skewed and thus edge switches can be grouped according to traffic locality. LazyCtrl aims at bringing laziness to the global controller by dynamically devolving most of the control tasks to independent switch groups to process frequent intra-group events near datapaths while handling rare inter-group or other specified events by the controller. We implement LazyCtrl and build a prototype based on Open vSwich and Floodlight. Trace-driven experiments on our prototype show that an effective switch grouping is easy to maintain in multi-tenant clouds and the central controller can be significantly shielded by staying lazy, with its workload reduced by up to 82%.
A Visual Analytics Approach to Compare Propagation Models in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Numerous propagation models describing social influence in social networks can be found in the literature. This makes the choice of an appropriate model in a given situation difficult. Selecting the most relevant model requires the ability to objectively compare them. This comparison can only be made at the cost of describing models based on a common formalism and yet independent from them. We propose to use graph rewriting to formally describe propagation mechanisms as local transformation rules applied according to a strategy. This approach makes sense when it is supported by a visual analytics framework dedicated to graph rewriting. The paper first presents our methodology to describe some propagation models as a graph rewriting problem. Then, we illustrate how our visual analytics framework allows to interactively manipulate models, and underline their differences based on measures computed on simulation traces.
Aggregation by Provenance Types: A Technique for Summarising Provenance Graphs
Venue: arXiv cs.DB 2015
Year: 2015

As users become confronted with a deluge of provenance data, dedicated techniques are required to make sense of this kind of information. We present Aggregation by Provenance Types, a provenance graph analysis that is capable of generating provenance graph summaries. It proceeds by converting provenance paths up to some length k to attributes, referred to as provenance types, and by grouping nodes that have the same provenance types. The summary also includes numeric values representing the frequency of nodes and edges in the original graph. A quantitative evaluation and a complexity analysis show that this technique is tractable; with small values of k, it can produce useful summaries and can help detect outliers. We illustrate how the generated summaries can further be used for conformance checking and visualization.
A Reference Interpreter for the Graph Programming Language GP 2
Venue: arXiv cs.PL 2015
Year: 2015

GP 2 is an experimental programming language for computing by graph transformation. An initial interpreter for GP 2, written in the functional language Haskell, provides a concise and simply structured reference implementation. Despite its simplicity, the performance of the interpreter is sufficient for the comparative investigation of a range of test programs. It also provides a platform for the development of more sophisticated implementations.
OneMax in Black-Box Models with Several Restrictions
Venue: arXiv cs.NE 2015
Year: 2015

Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity. Our testbed are so-called OneMax functions, a classical set of test functions that is intimately related to classic coin-weighing problems and to the board game Mastermind. We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated memory-restricted as well as its ranking-based black-box complexity for bit strings of length $n$ is only of order $n/\log n$, the combined model does not allow for algorithms being faster than linear in $n$, as can be seen by standard information-theoretic considerations. We show that this linear bound is indeed asymptotically tight. Similar results are obtained for other memory- and offspring-sizes. Our results also apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model, in which only the best-so-far solution can be kept in the memory. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models. Our result enlivens the quest for natural evolutionary algorithms optimizing OneMax in $o(n \log n)$ iterations.
Reachability analysis of first-order definable pushdown systems
Venue: arXiv cs.FL 2015
Year: 2015

We study pushdown systems where control states, stack alphabet, and transition relation, instead of being finite, are first-order definable in a fixed countably-infinite structure. We show that the reachability analysis can be addressed with the well-known saturation technique for the wide class of oligomorphic structures. Moreover, for the more restrictive homogeneous structures, we are able to give concrete complexity upper bounds. We show ample applicability of our technique by presenting several concrete examples of homogeneous structures, subsuming, with optimal complexity, known results from the literature. We show that infinitely many such examples of homogeneous structures can be obtained with the classical wreath product construction.
A Fibrational Approach to Automata Theory
Venue: arXiv cs.FL 2015
Year: 2015

For predual categories C and D we establish isomorphisms between opfibrations representing local varieties of languages in C, local pseudovarieties of D-monoids, and finitely generated profinite D-monoids. The global sections of these opfibrations are shown to correspond to varieties of languages in C, pseudovarieties of D-monoids, and profinite equational theories of D-monoids, respectively. As an application, we obtain a new proof of Eilenberg's variety theorem along with several related results, covering varieties of languages and their coalgebraic modifications, Straubing's C-varieties, fully invariant local varieties, etc., within a single framework.
Hierarchical Composition of Memristive Networks for Real-Time Computing
Venue: arXiv cs.ET 2015
Year: 2015

Advances in materials science have led to physical instantiations of self-assembled networks of memristive devices and demonstrations of their computational capability through reservoir computing. Reservoir computing is an approach that takes advantage of collective system dynamics for real-time computing. A dynamical system, called a reservoir, is excited with a time-varying signal and observations of its states are used to reconstruct a desired output signal. However, such a monolithic assembly limits the computational power due to signal interdependency and the resulting correlated readouts. Here, we introduce an approach that hierarchically composes a set of interconnected memristive networks into a larger reservoir. We use signal amplification and restoration to reduce reservoir state correlation, which improves the feature extraction from the input signals. Using the same number of output signals, such a hierarchical composition of heterogeneous small networks outperforms monolithic memristive networks by at least 20% on waveform generation tasks. On the NARMA-10 task, we reduce the error by up to a factor of 2 compared to homogeneous reservoirs with sigmoidal neurons, whereas single memristive networks are unable to produce the correct result. Hierarchical composition is key for solving more complex tasks with such novel nano-scale hardware.
Definition and Research of Internet Neurology
Venue: arXiv cs.OH 2015
Year: 2015

More and more scientific research shows that there is a close correlation between the Internet and brain science. This paper presents the idea of establishing the Internet neurology, which means to make a cross-contrast between the two in terms of physiology and psychology, so that a complete infrastructure system of the Internet is established, predicting the development trend of the Internet in the future as well as the brain structure and operation mechanism, and providing theoretical support for the generation principle of intelligence, cognition and emotion. It also proposes the viewpoint that the Internet can be divided into Internet neurophysiology, Internet neuropsychology, Brain Internet physiology, Brain Internet psychology and the Internet in cognitive science.
Compressed Sensing Recovery via Nonconvex Shrinkage Penalties
Venue: arXiv cs.IT 2015
Year: 2015

The $\ell^0$ minimization of compressed sensing is often relaxed to $\ell^1$, which yields easy computation using the shrinkage mapping known as soft thresholding, and can be shown to recover the original solution under certain hypotheses. Recent work has derived a general class of shrinkages and associated nonconvex penalties that better approximate the original $\ell^0$ penalty and empirically can recover the original solution from fewer measurements. We specifically examine p-shrinkage and firm thresholding. In this work, we prove that given data and a measurement matrix from a broad class of matrices, one can choose parameters for these classes of shrinkages to guarantee exact recovery of the sparsest solution. We further prove convergence of the algorithm iterative p-shrinkage (IPS) for solving one such relaxed problem.
Large-scale Antenna Operation in Heterogeneous Cloud Radio Access Networks: A Partial Centralization Approach
Venue: arXiv cs.NI 2015
Year: 2015

To satisfy the ever-increasing capacity demand and quality of service (QoS) requirements of users, 5G cellular systems will take the form of heterogeneous networks (HetNets) that consist of macro cells and small cells. To build and operate such systems, mobile operators have given significant attention to cloud radio access networks (C-RANs) due to their beneficial features of performance optimization and cost effectiveness. Along with the architectural enhancement of C-RAN, large-scale antennas (a.k.a. massive MIMO) at cell sites contribute greatly to increased network capacity either with higher spectral efficiency or through permitting many users at once. In this article, we discuss the challenging issues of C-RAN based HetNets (H-CRAN), especially with respect to large-scale antenna operation. We provide an overview of existing C-RAN architectures in terms of large-scale antenna operation and promote a partially centralized approach. This approach reduces, remarkably, fronthaul overheads in CRANs with large-scale antennas. We also provide some insights into its potential and applicability in the fronthaul bandwidthlimited H-CRAN with large-scale antennas.
Classification with Extreme Learning Machine and Ensemble Algorithms Over Randomly Partitioned Data
Venue: arXiv cs.LG 2015
Year: 2015

In this age of Big Data, machine learning based data mining methods are extensively used to inspect large scale data sets. Deriving applicable predictive modeling from these type of data sets is a challenging obstacle because of their high complexity. Opportunity with high data availability levels, automated classification of data sets has become a critical and complicated function. In this paper, the power of applying MapReduce based Distributed AdaBoosting of Extreme Learning Machine (ELM) are explored to build reliable predictive bag of classification models. Thus, (i) dataset ensembles are build; (ii) ELM algorithm is used to build weak classification models; and (iii) build a strong classification model from a set of weak classification models. This training model is applied to the publicly available knowledge discovery and data mining datasets.
Multi-Antenna Relay Aided Wireless Physical Layer Security
Venue: arXiv cs.IT 2015
Year: 2015

With growing popularity of mobile Internet, providing secure wireless services has become a critical issue. Physical layer security (PHY-security) has been recognized as an effective means to enhance wireless security by exploiting wireless medium characteristics, e.g., fading, noise, and interference. A particularly interesting PHY-security technology is cooperative relay due to the fact that it helps to provide distributed diversity and shorten access distance. This article offers a tutorial on various multi-antenna relaying technologies to improve security at physical layer. The state of the art research results on multi-antenna relay aided PHY-security as well as some secrecy performance optimization schemes are presented. In particular, we focus on large-scale MIMO (LS-MIMO) relaying technology, which is effective to tackle various challenging issues for implementing wireless PHY-security, such as short-distance interception without eavesdropper channel state information (CSI) and with imperfect legitimate CSI. Moreover, the future directions are identified for further enhancement of secrecy performance.
Power Talk: How to Modulate Data over a DC Micro Grid Bus using Power Electronics
Venue: arXiv cs.IT 2015
Year: 2015

We introduce a novel communication strategy for DC Micro Grids (MGs), termed power talk, in which the devices communicate by modulating the power levels in the DC bus. The information is transmitted by varying the parameters that the MG units use to control the level of the common bus voltage, while it is received by processing the bus measurements that units perform. This communication is challenged by the fact that the voltage level is subject to random disturbances, as the state of the MG changes with random load variations. We develop a corresponding communication model and address the random voltage fluctuations by using coding strategies that transform the MG into some well-known communication channels. The performance analysis shows that it is possible to mitigate the random voltage level variations and communicate reliably over the MG bus.
An Inference Attack Model for Flow Table Capacity and Usage: Exploiting the Vulnerability of Flow Table Overflow in Software-Defined Network
Venue: arXiv cs.NI 2015
Year: 2015

As the most competitive solution for next-generation network, software-defined network (SDN) and its dominant implementation OpenFlow, are attracting more and more interests. But besides convenience and flexibility, SDN/OpenFlow also introduces new kinds of limitations and security issues. Of these limitations, the most obvious and maybe the most neglected one, is the flow table capacity of SDN/OpenFlow switches. In this paper, we proposed a novel inference attack targeting at SDN/OpenFlow network, which is motivated by the limited flow table capacities of SDN/OpenFlow switches and the following measurable network performance decrease resulting from frequent interactions between data plane and control plane when the flow table is full. To our best knowledge, this is the first proposed inference attack model of this kind for SDN/OpenFlow. We also implemented an inference attack framework according to our model and examined its efficiency and accuracy. The simulation results demonstrate that our framework can infer the network parameters(flow table capacity and flow table usage) with an accuracy of 80% or higher. These findings give us a deeper understanding of SDN/OpenFlow limitations and serve as guidelines to future improvements of SDN/OpenFlow.
A Low-Complexity Message Recovery Method for Compute-and-Forward Relaying
Venue: arXiv cs.IT 2015
Year: 2015

The Compute-and-Forward relaying strategy achieves high computation rates by decoding linear combinations of transmitted messages at intermediate relays. However, if the involved relays independently choose which combinations of the messages to decode, there is no guarantee that the overall system of linear equations is solvable at the destination. In this article it is shown that, for a Gaussian fading channel model with two transmitters and two relays, always choosing the combination that maximizes the computation rate often leads to a case where the original messages cannot be recovered. It is further shown that by limiting the relays to select from carefully designed sets of equations, a solvable system can be guaranteed while maintaining high computation rates. The proposed method has a constant computational complexity and requires no information exchange between the relays.
Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings
Venue: arXiv cs.NE 2015
Year: 2015

While evolutionary algorithms are known to be very successful for a broad range of applications, the algorithm designer is often left with many algorithmic choices, for example, the size of the population, the mutation rates, and the crossover rates of the algorithm. These parameters are known to have a crucial influence on the optimization time, and thus need to be chosen carefully, a task that often requires substantial efforts. Moreover, the optimal parameters can change during the optimization process. It is therefore of great interest to design mechanisms that dynamically choose best-possible parameters. An example for such an update mechanism is the one-fifth success rule for step-size adaption in evolutionary strategies. While in continuous domains this principle is well understood also from a mathematical point of view, no comparable theory is available for problems in discrete domains. In this work we show that the one-fifth success rule can be effective also in discrete settings. We regard the $(1+(λ,λ))$~GA proposed in [Doerr/Doerr/Ebel: From black-box complexity to designing new genetic algorithms, TCS 2015]. We prove that if its population size is chosen according to the one-fifth success rule then the expected optimization time on \textsc{OneMax} is linear. This is better than what \emph{any} static population size $λ$ can achieve and is asymptotically optimal also among all adaptive parameter choices.
A Sharing- and Competition-Aware Framework for Cellular Network Evolution Planning
Venue: arXiv cs.NI 2015
Year: 2015

Mobile network operators are facing the difficult task of significantly increasing capacity to meet projected demand while keeping CAPEX and OPEX down. We argue that infrastructure sharing is a key consideration in operators' planning of the evolution of their networks, and that such planning can be viewed as a stage in the cognitive cycle. In this paper, we present a framework to model this planning process while taking into account both the ability to share resources and the constraints imposed by competition regulation (the latter quantified using the Herfindahl index). Using real-world demand and deployment data, we find that the ability to share infrastructure essentially moves capacity from rural, sparsely populated areas (where some of the current infrastructure can be decommissioned) to urban ones (where most of the next-generation base stations would be deployed), with significant increases in resource efficiency. Tight competition regulation somewhat limits the ability to share but does not entirely jeopardize those gains, while having the secondary effect of encouraging the wider deployment of next-generation technologies.
A Survey of Linguistic Structures for Application-level Fault-Tolerance
Venue: arXiv cs.SE 2015
Year: 2015

The structures for the expression of fault-tolerance provisions into the application software are the central topic of this paper. Structuring techniques answer the questions "How to incorporate fault-tolerance in the application layer of a computer program" and "How to manage the fault-tolerant code". As such, they provide means to control complexity, the latter being a relevant factor for the introduction of design faults. This fact and the ever increasing complexity of today's distributed software justify the need for simple, coherent, and effective structures for the expression of fault-tolerance in the application software. In this text we first define a "base" of structural attributes with which application-level fault-tolerance structures can be qualitatively assessed and compared with each other and with respect to the above mentioned needs. This result is then used to provide an elaborated survey of the state-of-the-art of application-level fault-tolerance structures.
Preprint Serious Game Based Dysphonic Rehabilitation Tool
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on 2015 International Conference on Virtual Rehabilitation (ICVR2015). The purpose of this work is designing and implementing a rehabilitation software for dysphonic patients. Constant training is a key factor for this type of therapy. The patient can play the game as well as conduct the voice training simultaneously guided by therapists at clinic or exercise independently at home. The voice information can be recorded and extracted for evaluating the long-time rehabilitation progress.
Language, Twitter and Academic Conferences
Venue: arXiv cs.SI 2015
Year: 2015

Using Twitter during academic conferences is a way of engaging and connecting an audience inherently multicultural by the nature of scientific collaboration. English is expected to be the lingua franca bridging the communication and integration between native speakers of different mother tongues. However, little research has been done to support this assumption. In this paper we analyzed how integrated language communities are by analyzing the scholars' tweets used in 26 Computer Science conferences over a time span of five years. We found that although English is the most popular language used to tweet during conferences, a significant proportion of people also tweet in other languages. In addition, people who tweet solely in English interact mostly within the same group (English monolinguals), while people who speak other languages tend to show a more diverse interaction with other lingua groups. Finally, we also found that the people who interact with other Twitter users show a more diverse language distribution, while people who do not interact mostly post tweets in a single language. These results suggest a relation between the number of languages a user speaks, which can affect the interaction dynamics of online communities.