OpenRaiser/Intern-Atlas huggingface dataset:
Active Linkability Attacks
Venue: arXiv cs.CR 2014
Year: 2014

We study linking attacks on communication protocols. We show that an active attacker is strictly more powerful in this setting than previously-considered passive attackers. We introduce a formal model to reason about active linkability attacks, formally define security against these attacks and give very general conditions for both security and insecurity of protocols. In addition, we introduce a composition-like technique that allows to obtain security proofs by only studying small components of a protocol.
Constructing Gazetteers from Volunteered Big Geo-Data Based on Hadoop
Venue: arXiv cs.DC 2014
Year: 2014

Traditional gazetteers are built and maintained by authoritative mapping agencies. In the age of Big Data, it is possible to construct gazetteers in a data-driven approach by mining rich volunteered geographic information (VGI) from the Web. In this research, we build a scalable distributed platform and a high-performance geoprocessing workflow based on the Hadoop ecosystem to harvest crowd-sourced gazetteer entries. Using experiments based on geotagged datasets in Flickr, we find that the MapReduce-based workflow running on the spatially enabled Hadoop cluster can reduce the processing time compared with traditional desktop-based operations by an order of magnitude. We demonstrate how to use such a novel spatial-computing infrastructure to facilitate gazetteer research. In addition, we introduce a provenance-based trust model for quality assurance. This work offers new insights on enriching future gazetteers with the use of Hadoop clusters, and makes contributions in connecting GIS to the cloud computing environment for the next frontier of Big Geo-Data analytics.
NOMAD: Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion
Venue: arXiv cs.DC 2014
Year: 2014

We develop an efficient parallel distributed algorithm for matrix completion, named NOMAD (Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion). NOMAD is a decentralized algorithm with non-blocking communication between processors. One of the key features of NOMAD is that the ownership of a variable is asynchronously transferred between processors in a decentralized fashion. As a consequence it is a lock-free parallel algorithm. In spite of being an asynchronous algorithm, the variable updates of NOMAD are serializable, that is, there is an equivalent update ordering in a serial implementation. NOMAD outperforms synchronous algorithms which require explicit bulk synchronization after every iteration: our extensive empirical evaluation shows that not only does our algorithm perform well in distributed setting on commodity hardware, but also outperforms state-of-the-art algorithms on a HPC cluster both in multi-core and distributed memory settings.
Preliminary Results on 3D Channel Modeling: From Theory to Standardization
Venue: arXiv cs.IT 2014
Year: 2014

Three dimensional beamforming (3D) (also elevation beamforming) is now gaining a growing interest among researchers in wireless communication. The reason can be attributed to its potential to enable a variety of strategies like sector or user specific elevation beamforming and cell-splitting. Since these techniques cannot be directly supported by current LTE releases, the 3GPP is now working on defining the required technical specifications. In particular, a large effort is currently made to get accurate 3D channel models that support the elevation dimension. This step is necessary as it will evaluate the potential of 3D and FD(Full Dimensional) beamforming techniques to benefit from the richness of real channels. This work aims at presenting the on-going 3GPP study item "Study on 3D-channel model for Elevation Beamforming and FD-MIMO studies for LTE", and positioning it with respect to previous standardization works.
The guillotine approach for TSP with neighborhoods revisited
Venue: arXiv cs.CG 2014
Year: 2014

The Euclidean TSP with neighborhoods (TSPN) is the following problem: Given a set R of k regions, find a shortest tour that visits at least one point from each region. We study the special cases of disjoint, connected, alpha-fat regions (i.e., every region P contains a disk of diameter diam(P)/alpha) and disjoint unit disks. For the latter, Dumitrescu and Mitchell proposed an algorithm based on Mitchell's guillotine subdivision approach for the Euclidean TSP and claimed it to be a PTAS. However, their proof contains a severe gap, which we will close in the following. Bodlaender et al. remark that their techniques for the minimum corridor connection problem carry over to the TSPN and yield an alternative PTAS for this problem. For disjoint connected alpha-fat regions of varying size, Mitchell proposed a slightly different PTAS candidate. We will expose several further problems and gaps in this approach. Some of them we can close, but overall, for alpha-fat regions, the existence of a PTAS for the TSPN remains open.
Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location
Venue: arXiv cs.DS 2014
Year: 2014

