HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Spatio-temporal join selectivity
Authors: Sun, Jimeng
Tao, Yufei
Papadias, Dimitris
Kollios, George
Keywords: Estimation theory
Set theory
Temporal databases
Issue Date: Dec-2006
Citation: Information systems, v. 31, no. 8, Dec. 2006, p. 793-813
Abstract: Given two sets S1, S2 of moving objects, a future timestamp tq, and a distance threshold d, a spatio-temporal join retrieves all pairs of objects that are within distance d at tq. The selectivity of a join equals the number of retrieved pairs divided by the cardinality of the Cartesian product S1×S2. 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 1D (point and rectangle) objects whose location and velocities distribute uniformly, and then extend the results to multi-dimensional spaces. Finally, we deal with nonuniform distributions using a specialized spatio-temporal histogram. Extensive experiments confirm that the proposed formulae are highly accurate (average error below 10%).
Rights: Information systems © copyright (2006) Elsevier. The Journal's web site is located at
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
IS06STJ.pdfpre-published version402KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.