OpenRaiser/Intern-Atlas huggingface dataset:
Massive MIMO testbed - Implementation and Initial Results in System Model Validation
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents the design and implementation of a novel SDR based massive MIMO testbed with up to 70 nodes built at Tennessee Technological University. The deployment can reach a $30 \times 30$ antenna MIMO scheme. With this testbed, we are able to measure the channel matrix and compute the achievable rate of the massive MIMO system using experimental data. The measured channel capacity is linearly increasing with the number of antennas of the base station. We also demonstrate the channel reciprocity including the circuits impact from the transmitter and receiver. We show that the Vandermonde channel model is more realistic to describe the massive MIMO architecture than the widely used Gaussian channel model, in terms of capacity. By adjusting the range for angle of arrival $α$ and the base station antenna distance $d$ during the simulation, we find out the Vandermonde model agrees with our measured capacity at a certain $α$ for each selected $d$ and the $α$ is very close to that of the experiment deployment. It is the first time that the feasibility of Vandermonde channel model is demonstrated by the experiment for massive MIMO.
Methods and Metrics for Fair Server Assessment under Real-Time Financial Workloads
Venue: arXiv cs.DC 2014
Year: 2014

Energy efficiency has been a daunting challenge for datacenters. The financial industry operates some of the largest datacenters in the world. With increasing energy costs and the financial services sector growth, emerging financial analytics workloads may incur extremely high operational costs, to meet their latency targets. Microservers have recently emerged as an alternative to high-end servers, promising scalable performance and low energy consumption in datacenters via scale-out. Unfortunately, stark differences in architectural features, form factor and design considerations make a fair comparison between servers and microservers exceptionally challenging. In this paper we present a rigorous methodology and new metrics for fair comparison of server and microserver platforms. We deploy our methodology and metrics to compare a microserver with ARM cores against two servers with x86 cores, running the same real-time financial analytics workload. We define workload-specific but platform-independent performance metrics for platform comparison, targeting both datacenter operators and end users. Our methodology establishes that a server based the Xeon Phi processor delivers the highest performance and energy-efficiency. However, by scaling out energy-efficient microservers, we achieve competitive or better energy-efficiency than a power-equivalent server with two Sandy Bridge sockets despite the microserver's slower cores. Using a new iso-QoS (iso-Quality of Service) metric, we find that the ARM microserver scales enough to meet market throughput demand, i.e. a 100% QoS in terms of timely option pricing, with as little as 55% of the energy consumed by the Sandy Bridge server.
Joint Downlink Cell Association and Bandwidth Allocation for Wireless Backhauling in Two-Tier HetNets with Large-Scale Antenna Arrays
Venue: arXiv cs.NI 2014
Year: 2014

The problem of joint downlink cell association (CA) and wireless backhaul bandwidth allocation (WBBA) in two-tier cellular heterogeneous networks (HetNets) is considered. Large-scale antenna array is implemented at the macro base station (BS), while the small cells within the macro cell range are single-antenna BSs and they rely on over-the-air links to the macro BS for backhauling. A sum logarithmic user rate maximization problem is investigated considering wireless backhauling constraints. A duplex and spectrum sharing scheme based on co-channel reverse time-division duplex (TDD) and dynamic soft frequency reuse (SFR) is proposed for interference management in two-tier HetNets with large-scale antenna arrays at the macro BS and wireless backhauling for small cells. Two in-band WBBA scenarios, namely, unified bandwidth allocation and per-small-cell bandwidth allocation scenarios, are investigated for joint CA-WBBA in the HetNet. A two-level hierarchical decomposition method for relaxed optimization is employed to solve the mixed-integer nonlinear program (MINLP). Solutions based on the General Algorithm Modeling System (GAMS) optimization solver and fast heuristics are also proposed for cell association in the per-small-cell WBBA scenario. It is shown that when all small cells have to use in-band wireless backhaul, the system load has more impact on both the sum log-rate and per-user rate performance than the number of small cells deployed within the macro cell range. The proposed joint CA-WBBA algorithms have an optimal load approximately equal to the size of the large-scale antenna array at the macro BS. The cell range expansion (CRE) strategy, which is an efficient cell association scheme for HetNets with perfect backhauling, is shown to be inefficient when in-band wireless backhauling for small cells comes into play.
Expected number of uniformly distributed balls in a most loaded bin using placement with simple linear functions
Venue: arXiv cs.DS 2014
Year: 2014