Metric facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. The capacity-constrained generalizations, such as capacitated facility location (CFL) and lower-bounded facility location (LBFL), have proved notorious as far as LP-based approximation is concerned: while there are local-search-based constant-factor approximations, there is no known linear relaxation with constant integrality gap. According to Williamson and Shmoys devising a relaxation-based approximation for \cfl\ is among the top 10 open problems in approximation algorithms. This paper advances significantly the state-of-the-art on the effectiveness of linear programming for capacity-constrained facility location through a host of impossibility results for both CFL and LBFL. We show that the relaxations obtained from the natural LP at $Ω(n)$ levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question of \cite{LiS13, AnBS13}. Here, $n$ denotes the number of facilities in the instance. Building on the ideas for this result, we prove that the standard CFL relaxation enriched with the generalized flow-cover valid inequalities \cite{AardalPW95} has also an unbounded gap. This disproves a long-standing conjecture of \cite{LeviSS12}. We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for CFL and LBFL through a sharp threshold phenomenon.
Analysis of Distributed Stochastic Dual Coordinate Ascent
Venue: arXiv cs.DC 2014
Year: 2014

In \citep{Yangnips13}, the author presented distributed stochastic dual coordinate ascent (DisDCA) algorithms for solving large-scale regularized loss minimization. Extraordinary performances have been observed and reported for the well-motivated updates, as referred to the practical updates, compared to the naive updates. However, no serious analysis has been provided to understand the updates and therefore the convergence rates. In the paper, we bridge the gap by providing a theoretical analysis of the convergence rates of the practical DisDCA algorithm. Our analysis helped by empirical studies has shown that it could yield an exponential speed-up in the convergence by increasing the number of dual updates at each iteration. This result justifies the superior performances of the practical DisDCA as compared to the naive variant. As a byproduct, our analysis also reveals the convergence behavior of the one-communication DisDCA.
A Necessary and Sufficient Condition for the Existence of Potential Functions for Heterogeneous Routing Games
Venue: arXiv cs.GT 2014
Year: 2014

We study a heterogeneous routing game in which vehicles might belong to more than one type. The type determines the cost of traveling along an edge as a function of the flow of various types of vehicles over that edge. We relax the assumptions needed for the existence of a Nash equilibrium in this heterogeneous routing game. We extend the available results to present necessary and sufficient conditions for the existence of a potential function. We characterize a set of tolls that guarantee the existence of a potential function when only two types of users are participating in the game. We present an upper bound for the price of anarchy (i.e., the worst-case ratio of the social cost calculated for a Nash equilibrium over the social cost for a socially optimal flow) for the case in which only two types of players are participating in a game with affine edge cost functions. A heterogeneous routing game with vehicle platooning incentives is used as an example throughout the article to clarify the concepts and to validate the results.
Rigorous asymptotic and moment-preserving diffusion approximations for generalized linear Boltzmann transport in arbitrary dimension
Venue: arXiv cs.GR 2014
Year: 2014

We derive new diffusion solutions to the monoenergetic generalized linear Boltzmann transport equation (GLBE) for the stationary collision density and scalar flux about an isotropic point source in an infinite $d$-dimensional absorbing medium with isotropic scattering. We consider both classical transport theory with exponentially-distributed free paths in arbitrary dimensions as well as a number of non-classical transport theories (non-exponential random flights) that describe a broader class of transport processes within partially-correlated random media. New rigorous asymptotic diffusion approximations are derived where possible. We also generalize Grosjean's moment-preserving approach of separating the first (or uncollided) distribution from the collided portion and approximating only the latter using diffusion. We find that for any spatial dimension and for many free-path distributions Grosjean's approach produces compact, analytic approximations that are, overall, more accurate for high absorption and for small source-detector separations than either $P_1$ diffusion or rigorous asymptotic diffusion. These diffusion-based approximations are exact in the first two even spatial moments, which we derive explicitly for various non-classical transport types. We also discuss connections between the random-flight-theory derivation of the Green's function and the discrete spectrum of the transport operator and report some new observations regarding the discrete eigenvalues of the transport operator for general dimensions and free-path distributions.
Multi-Antenna Wireless Powered Communication with Energy Beamforming
Venue: arXiv cs.IT 2014
Year: 2014

The newly emerging wireless powered communication networks (WPCNs) have recently drawn significant attention, where radio signals are used to power wireless terminals for information transmission. In this paper, we study a WPCN where one multi-antenna access point (AP) coordinates energy transfer and information transfer to/from a set of single-antenna users. A harvest-then-transmit protocol is assumed where the AP first broadcasts wireless power to all users via energy beamforming in the downlink (DL), and then the users send their independent information to the AP simultaneously in the uplink (UL) using their harvested energy. To optimize the users' throughput and yet guarantee their rate fairness, we maximize the minimum throughput among all users by a joint design of the DL-UL time allocation, the DL energy beamforming, and the UL transmit power allocation plus receive beamforming. We solve this non-convex problem optimally by two steps. First, we fix the DL-UL time allocation and obtain the optimal DL energy beamforming, UL power allocation and receive beamforming to maximize the minimum signal-to-interference-plus-noise ratio (SINR) of all users. This problem is shown to be in general non-convex; however, we convert it equivalently to a spectral radius minimization problem, which can be solved efficiently by applying the alternating optimization based on the non-negative matrix theory. Then, the optimal time allocation is found by a one-dimension search to maximize the minimum rate of all users. Furthermore, two suboptimal designs of lower complexity are proposed, and their throughput performance is compared against that of the optimal solution.
Energy-Efficient, Large-scale Distributed-Antenna System (L-DAS) for Multiple Users
Venue: arXiv cs.IT 2014
Year: 2014

