Presented by: Rui Li

Abstruct:

Managing and manipulating uncertainty in spatial databases are important problems for various practical applications. Unlike the traditional fuzzy approaches in relational databases, in this paper we use a probability-based method to model and index uncertain spatial data where every object is represented by a probability density function(PDF). To index PDFs, we construct an optimized Gaussian mixture hierarchy (OGMH) and two variants of uncertain R-tree. A comprehensive comparison among these three indices and plain R-tree is done on TIGER/Line Southern California landmark point dataset. We find that uncertain R-tree is the best for fixed query and OGMH is suitable for both certain and uncertain queries. Moreover, OGMH is suitable not only for spatial databases, but also for multi-dimensional indexing applications like content based image retrieval, where R-tree is inefficient in high dimensions.