2011 | OriginalPaper | Buchkapitel
Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data
verfasst von : Tak-Wah Lam, Chi-Man Liu, Hing-Fung Ting
Erschienen in: Approximation and Online Algorithms
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 online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. The objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the
d
-dimensional grid {1, 2, ⋯ ,
U
}
d
, we give an
O
(
d
log
U
)-competitive algorithm for this online problem. The competitive ratio is asymptotically tight as it is relatively easy to show an Ω(
d
log
U
) lower bound.