Aarhus University Seal / Aarhus Universitets segl

Lars Arge

(Approximate) Uncertain Skylines

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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 eciently determine the probability
of a query point lying on the skyline.
Original languageEnglish
Title of host publicationProceedings of the 14th International Conference on Database Theory
Number of pages11
PublisherAssociation for Computing Machinery
Publication year2011
ISBN (print)978-1-4503-0529-7
Publication statusPublished - 2011
EventInternational Conference on Database Theory - Uppsala, Sweden
Duration: 21 Mar 201124 Mar 2011
Conference number: 14


ConferenceInternational Conference on Database Theory

See relations at Aarhus University Citationformats

ID: 41946834