Please use this identifier to cite or link to this item:

Spatio-temporal join selectivity

Authors Sun, Jimeng
Tao, Yufei
Papadias, Dimitris View this author's profile
Kollios, George
Issue Date 2006
Source Information systems , v. 31, (8), 2006, DEC, p. 793-813
Summary Given two sets S-1, S-2 of moving objects, a future timestamp t(q), and a distance threshold d, a spatio-temporal join retrieves all pairs of objects that are within distance d at t(q). The selectivity of a join equals the number of retrieved pairs divided by the cardinality of the Cartesian product S-1 X S-2. This paper develops a model for spatio-temporal join selectivity estimation based on rigorous probabilistic analysis, and reveals the factors that affect the selectivity. Initially, we solve the problem for ID (point and rectangle) objects whose location and velocities distribute uniformly, and then extend the results to multi-dimensional spaces. Finally, we deal with non-uniform distributions using a specialized spatio-temporal histogram. Extensive experiments confirm that the proposed formulae are highly accurate (average error below 10\%). (c) 2005 Elsevier B.V. All rights reserved.
ISSN 0306-4379
Rights Information systems © copyright (2006) Elsevier. The Journal's web site is located at
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
IS06STJ.pdf 411835 B Adobe PDF