Authors: M. Hadjieleftheriou, G. Kollios, D. Gunopulos, V.J. Tsotras
Title: On-Line Discovery of Dense Areas in Spatio-temporal Databases
Abstract: Moving object databases have received considerable attention recently.
Previous work has concentrated mainly on modeling and indexing problems,
as well as query selectivity estimation.
Here we introduce a novel problem, that of addressing density-based
queries in the spatio-temporal domain. For example:
"Find all regions that will contain more than 500 objects, ten minutes from now".
The user may also be interested in finding the time period (interval) that the
query answer remains valid. We formally define a new class of density-based queries
and give approximate, on-line techniques that answer them efficiently.
Typically the threshold above which a region is considered to be dense is part
of the query. The difficulty of the problem lies in the fact that the spatial and temporal predicates
are not specified by the query. The techniques we introduce find all candidate dense
regions at any time in the future. To make them more scalable we
subdivide the spatial universe using
a grid and limit queries within a pre-specified time horizon.
Finally, we validate our approaches with a thorough experimental evaluation.