Uncertain range queries for necklaces

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.