OpenRaiser/Intern-Atlas huggingface dataset:
Beamspace Channel Estimation for Millimeter-Wave Massive MIMO Systems with Lens Antenna Array
Venue: arXiv cs.IT 2016
Year: 2016

By employing the lens antenna array, beamspace MIMO can utilize beam selection to reduce the number of required RF chains in mmWave massive MIMO systems without obvious performance loss. However, to achieve the capacityapproaching performance, beam selection requires the accurate information of beamspace channel of large size, which is challenging, especially when the number of RF chains is limited. To solve this problem, in this paper we propose a reliable support detection (SD)-based channel estimation scheme. Specifically, we propose to decompose the total beamspace channel estimation problem into a series of sub-problems, each of which only considers one sparse channel component. For each channel component, we first reliably detect its support by utilizing the structural characteristics of mmWave beamspace channel. Then, the influence of this channel component is removed from the total beamspace channel estimation problem. After the supports of all channel components have been detected, the nonzero elements of the sparse beamspace channel can be estimated with low pilot overhead. Simulation results show that the proposed SD-based channel estimation outperforms conventional schemes and enjoys satisfying accuracy, even in the low SNR region.
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Venue: arXiv cs.DS 2016
Year: 2016

We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions of nodes and their incident edges. We give worst-case guarantees on the time needed to process a single update (in contrast to related results, the update time is not amortized over a sequence of updates). Our main result is a simple randomized algorithm that for any parameter $c>1$ has a worst-case update time of $O(cn^{2+2/3} \log^{4/3}{n})$ and answers distance queries correctly with probability $1-1/n^c$, against an adaptive online adversary if the graph contains no negative cycle. The best deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time of $\tilde O(n^{2+3/4})$ and assumes non-negative weights. This is the first improvement for this problem for more than a decade. Conceptually, our algorithm shows that randomization along with a more direct approach can provide better bounds.
SBBA: a Strongly-Budget-Balanced Double-Auction Mechanism
Venue: arXiv cs.GT 2016
Year: 2016

In a seminal paper, McAfee (1992) presented the first dominant strategy truthful mechanism for double auction. His mechanism attains nearly optimal gain-from-trade when the market is sufficiently large. However, his mechanism may leave money on the table, since the price paid by the buyers may be higher than the price paid to the sellers. This money is included in the gain-from-trade and in some cases it accounts for almost all the gain-from-trade, leaving almost no gain-from-trade to the traders. We present SBBA: a variant of McAfee's mechanism which is strongly budget-balanced. There is a single price, all money is exchanged between buyers and sellers and no money is left on the table. This means that all gain-from-trade is enjoyed by the traders. We generalize this variant to spatially-distributed markets with transit costs.
Multi-view pattern matching
Venue: arXiv cs.DS 2016
Year: 2016

We introduce the \textit{multi-view pattern matching} problem, where a text can have multiple views. Each view is a string of the same size and drawn from disjoint alphabets. The pattern is drawn from the union of all alphabets. The algorithm we present is an extension of the Horspool algorithm, and in our experiments on synthetic data it shows an $3 \times$ improvement over the naive baseline.
LTE security, protocol exploits and location tracking experimentation with low-cost software radio
Venue: arXiv cs.CR 2016
Year: 2016

The Long Term Evolution (LTE) is the latest mobile standard being implemented globally to provide connectivity and access to advanced services for personal mobile devices. Moreover, LTE networks are considered to be one of the main pillars for the deployment of Machine to Machine (M2M) communication systems and the spread of the Internet of Things (IoT). As an enabler for advanced communications services with a subscription count in the billions, security is of capital importance in LTE. Although legacy GSM (Global System for Mobile Communications) networks are known for being insecure and vulnerable to rogue base stations, LTE is assumed to guarantee confidentiality and strong authentication. However, LTE networks are vulnerable to security threats that tamper availability, privacy and authentication. This manuscript, which summarizes and expands the results presented by the author at ShmooCon 2016 \cite{jover2016lte}, investigates the insecurity rationale behind LTE protocol exploits and LTE rogue base stations based on the analysis of real LTE radio link captures from the production network. Implementation results are discussed from the actual deployment of LTE rogue base stations, IMSI catchers and exploits that can potentially block a mobile device. A previously unknown technique to potentially track the location of mobile devices as they move from cell to cell is also discussed, with mitigations being proposed.
mpEAd: Multi-Population EA Diagrams
Venue: arXiv cs.NE 2016
Year: 2016

