^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{3} Department of Computer Science, Duke University^{4} School of Computing, University of Utah^{5} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/s00224-012-9382-7

Abstract:

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each pointâ€™s uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline

Type:

Journal article

Language:

English

Published in:

Theory of Computing Systems, 2013, Vol 52, Issue 3, p. 342-366

Keywords:

dat structures; approximation algorithms; computational geometry