Algorithms for Moving Objects Databases

Whereas earlier work on spatio-temporal databases generally focused on geometries changing in discrete steps, the emerging area of moving objects databases supports geometries changing continuously. Two important abstractions are moving point and moving region, modeling objects for which only the time- dependent position, or also the shape and extent are relevant, respectively. Examples of the ¯rst kind of moving entity are all kinds of vehicles, aircraft, people, or animals; of the latter hurricanes, forest ¯res, forest growth, or oil spills in the sea. The goal is to develop data models and query languages as well as DBMS implementations supporting such entities, enabling new kinds of database applications. In earlier work we have proposed an approach based on abstract data types. Hence, moving point or moving region are viewed as data types with suitable operations. For example, a moving point might be projected into the plane, yielding a curve, or a moving region be mapped to a function describing the development of its size, yielding a real-valued function. A careful design of a system of types and operations (an algebra) has been presented, emphasizing completeness, closure, consistency and genericity. This design was given at an abstract level, de¯ning, for example, geometries in terms of in¯nite point sets. In the next step, a discrete model was presented, o®ering ¯nite representations and data structures for all the types of the abstract model. The present paper provides the ¯nal step towards implementation by studying and developing systematically algorithms for (a large subset of) the operations. Some of them are relatively straightforward; others are quite complex. Algorithms are meant to be used in a database context; we also address ¯ltering techniques and practical issues such as large object management or numeric robustness in the context of an ongoing prototype implementation.