Multi-population evolutionary algorithms are, by nature, highly complex and difficult to describe. Even two populations working in concert (or opposition) present a myriad of potential configurations that are often difficult to relate using text alone. Little effort has been made, however, to depict these kinds of systems, relying solely on the simple structural connections (related using ad hoc diagrams) between populations and often leaving out crucial details. In this paper, we propose a notation and accompanying formalism for consistently and powerfully depicting these structures and the relationships within them in an intuitive and consistent way. Using our notation, we examine simple co-evolutionary systems and discover new configurations by the simple process of "drawing on a whiteboard". Finally, we demonstrate that even complex, highly-interconnected systems with large numbers of populations can be understood with ease using the advanced features of our formalism
How to Emulate Web Traffic Using Standard Load Testing Tools
Venue: arXiv cs.PF 2016
Year: 2016

Conventional load-testing tools are based on a fifty-year old time-share computer paradigm where a finite number of users submit requests and respond in a synchronized fashion. Conversely, modern web traffic is essentially asynchronous and driven by an unknown number of users. This difference presents a conundrum for testing the performance of modern web applications. Even when the difference is recognized, performance engineers often introduce modifications to their test scripts based on folklore or hearsay published in various Internet fora, much of which can lead to wrong results. We present a coherent methodology, based on two fundamental principles, for emulating web traffic using a standard load-test environment.
An Empirical Evaluation of doc2vec with Practical Insights into Document Embedding Generation
Venue: arXiv cs.CL 2016
Year: 2016

Recently, Le and Mikolov (2014) proposed doc2vec as an extension to word2vec (Mikolov et al., 2013a) to learn document-level embeddings. Despite promising results in the original paper, others have struggled to reproduce those results. This paper presents a rigorous empirical evaluation of doc2vec over two tasks. We compare doc2vec to two baselines and two state-of-the-art document embedding methodologies. We found that doc2vec performs robustly when using models trained on large external corpora, and can be further improved by using pre-trained word embeddings. We also provide recommendations on hyper-parameter settings for general purpose applications, and release source code to induce document embeddings using our trained doc2vec models.
A Multi-task Deep Network for Person Re-identification
Venue: arXiv cs.CV 2016
Year: 2016

Person re-identification (ReID) focuses on identifying people across different scenes in video surveillance, which is usually formulated as a binary classification task or a ranking task in current person ReID approaches. In this paper, we take both tasks into account and propose a multi-task deep network (MTDnet) that makes use of their own advantages and jointly optimize the two tasks simultaneously for person ReID. To the best of our knowledge, we are the first to integrate both tasks in one network to solve the person ReID. We show that our proposed architecture significantly boosts the performance. Furthermore, deep architecture in general requires a sufficient dataset for training, which is usually not met in person ReID. To cope with this situation, we further extend the MTDnet and propose a cross-domain architecture that is capable of using an auxiliary set to assist training on small target sets. In the experiments, our approach outperforms most of existing person ReID algorithms on representative datasets including CUHK03, CUHK01, VIPeR, iLIDS and PRID2011, which clearly demonstrates the effectiveness of the proposed approach.
Training Skinny Deep Neural Networks with Iterative Hard Thresholding Methods
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks have achieved remarkable success in a wide range of practical problems. However, due to the inherent large parameter space, deep models are notoriously prone to overfitting and difficult to be deployed in portable devices with limited memory. In this paper, we propose an iterative hard thresholding (IHT) approach to train Skinny Deep Neural Networks (SDNNs). An SDNN has much fewer parameters yet can achieve competitive or even better performance than its full CNN counterpart. More concretely, the IHT approach trains an SDNN through following two alternative phases: (I) perform hard thresholding to drop connections with small activations and fine-tune the other significant filters; (II)~re-activate the frozen connections and train the entire network to improve its overall discriminative capability. We verify the superiority of SDNNs in terms of efficiency and classification performance on four benchmark object recognition datasets, including CIFAR-10, CIFAR-100, MNIST and ImageNet. Experimental results clearly demonstrate that IHT can be applied for training SDNN based on various CNN architectures such as NIN and AlexNet.
Assessing and Comparing Mutation-based Fault Localization Techniques
Venue: arXiv cs.SE 2016
Year: 2016

Recent research demonstrated that mutation-based fault localization techniques are relatively accurate and practical. However, these methods have never been compared and have only been assessed with simple hand-seeded faults. Therefore, their actual practicality is questionable when it comes to real-wold faults. To deal with this limitation we asses and compare the two main mutation-based fault localization methods, named Metallaxis and MUSE, on a set of real-world programs and faults. Our results based on three typical evaluation metrics indicate that mutation-based fault localization methods are relatively accurate and provide relevant information to developers. Overall, our result indicate that Metallaxis and MUSE require 18% and 37% of the program statements to find the sought faults. Additionally, both methods locate 50% and 80% of the studied faults when developers inspect 10 and 25 statements.
Partial Diffusion Recursive Least-Squares for Distributed Estimation under Noisy Links Condition
Venue: arXiv cs.DC 2016
Year: 2016

