Advertisement
Published in:
2010 | OriginalPaper | Chapter
Computational Geometry for Uncertain Data
(Abstract of Keynote Talk)
Author : Mikhail J. Atallah
Published in: Frontiers in Algorithmics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The talk will review recent results and algorithmic challenges for computational geometry problems in the context of uncertain data. This is an active area of investigation in the database community, and we introduce it through the specifics of the maximal elements problem (called the skyline problem in the database community): Rather than being a point, an uncertain object is a set of points called instances, each with an associated probability; instances of the same uncertain object can be geometrically far from each other, and are mutually exclusive (i.e., at most one of them can occur). For this version of the maximal elements problem, the input is a collection of
m
uncertain objects, whose total number of instances is
n
, and the problem is to compute for each of these
n
instances the probability that it is a maximal point, i.e., that it occurs for its own object and is not dominated by any occurring instance from another object.