We estimate the size of a most loaded bin in the setting when the balls are placed into the bins using a random linear function in a finite field. The balls are chosen from a transformed interval. We show that in this setting the expected load of the most loaded bins is constant. This is an interesting fact because using fully random hash functions with the same class of input sets leads to an expectation of $Θ\left(\frac{\log m}{\log \log m}\right)$ balls in most loaded bins where $m$ is the number of balls and bins. Although the family of the functions is quite common the size of largest bins was not known even in this simple case.
Error Correction in Polynomial Remainder Codes with Non-Pairwise Coprime Moduli and Robust Chinese Remainder Theorem for Polynomials
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates polynomial remainder codes with non-pairwise coprime moduli. We first consider a robust reconstruction problem for polynomials from erroneous residues when the degrees of all residue errors are assumed small, namely robust Chinese Remainder Theorem (CRT) for polynomials. It basically says that a polynomial can be reconstructed from erroneous residues such that the degree of the reconstruction error is upper bounded by $τ$ whenever the degrees of all residue errors are upper bounded by $τ$, where a sufficient condition for $τ$ and a reconstruction algorithm are obtained. By releasing the constraint that all residue errors have small degrees, another robust reconstruction is then presented when there are multiple unrestricted errors and an arbitrary number of errors with small degrees in the residues. By making full use of redundancy in moduli, we obtain a stronger residue error correction capability in the sense that apart from the number of errors that can be corrected in the previous existing result, some errors with small degrees can be also corrected in the residues. With this newly obtained result, improvements in uncorrected error probability and burst error correction capability in a data transmission are illustrated.
Reinforcement Learning and Nonparametric Detection of Game-Theoretic Equilibrium Play in Social Networks
Venue: arXiv cs.GT 2014
Year: 2014

This paper studies two important signal processing aspects of equilibrium behavior in non-cooperative games arising in social networks, namely, reinforcement learning and detection of equilibrium play. The first part of the paper presents a reinforcement learning (adaptive filtering) algorithm that facilitates learning an equilibrium by resorting to diffusion cooperation strategies in a social network. Agents form homophilic social groups, within which they exchange past experiences over an undirected graph. It is shown that, if all agents follow the proposed algorithm, their global behavior is attracted to the correlated equilibria set of the game. The second part of the paper provides a test to detect if the actions of agents are consistent with play from the equilibrium of a concave potential game. The theory of revealed preference from microeconomics is used to construct a non-parametric decision test and statistical test which only require the probe and associated actions of agents. A stochastic gradient algorithm is given to optimize the probe in real time to minimize the Type-II error probabilities of the detection test subject to specified Type-I error probability. We provide a real-world example using the energy market, and a numerical example to detect malicious agents in an online social network.
Challenges and characterization of a Biological system on Grid by means of the PhyloGrid application
Venue: arXiv cs.CE 2014
Year: 2014

In this work we present a new application that is being developed. PhyloGrid is able to perform large-scale phylogenetic calculations as those that have been made for estimating the phylogeny of all the sequences already stored in the public NCBI database. The further analysis has been focused on checking the origin of the HIV-1 disease by means of a huge number of sequences that sum up to 2900 taxa. Such a study has been able to be done by the implementation of a workflow in Taverna.
One-Pass, One-Hash n-Gram Statistics Estimation
Venue: arXiv cs.DB 2014
Year: 2014

In multimedia, text or bioinformatics databases, applications query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is sufficient for accurate estimates if the hashing is sufficiently independent. To reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our running times with exact counts using suffix arrays and show that, while we use hardly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass/one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.
Corpus sp{é}cialis{é} et ressource de sp{é}cialit{é}
Venue: arXiv cs.IR 2015
Year: 2015

"Semantic Atlas" is a mathematic and statistic model to visualise word senses according to relations between words. The model, that has been applied to proximity relations from a corpus, has shown its ability to distinguish word senses as the corpus' contributors comprehend them. We propose to use the model and a specialised corpus in order to create automatically a specialised dictionary relative to the corpus' domain. A morpho-syntactic analysis performed on the corpus makes it possible to create the dictionary from syntactic relations between lexical units. The semantic resource can be used to navigate semantically - and not only lexically - through the corpus, to create classical dictionaries or for diachronic studies of the language.
$α$-Discounting Multi-Criteria Decision Making ($α$-D MCDM)
Venue: arXiv cs.AI 2015
Year: 2015