Partial diffusion-based recursive least squares (PDRLS) is an effective method for reducing computational load and power consumption in adaptive network implementation. In this method, each node shares a part of its intermediate estimate vector with its neighbors at each iteration. PDRLS algorithm reduces the internode communications relative to the full-diffusion RLS algorithm. This selection of estimate entries becomes more appealing when the information fuse over noisy links. In this paper, we study the steady-state performance of PDRLS algorithm in presence of noisy links and investigate its convergence in both mean and mean-square senses. We also derive a theoretical expression for its steady-state meansquare deviation (MSD). The simulation results illustrate that the stability conditions for PDRLS under noisy links are not sufficient to guarantee its convergence. Strictly speaking, considering nonideal links condition adds a new complexity to the estimation problem for which the PDRLS algorithm becomes unstable and do not converge for any value of the forgetting factor.
Exploiting Vagueness for Multi-Agent Consensus
Venue: arXiv cs.MA 2016
Year: 2016

A framework for consensus modelling is introduced using Kleene's three valued logic as a means to express vagueness in agents' beliefs. Explicitly borderline cases are inherent to propositions involving vague concepts where sentences of a propositional language may be absolutely true, absolutely false or borderline. By exploiting these intermediate truth values, we can allow agents to adopt a more vague interpretation of underlying concepts in order to weaken their beliefs and reduce the levels of inconsistency, so as to achieve consensus. We consider a consensus combination operation which results in agents adopting the borderline truth value as a shared viewpoint if they are in direct conflict. Simulation experiments are presented which show that applying this operator to agents chosen at random (subject to a consistency threshold) from a population, with initially diverse opinions, results in convergence to a smaller set of more precise shared beliefs. Furthermore, if the choice of agents for combination is dependent on the payoff of their beliefs, this acting as a proxy for performance or usefulness, then the system converges to beliefs which, on average, have higher payoff.
The Memory of Science: Inflation, Myopia, and the Knowledge Network
Venue: arXiv cs.DL 2016
Year: 2016

