Maintenance of Spatial Queries on Continuously Moving Points

Abstract

Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the linear function p(t) = x_0 + (t - t_0)v, where x_0 is the start location, t_0 is the start time, and v is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object's behavior changes enough that the function describing its location is no longer accurate, the function coefficients for the object are updated.Because the objects are represented as a function of time, spatial query results can change even when no transactions update the database. Our hypothesis is that algorithms for the maintenance of spatial queries on kinematic point data types can be developed to support updates to base relations as time advances that are more efficient than straight forward adaptations of previous work. We present algorithms to maintain k-nearest neighbor, spatial join, and spatial semijoin queries in this domain. We compare by experimentation these new algorithms to more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I/O disk accesses needed to maintain the query results and supporting data structures. A system to query and visualize results on moving object data, in a client-server environment, is also presented. The work presented here is built upon a culmination of our previously published work, including work on continuously moving point queries [35, 36], and client-server systems [31, 33, 34].