Maintenance of K-nn and spatial join queries on continuously moving points

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 function p(t) = &OV0489;0 + (t − t0)&OV0505;, where &OV0489;0 is the start location, t0 is the start time, and &OV0505; 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 so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain k-nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with 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 the supporting data structures.