.png){kind=icon}
.png){kind=icon}
Return
A Distributed Information Divergence Estimation over Data Streams
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2013.101.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we consider the setting of large-scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we propose a novel algorithm AnKLe for estimating the Kullback-Leibler divergence of an observed stream compared with the expected one. AnKLe combines sampling techniques and information-theoretic methods. It is very efficient, both in terms of space and time complexities, and requires only a single pass over the data stream. We show that AnKLe is an (epsilon, delta)-approximation algorithm with a space complexity (O) over tilde (1/epsilon+1/epsilon(2)) bits in most cases, and (O) over tilde (1/epsilon+n-epsilon (1)/epsilon(2)) otherwise, where n is the number of distinct data items in a stream. Moreover, we propose a distributed version of AnKLe that requires at most O(rl(log n + 1) bits of communication between the l participating nodes, where r is number of rounds of the algorithm. Experimental results show that the estimation provided by AnKLe remains accurate even for different adversarial settings for which the quality of other methods dramatically decreases.
Keywords:
Data stream
Kullback-Leibler divergence
randomized approximation algorithm
byzantine adversary
performance analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W