OpenRaiser/Intern-Atlas huggingface dataset:
Effects of Channel Aging in Massive MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

MIMO communication may provide high spectral efficiency through the deployment of a very large number of antenna elements at the base stations. The gains from massive MIMO communication come from the use of multi-user MIMO on the uplink and downlink, but with a large excess of antennas at the base station compared to the number of served users. Initial work on massive MIMO did not fully address several practical issues associated with its deployment. This paper considers the impact of channel aging on the performance of massive MIMO systems. The effects of channel variation are characterized as a function of different system parameters assuming a simple model for the channel time variations at the transmitter. Channel prediction is proposed to overcome channel aging effects. The analytical results on aging show how capacity is lost due to time variation in the channel. Numerical results in a multicell network show that massive MIMO works even with some channel variation and that channel prediction could partially overcome channel aging effects.
The Story of Telebrain: A multi-performer telematic platform for performatization
Venue: arXiv cs.HC 2013
Year: 2013

This paper presents Telebrain, a browser-based performatization platform invented for organizing real-time telematic performances. Performatization is the human performance of algorithms. When computers and humans performatize cooperatively, the human-computer interaction (HCI) becomes the location of computation. Novel modes of machine-human communication are necessary for organizing performatizations. Telebrain is designed to facilitate machine-human languages. Capitalizing on the ubiquity and cross-platform compatibility of the Internet, Telebrain is an open-source web application supporting PerPL (Performer Programming Language), a human-interpreted configurable language of multi-media instructions used to program performers. Telebrain facilitates a variety of performance disciplines such as music, theater, dance, computational performance, networked scoring (image and audio), prompted improvisation, real-space multi-player gaming, collaborative transdisciplinary karaoke and quantum square-dancing. (http://telebrain.org)
An efficient dynamic ID based remote user authentication scheme using self-certified public keys for multi-server environment
Venue: arXiv cs.CR 2013
Year: 2013

Recently, Li et al. analyzed Lee et al.'s multi-server authentication scheme and proposed a novel smart card and dynamic ID based remote user authentication scheme for multi-server environments. They claimed that their scheme can resist several kinds of attacks. However, through careful analysis, we find that Li et al.'s scheme is vulnerable to stolen smart card and offline dictionary attack, replay attack, impersonation attack and server spoofing attack. By analyzing other similar schemes, we find that the certain type of dynamic ID based multi-server authentication scheme in which only hash functions are used and no registration center participates in the authentication and session key agreement phase is hard to provide perfect efficient and secure authentication. To compensate for these shortcomings, we improve the recently proposed Liao et al.'s multi-server authentication scheme which is based on pairing and self-certified public keys, and propose a novel dynamic ID based remote user authentication scheme for multi-server environments. Liao et al.'s scheme is found vulnerable to offline dictionary attack and denial of service attack, and cannot provide user's anonymity and local password verification. However, our proposed scheme overcomes the shortcomings of Liao et al.'s scheme. Security and performance analyses show the proposed scheme is secure against various attacks and has many excellent features.
Reallocation Problems in Scheduling
Venue: arXiv cs.DS 2013
Year: 2013

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the reallocation cost. We focus on the classic problem of scheduling jobs on a multiprocessor system. Each unit-size job has a time window in which it can be executed. Jobs are dynamically added and removed from the system. We provide an algorithm that maintains a valid schedule, as long as a sufficiently feasible schedule exists. The algorithm reschedules only a total number of O(min{log^* n, log^* Delta}) jobs for each job that is inserted or deleted from the system, where n is the number of active jobs and Delta is the size of the largest window.
Reinforcement Learning for the Soccer Dribbling Task
Venue: arXiv cs.LG 2013
Year: 2013

We propose a reinforcement learning solution to the \emph{soccer dribbling task}, a scenario in which a soccer agent has to go from the beginning to the end of a region keeping possession of the ball, as an adversary attempts to gain possession. While the adversary uses a stationary policy, the dribbler learns the best action to take at each decision point. After defining meaningful variables to represent the state space, and high-level macro-actions to incorporate domain knowledge, we describe our application of the reinforcement learning algorithm \emph{Sarsa} with CMAC for function approximation. Our experiments show that, after the training period, the dribbler is able to accomplish its task against a strong adversary around 58% of the time.
A TimeStamp based Multi-version STM Protocol that satisfies Opacity and Multi-Version Permissiveness
Venue: arXiv cs.DC 2013
Year: 2013

Software Transactional Memory Systems (STM) are a promising alternative to lock based systems for concurrency control in shared memory systems. In multiversion STM systems, each write on a transaction object produces a new version of that object. The advantage obtained by storing multiple versions is that one can ensure that read operations do not fail. Opacity is a commonly used correctness criterion for STM systems. Multi-Version permissive STM system never aborts a read-only transaction. Although many multi-version STM systems have been proposed, to the best of our knowledge none of them have been formally proved to satisfy opacity. In this paper we present a time-stamp based multiversion STM system that satisfies opacity and mv-permissiveness. We formally prove the correctness of the proposed STM system. We also present garbage collection procedure which deletes unwanted versions of the transaction objects and formally prove it correctness.
On Cost-Effective Incentive Mechanisms in Microtask Crowdsourcing
Venue: arXiv cs.GT 2013
Year: 2013

While microtask crowdsourcing provides a new way to solve large volumes of small tasks at a much lower price compared with traditional in-house solutions, it suffers from quality problems due to the lack of incentives. On the other hand, providing incentives for microtask crowdsourcing is challenging since verifying the quality of submitted solutions is so expensive that will negate the advantage of microtask crowdsourcing. We study cost-effective incentive mechanisms for microtask crowdsourcing in this paper. In particular, we consider a model with strategic workers, where the primary objective of a worker is to maximize his own utility. Based on this model, we analyze two basic mechanisms widely adopted in existing microtask crowdsourcing applications and show that, to obtain high quality solutions from workers, their costs are constrained by some lower bounds. We then propose a cost-effective mechanism that employs quality-aware worker training as a tool to stimulate workers to provide high quality solutions. We prove theoretically that the proposed mechanism, when properly designed, can obtain high quality solutions with an arbitrarily low cost. Beyond its theoretical guarantees, we further demonstrate the effectiveness of our proposed mechanisms through a set of behavioral experiments.
On The Optimality of Myopic Sensing in Multi-State Channels
Venue: arXiv cs.SY 2013
Year: 2013

We consider the channel sensing problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and resource constrained jamming. The communication system consists of N channels. Each channel is modeled as a multi-state Markov chain (M.C.). At each time instant a user selects one channel to sense and uses it to transmit information. A reward depending on the state of the selected channel is obtained for each transmission. The objective is to design a channel sensing policy that maximizes the expected total reward collected over a finite or infinite horizon. This problem can be viewed as an instance of a restless bandit problem, for which the form of optimal policies is unknown in general. We discover sets of conditions sufficient to guarantee the optimality of a myopic sensing policy; we show that under one particular set of conditions the myopic policy coincides with the Gittins index rule.
Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty
Venue: arXiv cs.DB 2013
Year: 2013

There is a growing need for methods which can capture uncertainties and answer queries over graph-structured data. Two common types of uncertainty are uncertainty over the attribute values of nodes and uncertainty over the existence of edges. In this paper, we combine those with identity uncertainty. Identity uncertainty represents uncertainty over the mapping from objects mentioned in the data, or references, to the underlying real-world entities. We propose the notion of a probabilistic entity graph (PEG), a probabilistic graph model that defines a distribution over possible graphs at the entity level. The model takes into account node attribute uncertainty, edge existence uncertainty, and identity uncertainty, and thus enables us to systematically reason about all three types of uncertainties in a uniform manner. We introduce a general framework for constructing a PEG given uncertain data at the reference level and develop highly efficient algorithms to answer subgraph pattern matching queries in this setting. Our algorithms are based on two novel ideas: context-aware path indexing and reduction by join-candidates, which drastically reduce the query search space. A comprehensive experimental evaluation shows that our approach outperforms baseline implementations by orders of magnitude.
Tweets Miner for Stock Market Analysis
Venue: arXiv cs.IR 2013
Year: 2013

In this paper, we present a software package for the data mining of Twitter microblogs for the purpose of using them for the stock market analysis. The package is written in R langauge using apropriate R packages. The model of tweets has been considered. We have also compared stock market charts with frequent sets of keywords in Twitter microblogs messages.
Modelling, Reduction and Analysis of Markov Automata (extended version)
Venue: arXiv cs.LO 2013
Year: 2013

Markov automata (MA) constitute an expressive continuous-time compositional modelling formalism. They appear as semantic backbones for engineering frameworks including dynamic fault trees, Generalised Stochastic Petri Nets, and AADL. Their expressive power has thus far precluded them from effective analysis by probabilistic (and statistical) model checkers, stochastic game solvers, or analysis tools for Petri net-like formalisms. This paper presents the foundations and underlying algorithms for efficient MA modelling, reduction using static analysis, and most importantly, quantitative analysis. We also discuss implementation pragmatics of supporting tools and present several case studies demonstrating feasibility and usability of MA in practice.
Temporal Locality in Today's Content Caching: Why it Matters and How to Model it
Venue: arXiv cs.NI 2013
Year: 2013

The dimensioning of caching systems represents a difficult task in the design of infrastructures for content distribution in the current Internet. This paper addresses the problem of defining a realistic arrival process for the content requests generated by users, due its critical importance for both analytical and simulative evaluations of the performance of caching systems. First, with the aid of YouTube traces collected inside operational residential networks, we identify the characteristics of real traffic that need to be considered or can be safely neglected in order to accurately predict the performance of a cache. Second, we propose a new parsimonious traffic model, named the Shot Noise Model (SNM), that enables users to natively capture the dynamics of content popularity, whilst still being sufficiently simple to be employed effectively for both analytical and scalable simulative studies of caching systems. Finally, our results show that the SNM presents a much better solution to account for the temporal locality observed in real traffic compared to existing approaches.
Regression techniques for subspace-based black-box state-space system identification: an overview
Venue: arXiv cs.SY 2013
Year: 2013

As far as the identification of linear time-invariant state-space representation is concerned, among all of the solutions available in the literature, the subspace-based state-space model identification techniques have proved their efficiency in many practical cases since the beginning of the 90's. This paper introduces an overview of these techniques by focusing on their formulation as a least-squares problem. Apart from an article written by J. Qin, to the author's knowledge, such a regression formulation is not totally investigated in the books which can be considered as the references as far as subspace-based identification is concerned. Thus, in this paper, a specific attention is payed to the regression-based techniques used to identify systems working under open-loop as well as closed-loop conditions.
Modelling and Analysing Cargo Screening Processes: A Project Outline
Venue: arXiv cs.AI 2013
Year: 2013

The efficiency of current cargo screening processes at sea and air ports is unknown as no benchmarks exists against which they could be measured. Some manufacturer benchmarks exist for individual sensors but we have not found any benchmarks that take a holistic view of the screening procedures assessing a combination of sensors and also taking operator variability into account. Just adding up resources and manpower used is not an effective way for assessing systems where human decision-making and operator compliance to rules play a vital role. For such systems more advanced assessment methods need to be used, taking into account that the cargo screening process is of a dynamic and stochastic nature. Our project aim is to develop a decision support tool (cargo-screening system simulator) that will map the right technology and manpower to the right commodity-threat combination in order to maximize detection rates. In this paper we present a project outline and highlight the research challenges we have identified so far. In addition we introduce our first case study, where we investigate the cargo screening process at the ferry port in Calais.
Average Consensus on Arbitrary Strongly Connected Digraphs with Time-Varying Topologies
Venue: arXiv cs.SY 2013
Year: 2013

We have recently proposed a "surplus-based" algorithm which solves the multi-agent average consensus problem on general strongly connected and static digraphs. The essence of that algorithm is to employ an additional variable to keep track of the state changes of each agent, thereby achieving averaging even though the state sum is not preserved. In this note, we extend this approach to the more interesting and challenging case of time-varying topologies: An extended surplus-based averaging algorithm is designed, under which a necessary and sufficient graphical condition is derived that guarantees state averaging. The derived condition requires only that the digraphs be arbitrary strongly connected in a \emph{joint} sense, and does not impose "balanced" or "symmetric" properties on the network topology, which is therefore more general than those previously reported in the literature.
Robust Hyperspectral Unmixing with Correntropy based Metric
Venue: arXiv cs.CV 2013
Year: 2013

Hyperspectral unmixing is one of the crucial steps for many hyperspectral applications. The problem of hyperspectral unmixing has proven to be a difficult task in unsupervised work settings where the endmembers and abundances are both unknown. What is more, this task becomes more challenging in the case that the spectral bands are degraded with noise. This paper presents a robust model for unsupervised hyperspectral unmixing. Specifically, our model is developed with the correntropy based metric where the non-negative constraints on both endmembers and abundances are imposed to keep physical significance. In addition, a sparsity prior is explicitly formulated to constrain the distribution of the abundances of each endmember. To solve our model, a half-quadratic optimization technique is developed to convert the original complex optimization problem into an iteratively re-weighted NMF with sparsity constraints. As a result, the optimization of our model can adaptively assign small weights to noisy bands and give more emphasis on noise-free bands. In addition, with sparsity constraints, our model can naturally generate sparse abundances. Experiments on synthetic and real data demonstrate the effectiveness of our model in comparison to the related state-of-the-art unmixing models.
Compositional Verification and Optimization of Interactive Markov Chains
Venue: arXiv cs.LO 2013
Year: 2013

Interactive Markov chains (IMC) are compositional behavioural models extending labelled transition systems and continuous-time Markov chains. We provide a framework and algorithms for compositional verification and optimization of IMC with respect to time-bounded properties. Firstly, we give a specification formalism for IMC. Secondly, given a time-bounded property, an IMC component and the assumption that its unknown environment satisfies a given specification, we synthesize a scheduler for the component optimizing the probability that the property is satisfied in any such environment.
Local and Global Analysis of Parametric Solid Sweeps
Venue: arXiv cs.CG 2013
Year: 2013

In this work, we propose a detailed computational framework for modelling the envelope of the swept volume, that is the boundary of the volume obtained by sweeping an input solid along a trajectory of rigid motions. Our framework is adapted to the well-established industry-standard brep format to enable its implementation in modern CAD systems. This is achieved via a "local analysis", which covers parametrization and singularities, as well as a "global theory" which tackles face-boundaries, self-intersections and trim curves. Central to the local analysis is the "funnel" which serves as a natural parameter space for the basic surfaces constituting the sweep. The trimming problem is reduced to the problem of surface-surface intersections of these basic surfaces. Based on the complexity of these intersections, we introduce a novel classification of sweeps as either decomposable or non-decomposable. Further, we construct an {\em invariant} function $θ$ on the funnel which efficiently separates decomposable and non-decomposable sweeps. Through a geometric theorem we also show intimate connections between $θ$, local curvatures and the inverse trajectory used in earlier works as an approach towards trimming. In contrast to the inverse trajectory approach, $θ$ is robust and is the key to a complete structural understanding, and an efficient computation of both, the singular locus and the trim curves, which are central to a stable implementation. Several illustrative outputs of a pilot implementation are included.
Polynomial Gap Extensions of the Erdős-Pósa Theorem
Venue: arXiv cs.DM 2013
Year: 2013

Given a graph $H$, we denote by ${\cal M}(H)$ all graphs that can be contracted to $H$. The following extension of the Erdős-Pósa Theorem holds: for every $h$-vertex planar graph $H$, there exists a function $f_{H}$ such that every graph $G$, either contains $k$ disjoint copies of graphs in ${\cal M}(H)$, or contains a set of $f_{H}(k)$ vertices meeting every subgraph of $G$ that belongs in ${\cal M}(H)$. In this paper we prove that this is the case for every graph $H$ of pathwidth at most 2 and, in particular, that $f_{H}(k) = 2^{O(h^2)}\cdot k^{2}\cdot \log k$. As a main ingredient of the proof of our result, we show that for every graph $H$ on $h$ vertices and pathwidth at most 2, either $G$ contains $k$ disjoint copies of $H$ as a minor or the treewidth of $G$ is upper-bounded by $2^{O(h^2)}\cdot k^{2}\cdot \log k$. We finally prove that the exponential dependence on $h$ in these bounds can be avoided if $H=K_{2,r}$. In particular, we show that $f_{K_{2,r}}=O(r^2\cdot k^2)$
Modelling Electricity Consumption in Office Buildings: An Agent Based Approach
Venue: arXiv cs.CE 2013
Year: 2013

In this paper, we develop an agent-based model which integrates four important elements, i.e. organisational energy management policies/regulations, energy management technologies, electric appliances and equipment, and human behaviour, to simulate the electricity consumption in office buildings. Based on a case study, we use this model to test the effectiveness of different electricity management strategies, and solve practical office electricity consumption problems. This paper theoretically contributes to an integration of the four elements involved in the complex organisational issue of office electricity consumption, and practically contributes to an application of an agent-based approach for office building electricity consumption study.
Validation of a Microsimulation of the Port of Dover
Venue: arXiv cs.CE 2013
Year: 2013

Modelling and simulating the traffic of heavily used but secure environments such as seaports and airports is of increasing importance. Errors made when simulating these environments can have long standing economic, social and environmental implications. This paper discusses issues and problems that may arise when designing a simulation strategy. Data for the Port is presented, methods for lightweight vehicle assessment that can be used to calibrate and validate simulations are also discussed along with a diagnosis of overcalibration issues. We show that decisions about where the intelligence lies in a system has important repercussions for the reliability of system statistics. Finally, conclusions are drawn about how microsimulations can be moved forward as a robust planning tool for the 21st century.
Theoretical formulation and analysis of the deterministic dendritic cell algorithm
Venue: arXiv cs.NE 2013
Year: 2013

As one of the emerging algorithms in the field of Artificial Immune Systems (AIS), the Dendritic Cell Algorithm (DCA) has been successfully applied to a number of challenging real-world problems. However, one criticism is the lack of a formal definition, which could result in ambiguity for understanding the algorithm. Moreover, previous investigations have mainly focused on its empirical aspects. Therefore, it is necessary to provide a formal definition of the algorithm, as well as to perform runtime analyses to revealits theoretical aspects. In this paper, we define the deterministic version of the DCA, named the dDCA, using set theory and mathematical functions. Runtime analyses of the standard algorithm and the one with additional segmentation are performed. Our analysis suggests that the standard dDCA has a runtime complexity of O(n2) for the worst-case scenario, where n is the number of input data instances. The introduction of segmentation changes the algorithm's worst case runtime complexity to O(max(nN; nz)), for DC population size N with size of each segment z. Finally, two runtime variables of the algorithm are formulated based on the input data, to understand its runtime behaviour as guidelines for further development.