In this book we introduce a new procedure called α-Discounting Method for Multi-Criteria Decision Making (α-D MCDM), which is as an alternative and extension of Saaty Analytical Hierarchy Process (AHP). It works for any number of preferences that can be transformed into a system of homogeneous linear equations. A degree of consistency (and implicitly a degree of inconsistency) of a decision-making problem are defined. α-D MCDM is afterwards generalized to a set of preferences that can be transformed into a system of linear and or non-linear homogeneous and or non-homogeneous equations and or inequalities. The general idea of α-D MCDM is to assign non-null positive parameters α_1, α_2, and so on α_p to the coefficients in the right-hand side of each preference that diminish or increase them in order to transform the above linear homogeneous system of equations which has only the null-solution, into a system having a particular non-null solution. After finding the general solution of this system, the principles used to assign particular values to all parameters αis the second important part of α-D, yet to be deeper investigated in the future. In the current book we propose the Fairness Principle, i.e. each coefficient should be discounted with the same percentage (we think this is fair: not making any favoritism or unfairness to any coefficient), but the reader can propose other principles. For consistent decision-making problems with pairwise comparisons, α-Discounting Method together with the Fairness Principle give the same result as AHP. But for weak inconsistent decision-making problem, α-Discounting together with the Fairness Principle give a different result from AHP. Many consistent, weak inconsistent, and strong inconsistent examples are given in this book.
On Flat Polyhedra deriving from Alexandrov's Theorem
Venue: arXiv cs.CG 2015
Year: 2015

We show that there is a straightforward algorithm to determine if the polyhedron guaranteed to exist by Alexandrov's gluing theorem is a degenerate flat polyhedron, and to reconstruct it from the gluing instructions. The algorithm runs in O(n^3) time for polygons whose gluings are specified by n labels.
Actor Model of Computation: Scalable Robust Information Systems
Venue: arXiv cs.PL 2015
Year: 2015

The Actor model is a mathematical theory that treats "Actors" as the universal primitives of concurrent digital computation. The model has been used both as a framework for a theoretical understanding of concurrency, and as the theoretical basis for several practical implementations of concurrent systems. Unlike previous models of computation, the Actor model was inspired by physical laws. It was also influenced by the programming languages Lisp, Simula 67 and Smalltalk-72, as well as ideas for Petri Nets, capability-based systems and packet switching. The advent of massive concurrency through client-cloud computing and many-core computer architectures has galvanized interest in the Actor model. Actor technology will see significant application for integrating all kinds of digital information for individuals, groups, and organizations so their information usefully links together. Information integration needs to make use of the following information system principles: * Persistence. Information is collected and indexed. * Concurrency: Work proceeds interactively and concurrently, overlapping in time. * Quasi-commutativity: Information can be used regardless of whether it initiates new work or become relevant to ongoing work. * Sponsorship: Sponsors provide resources for computation, i.e., processing, storage, and communications. * Pluralism: Information is heterogeneous, overlapping and often inconsistent. * Provenance: The provenance of information is carefully tracked and recorded The Actor Model is intended to provide a foundation for inconsistency robust information integration
A note on revelation principle from an energy perspective
Venue: arXiv cs.GT 2015
Year: 2015

The revelation principle has been known in the economics society for decades. In this paper, I will investigate it from an energy perspective, i.e., considering the energy consumed by agents and the designer in participating a mechanism. The main result is that when the strategies of agents are actions rather than messages, an additional energy condition should be added to make the revelation principle hold in the real world.
Stochastic Analysis of a Churn-Tolerant Structured Peer-to-Peer Scheme
Venue: arXiv cs.DC 2015
Year: 2015

We present and analyze a simple and general scheme to build a churn (fault)-tolerant structured Peer-to-Peer (P2P) network. Our scheme shows how to "convert" a static network into a dynamic distributed hash table(DHT)-based P2P network such that all the good properties of the static network are guaranteed with high probability (w.h.p). Applying our scheme to a cube-connected cycles network, for example, yields a $O(\log N)$ degree connected network, in which every search succeeds in $O(\log N)$ hops w.h.p., using $O(\log N)$ messages, where $N$ is the expected stable network size. Our scheme has an constant storage overhead (the number of nodes responsible for servicing a data item) and an $O(\log N)$ overhead (messages and time) per insertion and essentially no overhead for deletions. All these bounds are essentially optimal. While DHT schemes with similar guarantees are already known in the literature, this work is new in the following aspects: (1) It presents a rigorous mathematical analysis of the scheme under a general stochastic model of churn and shows the above guarantees; (2) The theoretical analysis is complemented by a simulation-based analysis that validates the asymptotic bounds even in moderately sized networks and also studies performance under changing stable network size; (3) The presented scheme seems especially suitable for maintaining dynamic structures under churn efficiently. In particular, we show that a spanning tree of low diameter can be efficiently maintained in constant time and logarithmic number of messages per insertion or deletion w.h.p. Keywords: P2P Network, DHT Scheme, Churn, Dynamic Spanning Tree, Stochastic Analysis.
Weighted Random Sampling over Data Streams
Venue: arXiv cs.DS 2015
Year: 2015

