Closest pair queries in spatio-temporal databases

Abstract

In recent years, spatio-temporal databases have been studied intensively. This paper proposes how to process k closest pair queries in spatio-temporal databases for the first time. A spatio-temporal k closest pair query continuously searches the k closest pairs between a set of spatial objects and a set of moving objects for a specified time interval of the query. To maintain the order of the kclosest pairs, we use a time function that can represent the change in distance between a spatial object and a moving object as time passes. For efficient processing of k closest pair queries, we present an event-based structure, instead of a simple split list structure to avoid unnecessary computations, along with a distance bound used to prune unnecessary node accesses. Our event-based method is 9 to 43 times faster, compared to a method using a simple split list structure. Also, our event-based structure can be applied to process spatio-temporal k nearest neighbor queries. In various experiments, our event-based approach is 11 to 46 times faster than an existing approach for processing spatio-temporal k nearest neighbor queries.