Large-scale distributed-antenna system (L-DAS) with very large number of distributed antennas, possibly up to a few hundred antennas, is considered. A few major issues of the L-DAS, such as high latency, energy consumption, computational complexity, and large feedback (signaling) overhead, are identified. The potential capability of the L-DAS is illuminated in terms of an energy efficiency (EE) throughout the paper. We firstly and generally model the power consumption of an L-DAS, and formulate an EE maximization problem. To tackle two crucial issues, namely the huge computational complexity and large amount of feedback (signaling) information, we propose a channel-gain-based antenna selection (AS) method and an interference-based user clustering (UC) method. The original problem is then split into multiple subproblems by a cluster, and each cluster's precoding and power control are managed in parallel for high EE. Simulation results reveal that i) using all antennas for zero-forcing multiuser multiple-input multiple-output (MU-MIMO) is energy inefficient if there is nonnegligible overhead power consumption on MU-MIMO processing, and ii) increasing the number of antennas does not necessarily result in a high EE. Furthermore, the results validate and underpin the EE merit of the proposed L-DAS complied with the AS, UC, precoding, and power control by comparing with non-clustering L-DAS and colocated antenna systems.
Multi-frame denoising of high speed optical coherence tomography data using inter-frame and intra-frame priors
Venue: arXiv cs.CV 2014
Year: 2014

Optical coherence tomography (OCT) is an important interferometric diagnostic technique which provides cross-sectional views of the subsurface microstructure of biological tissues. However, the imaging quality of high-speed OCT is limited due to the large speckle noise. To address this problem, this paper proposes a multi-frame algorithmic method to denoise OCT volume. Mathematically, we build an optimization model which forces the temporally registered frames to be low rank, and the gradient in each frame to be sparse, under logarithmic image formation and noise variance constraints. Besides, a convex optimization algorithm based on the augmented Lagrangian method is derived to solve the above model. The results reveal that our approach outperforms the other methods in terms of both speckle noise suppression and crucial detail preservation.
Spectral Efficiency and Outage Performance for Hybrid D2D-Infrastructure Uplink Cooperation
Venue: arXiv cs.IT 2014
Year: 2014

We propose a time-division uplink transmission scheme that is applicable to future cellular systems by introducing hybrid device-to-device (D2D) and infrastructure cooperation. We analyze its spectral efficiency and outage performance and show that compared to existing frequency-division schemes, the proposed scheme achieves the same or better spectral efficiency and outage performance while having simpler signaling and shorter decoding delay. Using time-division, the proposed scheme divides each transmission frame into three phases with variable durations. The two user equipments (UEs) partially exchange their information in the first two phases, then cooperatively transmit to the base station (BS) in the third phase. We further formulate its common and individual outage probabilities, taking into account outages at both UEs and the BS. We analyze this outage performance in Rayleigh fading environment assuming full channel state information (CSI) at the receivers and limited CSI at the transmitters. Results show that comparing to non-cooperative transmission, the proposed cooperation always improves the instantaneous achievable rate region even under half-duplex transmission. Moreover, as the received signal-to-noise ratio increases, this uplink cooperation significantly reduces overall outage probabilities and achieves the full diversity order in spite of additional outages at the UEs. These characteristics of the proposed uplink cooperation make it appealing for deployment in future cellular networks.
Exact Recovery for Sparse Signal via Weighted $l_1$ Minimization
Venue: arXiv cs.IT 2014
Year: 2014

Numerical experiments in literature on compressed sensing have indicated that the reweighted $l_1$ minimization performs exceptionally well in recovering sparse signal. In this paper, we develop exact recovery conditions and algorithm for sparse signal via weighted $l_1$ minimization from the insight of the classical NSP (null space property) and RIC (restricted isometry constant) bound. We first introduce the concept of WNSP (weighted null space property) and reveal that it is a necessary and sufficient condition for exact recovery. We then prove that the RIC bound by weighted $l_1$ minimization is $δ_{ak}<\sqrt{\frac{a-1}{a-1+γ^2}}$, where $a>1$, $0<γ\leq1$ is determined by an optimization problem over the null space. When $γ< 1$ this bound is greater than $\sqrt{\frac{a-1}{a}}$ from $l_1$ minimization. In addition, we also establish the bound on $δ_k$ and show that it can be larger than the sharp one 1/3 via $l_1$ minimization and also greater than 0.4343 via weighted $l_1$ minimization under some mild cases. Finally, we achieve a modified iterative reweighted $l_1$ minimization (MIRL1) algorithm based on our selection principle of weight, and the numerical experiments demonstrate that our algorithm behaves much better than $l_1$ minimization and iterative reweighted $l_1$ minimization (IRL1) algorithm.
Optimal compression in natural gas networks: a geometric programming approach
Venue: arXiv cs.SY 2014
Year: 2014

