Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data

Man Lung Yiu, Nikos Mamoulis, Xiangyuan Dai, Yufei Tao, Michail Vaitis

Research output: Journal article publicationJournal articleAcademic researchpeer-review

57 Citations (Scopus)


We study the problem of answering spatial queries in databases where objects exist with some uncertainty and they are associated with an existential probability. The goal of a thresholding probabilistic spatial query is to retrieve the objects that qualify the spatial predicates with probability that exceeds a threshold. Accordingly, a ranking probabilistic spatial query selects the objects with the highest probabilities to qualify the spatial predicates. We propose adaptations of spatial access methods and search algorithms for probabilistic versions of range queries, nearest neighbors (NNs), spatial skylines, and reverse NNs, and conduct an extensive experimental study, which evaluates the effectiveness of proposed solutions.
Original languageEnglish
Article number4564461
Pages (from-to)108-122
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
Publication statusPublished - 1 Jan 2009
Externally publishedYes


  • Query processing
  • Spatial databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this