Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A Randomized Algorithm for Finding Frequent Elements in Streams Using O(loglogN) Space
verfasst von : Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Finding frequent items in a data stream is a fundamental problem; Given a threshold
θ
∈ (0,1), find items appearing more than
$\theta \cdotp N$
times in an input
stream
with length
N
. Karp, Shenker, Papadimiriou (2003) gave a simple deterministic online algorithm, which allows false positive outputs using memory of O(
θ
− 1
log
N
)
bits
, while they also gave a lower bound. Motivated by the theoretical bound of the space complexity, this paper proposes a simple randomized online algorithm using memory of O(
θ
− 2
log
2
θ
− 1
+ loglog
N
) bits where parameters for approximation are hidden in the constant. Our algorithm is
robust
for memory overflow, compared with other naïve randomized algorithms, or deterministic algorithms using memory of O(log
N
) bits. We also give some randomized algorithms for approximate counting.