In this work, we present a comprehensive treatment of weighted random sampling (WRS) over data streams. More precisely, we examine two natural interpretations of the item weights, describe an existing algorithm for each case ([2, 4]), discuss sampling with and without replacement and show adaptations of the algorithms for several WRS problems and evolving data streams.
Cooperation under Incomplete Information on the Discount Factors
Venue: arXiv cs.GT 2015
Year: 2015

In the repeated Prisoner's Dilemma, when every player has a different discount factor, the grim-trigger strategy is an equilibrium if and only if the discount factor of each player is higher than some threshold. What happens if the players have incomplete information regarding the discount factors? In this work we look at repeated games in which each player has incomplete information regarding the other player's discount factor, and ask when a pair of grim-trigger strategies is an equilibrium. We provide necessary and sufficient conditions for such strategies to be an equilibrium. We characterize the states of the world in which the strategies are not triggered, i.e., the players cooperate, in such equilibria (or $ε$-equilibria), and ask whether these "cooperation events" are close to those in the complete information case, when the information is "almost" complete, in several senses.
Invertible Bloom Lookup Tables
Venue: arXiv cs.DS 2015
Year: 2015

We present a version of the Bloom filter data structure that supports not only the insertion, deletion, and lookup of key-value pairs, but also allows a complete listing of its contents with high probability, as long the number of key-value pairs is below a designed threshold. Our structure allows the number of key-value pairs to greatly exceed this threshold during normal operation. Exceeding the threshold simply temporarily prevents content listing and reduces the probability of a successful lookup. If later entries are deleted to return the structure below the threshold, everything again functions appropriately. We also show that simple variations of our structure are robust to certain standard errors, such as the deletion of a key without a corresponding insertion or the insertion of two distinct values for a key. The properties of our structure make it suitable for several applications, including database and networking applications that we highlight.
Rapid-convergent nonlinear differentiator
Venue: arXiv cs.SY 2015
Year: 2015

A nonlinear differentiator being fit for rapid convergence is presented, which is based on singular perturbation technique. The differentiator design can not only sufficiently reduce the chattering phenomenon of derivative estimation by introducing a continuous power function, but the dynamical performances are also improved by adding linear correction terms to the nonlinear ones. Moreover, strong robustness ability is obtained by integrating nonlinear items and the linear filter. The merits of the rapid-convergent differentiator include the excellent dynamical performances, restraining noises sufficiently, avoiding the chattering phenomenon and being not based on system model. The theoretical results are confirmed by computer simulations and an experiment.
Many-one reductions and the category of multivalued functions
Venue: arXiv cs.CC 2015
Year: 2015

Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degrees). A more general understanding is possible, if the category-theoretic properties of multi-valued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multi-valued functions form a distributive lattice under very general conditions, regardless of the actual reducibility notions used (e.g. Cook, Karp, Weihrauch). Beyond this, an abundance of open questions arises. Some classic results for reductions between functions carry over to multi-valued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multi-valued functions.
The Theory of the Interleaving Distance on Multidimensional Persistence Modules
Venue: arXiv cs.CG 2015
Year: 2015

In 2009, Chazal et al. introduced $ε$-interleavings of persistence modules. $ε$-interleavings induce a pseudometric $d_I$ on (isomorphism classes of) persistence modules, the interleaving distance. The definitions of $ε$-interleavings and $d_I$ generalize readily to multidimensional persistence modules. In this paper, we develop the theory of multidimensional interleavings, with a view towards applications to topological data analysis. We present four main results. First, we show that on 1-D persistence modules, $d_I$ is equal to the bottleneck distance $d_B$. This result, which first appeared in an earlier preprint of this paper, has since appeared in several other places, and is now known as the isometry theorem. Second, we present a characterization of the $ε$-interleaving relation on multidimensional persistence modules. This expresses transparently the sense in which two $ε$-interleaved modules are algebraically similar. Third, using this characterization, we show that when we define our persistence modules over a prime field, $d_I$ satisfies a universality property. This universality result is the central result of the paper. It says that $d_I$ satisfies a stability property generalizing one which $d_B$ is known to satisfy, and that in addition, if $d$ is any other pseudometric on multidimensional persistence modules satisfying the same stability property, then $d\leq d_I$. We also show that a variant of this universality result holds for $d_B$, over arbitrary fields. Finally, we show that $d_I$ restricts to a metric on isomorphism classes of finitely presented multidimensional persistence modules.