Natural gas transmission pipelines are complex systems whose flow characteristics are governed by challenging non-linear physical behavior. These pipelines extend over hundreds and even thousands of miles. Gas is typically injected into the system at a constant rate, and a series of compressors are distributed along the pipeline to boost the gas pressure to maintain system pressure and throughput. These compressors consume a portion of the gas, and one goal of the operator is to control the compressor operation to minimize this consumption while satisfying pressure constraints at the gas load points. The optimization of these operations is computationally challenging. Many pipelines simply rely on the intuition and prior experience of operators to make these decisions. Here, we present a new geometric programming approach for optimizing compressor operation in natural gas pipelines. Using models of real natural gas pipelines, we show that the geometric programming algorithm consistently outperforms approaches that mimic existing state of practice.
Efficient Lineage for SUM Aggregate Queries
Venue: arXiv cs.DB 2014
Year: 2014

AI systems typically make decisions and find patterns in data based on the computation of aggregate and specifically sum functions, expressed as queries, on data's attributes. This computation can become costly or even inefficient when these queries concern the whole or big parts of the data and especially when we are dealing with big data. New types of intelligent analytics require also the explanation of why something happened. In this paper we present a randomised algorithm that constructs a small summary of the data, called Aggregate Lineage, which can approximate well and explain all sums with large values in time that depends only on its size. The size of Aggregate Lineage is practically independent on the size of the original data. Our algorithm does not assume any knowledge on the set of sum queries to be approximated.
Power Scheduling of Kalman Filtering in Wireless Sensor Networks with Data Packet Drops
Venue: arXiv cs.SY 2014
Year: 2014

For a wireless sensor network (WSN) with a large number of low-cost, battery-driven, multiple transmission power leveled sensor nodes of limited transmission bandwidth, then conservation of transmission resources (power and bandwidth) is of paramount importance. Towards this end, this paper considers the problem of power scheduling of Kalman filtering for general linear stochastic systems subject to data packet drops (over a packet-dropping wireless network). The transmission of the acquired measurement from the sensor to the remote estimator is realized by sequentially transmitting every single component of the measurement to the remote estimator in one time period. The sensor node decides separately whether to use a high or low transmission power to communicate every component to the estimator across a packet-dropping wireless network based on the rule that promotes the power scheduling with the least impact on the estimator mean squared error. Under the customary assumption that the predicted density is (approximately) Gaussian, leveraging the statistical distribution of sensor data, the mechanism of power scheduling, the wireless network effect and the received data, the minimum mean squared error estimator is derived. By investigating the statistical convergence properties of the estimation error covariance, we establish, for general linear systems, both the sufficient condition and the necessary condition guaranteeing the stability of the estimator.
Low Latency Datacenter Networking: A Short Survey
Venue: arXiv cs.NI 2014
Year: 2014

Datacenters are the cornerstone of the big data infrastructure supporting numerous online services. The demand for interactivity, which significantly impacts user experience and provider revenue, is translated into stringent timing requirements for flows in datacenter networks. Thus low latency networking is becoming a major concern of both industry and academia. We provide a short survey of recent progress made by the networking community for low latency datacenter networks. We propose a taxonomy to categorize existing work based on four main techniques, reducing queue length, accelerating retransmissions, prioritizing mice flows, and exploiting multi-path. Then we review select papers, highlight the principal ideas, and discuss their pros and cons. We also present our perspectives of the research challenges and opportunities, hoping to aspire more future work in this space.
Geometric lattice structure of covering and its application to attribute reduction through matroids
Venue: arXiv cs.AI 2014
Year: 2014

The reduction of covering decision systems is an important problem in data mining, and covering-based rough sets serve as an efficient technique to process the problem. Geometric lattices have been widely used in many fields, especially greedy algorithm design which plays an important role in the reduction problems. Therefore, it is meaningful to combine coverings with geometric lattices to solve the optimization problems. In this paper, we obtain geometric lattices from coverings through matroids and then apply them to the issue of attribute reduction. First, a geometric lattice structure of a covering is constructed through transversal matroids. Then its atoms are studied and used to describe the lattice. Second, considering that all the closed sets of a finite matroid form a geometric lattice, we propose a dependence space through matroids and study the attribute reduction issues of the space, which realizes the application of geometric lattices to attribute reduction. Furthermore, a special type of information system is taken as an example to illustrate the application. In a word, this work points out an interesting view, namely, geometric lattice to study the attribute reduction issues of information systems.