Authors: M. Hadjieleftheriou, G. Kollios, V.J. Tsotras
Title: Performance Evaluation of Spatio-temporal Selectivity Estimation Techniques
Conference: SSDBM
Year: 2003
Abstract: Many novel spatio-temporal applications deal with moving objects. In such environments,
a database typically maintains the initial position and the moving function for each
object. Instead of
updating the database whenever an object position changes (which is not manageable),
updates are issued whenever the moving function deviates beyond a given threshold.
For simplicity, we assume that objects move with linear trajectories. Maintaining the
moving functions in a database introduces novel problems. For example,
the database can answer queries about object positions in the {\em future}:
"find all objects that will be in area $A$, 10 minutes from now".
In this paper we present a thorough performance evaluation of techniques for estimating the
selectivity of such queries.
We consider various existing estimators that can be stored
in main memory and are updated dynamically.
Furthermore, we propose
two new approaches, a technique that uses histograms and a secondary index based estimator.
We run a diverse set of experiments to identify the strengths and weaknesses of every approach,
using a wide variety of datasets.
Back