Uncertain range queries for necklaces

Goce Trajcevski*, Alok Choudhary, Ouri Wolfson, Li Ye, Gang Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations


We address the problem of efficient processing of spatio-temporal range queries for moving objects whose whereabouts in time are not known exactly. The fundamental question tackled by such queries is, given a spatial region and a temporal interval, retrieve the objects that were inside the region during the given time-interval. As earlier works have demonstrated, when the (location,time) information is uncertain, syntactic constructs are needed to capture the impact of the uncertainty, along with the corresponding processing algorithms. In this work, we focus on the uncertainty model that represents the whereabouts in-between two known locations as a bead, and an uncertain trajectory is represented as a necklace - a sequence of beads. For each syntactic variant of the range query, we present the respective processing algorithms and, in addition, we propose pruning strategies that speed up the generation of the queries' answers. We also present the experimental observations that quantify the benefits of our proposed methodologies.

Original languageEnglish (US)
Title of host publicationMDM2010 - 11th International Conference on Mobile Data Management
Number of pages10
StatePublished - 2010
Event11th IEEE International Conference on Mobile Data Management, MDM 2010 - Kansas City, MO, United States
Duration: May 23 2010May 26 2010

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
ISSN (Print)1551-6245


Other11th IEEE International Conference on Mobile Data Management, MDM 2010
Country/TerritoryUnited States
CityKansas City, MO

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Uncertain range queries for necklaces'. Together they form a unique fingerprint.

Cite this