Science is a growing system, exhibiting ~4% annual growth in publications and ~1.8% annual growth in the number of references per publication. Combined these trends correspond to a 12-year doubling period in the total supply of references, thereby challenging traditional methods of evaluating scientific production, from researchers to institutions. Against this background, we analyzed a citation network comprised of 837 million references produced by 32.6 million publications over the period 1965-2012, allowing for a temporal analysis of the `attention economy' in science. Unlike previous studies, we analyzed the entire probability distribution of reference ages - the time difference between a citing and cited paper - thereby capturing previously overlooked trends. Over this half-century period we observe a narrowing range of attention - both classic and recent literature are being cited increasingly less, pointing to the important role of socio-technical processes. To better understand the impact of exponential growth on the underlying knowledge network we develop a network-based model, featuring the redirection of scientific attention via publications' reference lists, and validate the model against several empirical benchmarks. We then use the model to test the causal impact of real paradigm shifts, thereby providing guidance for science policy analysis. In particular, we show how perturbations to the growth rate of scientific output affects the reference age distribution and the functionality of the vast science citation network as an aid for the search & retrieval of knowledge. In order to account for the inflation of science, our study points to the need for a systemic overhaul of the counting methods used to evaluate citation impact - especially in the case of evaluating science careers, which can span several decades and thus several doubling periods.
Ghosts! A Location-Based Bluetooth LE Mobile Game for Museum Exploration
Venue: arXiv cs.HC 2016
Year: 2016

BLE (Bluetooth Low Energy) is a new wireless communication technology that, thanks to reduced power consumption, promises to facilitate communication between computing devices and help us harness their power in environments and contexts previously untouched by information technology. Museums and other facilities housing various cultural content are a particularly interesting area of application. The University of Cambridge Museums consortium has put considerable effort into researching the potential uses of emerging technologies such as BLE to unlock new experiences enriching the way we engage with cultural information. As a part of this research initiative, our ambition has been to examine the challenges and opportunities introduced by the introduction of a BLE-centred system into the museum context. We present an assessment of the potential offered by this technology and of the design approaches that might yield the best results when developing BLE-centred experiences for museum environments. A pivotal part of our project consisted of designing, developing and evaluating a prototype mobile location-based BLE-centred game. A number of technical problems, such as unstable and fluctuating signal strength, were encountered throughout the project lifecycle. Instead of attempting to eliminate such problems, we argued in favour of embracing them and turning them into a cornerstone of the gameplay. Our study suggested that this alternative seamful design approach yields particularly good results when deploying the technology in public environments. The project outcome also demonstrated the potential of BLE-centred solutions to reach out and engage new demographics, especially children, extending their interest in museum visits.
Stochastic Epidemic Networks with Strategic Link Formation
Venue: arXiv cs.GT 2016
Year: 2016

Understanding cascading failures or epidemics in networks is crucial for developing effective defensive mechanisms for many critical systems and infrastructures (e.g. biological, social and cyber networks). Most of the existing works treat the network topology as being exogenously given and study under what conditions an epidemic breaks out and/or extinguishes. However, if agents are able to strategically decide their connections according to their own self-interest, the network will instead be endogenously formed and evolving. In such systems, the epidemic, agents' strategic decisions and the network structure become complexly coupled and co-evolve. As a result, existing knowledge may no longer be applicable. Built on a continuous time Susceptible-Infected-Susceptible epidemic model with strong mixing, this paper studies stochastic epidemic networks consisting of strategic agents, who decide the number of links to form based on a careful evaluation of its current obtainable benefit and the potential future cost due to infection by forming links. A game theoretical framework is developed to analyze such networks and a number of important insights are obtained. One key result is that whereas an epidemic eventually dies out if the effective spreading rate is sufficiently low in exogenously given networks, it never dies out when agents are strategic regardless of the effective spreading rate. This property leads to reduced achievable system efficiency and considerably different optimal protection mechanisms. Without understanding the strategic behavior of agents, significant security cost may incur.
Integration of Probabilistic Uncertain Information
Venue: arXiv cs.DB 2016
Year: 2016

We study the problem of data integration from sources that contain probabilistic uncertain information. Data is modeled by possible-worlds with probability distribution, compactly represented in the probabilistic relation model. Integration is achieved efficiently using the extended probabilistic relation model. We study the problem of determining the probability distribution of the integration result. It has been shown that, in general, only probability ranges can be determined for the result of integration. In this paper we concentrate on a subclass of extended probabilistic relations, those that are obtainable through integration. We show that under intuitive and reasonable assumptions we can determine the exact probability distribution of the result of integration.
FPGA based hybrid architecture for parallelizing RRT
Venue: arXiv cs.RO 2016
Year: 2016

Field Programmable Gate Arrays(FPGA) exceed the computing power of software based implementations by breaking the paradigm of sequential execution and accomplishing more per clock cycle by enabling hardware level parallelization at an architectural level. Introducing parallel architectures for a computationally intensive algorithm like Rapidly Exploring Random Trees(RRT) will result in an exploration that is fast, dense and uniform. Through a cost function delineated in later sections, FPGA based combinatorial architecture delivers superlative speed-up but consumes very high power while hierarchical architecture delivers relatively lower speed-up with acceptable power consumption levels. To combine the qualities of both, a hybrid architecture, that encompasses both combinatorial and hierarchical architecture, is designed. To determine the number of RRT nodes to be allotted to the combinatorial and hierarchical blocks of the hybrid architecture, a cost function, comprised of fundamentally inversely related speed-up and power parameters, is formulated. This maximization of cost function, with its associated constraints,is then mathematically solved using a modified branch and bound, that leads to optimal allocation of RRT modules to both blocks. It is observed that this hybrid architecture delivers the highest performance-per-watt out of the three architectures for differential, quad-copter and fixed wing kinematics.
Recognition of Triangulation Duals of Simple Polygons With and Without Holes
Venue: arXiv cs.CG 2016
Year: 2016

We investigate the problem of determining if a given graph corresponds to the dual of a triangulation of a simple polygon. This is a graph recognition problem, where in our particular case we wish to recognize a graph which corresponds to the dual of a triangulation of a simple polygon with or without holes and interior points. We show that the difficulty of this problem depends critically on the amount of information given and we give a sharp boundary between the various tractable and intractable versions of the problem.
A Local-Global LDA Model for Discovering Geographical Topics from Social Media
Venue: arXiv cs.IR 2016
Year: 2016

Micro-blogging services can track users' geo-locations when users check-in their places or use geo-tagging which implicitly reveals locations. This "geo tracking" can help to find topics triggered by some events in certain regions. However, discovering such topics is very challenging because of the large amount of noisy messages (e.g. daily conversations). This paper proposes a method to model geographical topics, which can filter out irrelevant words by different weights in the local and global contexts. Our method is based on the Latent Dirichlet Allocation (LDA) model but each word is generated from either a local or a global topic distribution by its generation probabilities. We evaluated our model with data collected from Weibo, which is currently the most popular micro-blogging service for Chinese. The evaluation results demonstrate that our method outperforms other baseline methods in several metrics such as model perplexity, two kinds of entropies and KL-divergence of discovered topics.