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%).