Math @ Duke

Publications [#235369] of Pankaj K. Agarwal
Papers Published
 Afshani, P; Agarwal, PK; Arge, L; Larsen, KG; Phillips, JM, (Approximate) Uncertain Skylines,
Theory of Computing Systems, vol. 52 no. 3
(2013),
pp. 342366, ISSN 14324350 [doi]
(last updated on 2017/12/12)
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, nearlinear 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. © 2012 Springer Science+Business Media, LLC.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

