2007 | OriginalPaper | Buchkapitel
A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window
verfasst von : Costas Busch, Srikanta Tirthapura
Erschienen in: STACS 2007
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
We consider the problem of maintaining aggregates over recent elements of a massive data stream. Motivated by applications involving network data, we consider
asynchronous
data streams, where the observed order of data may be different from the order in which the data was generated. The set of recent elements is modeled as a
sliding timestamp window
of the stream, whose elements are changing continuously with time. We present the first
deterministic
algorithms for maintaining a small space summary of elements in a sliding timestamp window of an asynchronous data stream. The summary can return approximate answers for the following fundamental aggregates:
basic count
, the number of elements within the sliding window, and
sum
, the sum of all element values within the sliding window. For basic counting, the space taken by our summary is
O
(log
W
·log
B
·(log
W
+ log
B
)/
ε
) bits, where
B
is an upper bound on the value of the basic count,
W
is an upper bound on the width of the timestamp window, and
ε
is the desired relative error. Our algorithms are based on a novel data structure called
splittable histogram
. Prior to this work, randomized algorithms were known for this problem, which provide weaker guarantees than those provided by our deterministic algorithms.