Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data

摘要

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.