Index for Fast Retrieval of Uncertain Spatial Point Data.

Appeared in ACM GIS 2006 Conference

Dmitri V. Kalashnikov, Yiming Ma, Sharad Mehrotra, Ramaswamy Hariharan

Computer Science Department
University of California, Irvine


Location information gathered from a variety of sources in the form of sensor data, video streams, human observations, and so on, is often imprecise and uncertain and needs to be represented approximately. To represent such uncertain location information, the use of a probabilistic model that captures the imprecise location as a probability density function (pdf) has been recently proposed. The pdfs can be arbitrarily complex depending on the type of application and the source of imprecision. Hence, efficiently representing, storing and querying pdfs is a very challenging task. While the current state of the art indexing approaches treat the representation and storage of pdfs as a black box, in this paper, we take the challenge of representing and storing any complex pdf in an efficient way. We further develop techniques to index such pdfs to support the efficient processing of location queries. Our extensive experiments demonstrate that our indexing techniques significantly outperform the best existing solutions.

Categories and Subject Descriptors:

H.2.8 [Information System]: Database Management—Spatial databases and GIS


Spatial Database, Uncertainty Indexing, U-grid, Probability

Downloadable files:

Paper: GIS06_dvk_index.pdf
Presentation: GIS06_dvk_index.ppt

BibTeX entry:

   author    = {Dmitri V.\ Kalashnikov and Yiming Ma and Sharad Mehrotra and Ram Hariharan},
   title     = {Index for Fast Retrieval of Uncertain Spatial Point Data},
   booktitle = {Proc. of Int'l Symposium on Advances in Geographic Information Systems (ACM GIS 2006)},
   year      = {2006},
   month     = {November 10--11},
   address   = {Arlington, VA, USA}

Back to Kalashnikov's homepage