Indexing for moving objects

Abstract

Rapid advancements in positioning systems such as GPS technology and wireless communications enable accurate tracking of continuously moving objects. This development poses new challenges to database technology since maintaining up-to-date information regarding the location of moving objects incurs an enormous amount of updates. Furthermore, some applications require high degree of concurrent operations, which introduces more difficulties for indexing technology. In this thesis, we shall examine a simple yet efficient technique in moving objects indexing.Most of existing techniques for indexing moving objects depend on the use of a minimum bounding rectangle (MBR) in a multi-dimensional index structure such as the R-tree. The association of moving speeds with its MBR often causes large overlaps among MBRs. This problem becomes more severe as the number of concurrent operations increases due to lock contention. Thus, it cannot handle heavy update load and high degree concurrent update efficiently. We observe that due to the movement of objects and the need to support fast and frequent concurrent operations, MBR is a stumbling block to performance. To address the problem, we believe that indexes based on hash functions are good alternatives, since they are able to provide quickly update and do not suffer from the overlapping problem. However, region based retrieval must be supported. Consequently, we propose a a??newa??, simple structure based on the Buddytree, named Buddy*-tree. The Buddy*-tree is a hierarchical structure without the notion of tight bounding spaces. In the proposed structure, a moving object is stored as a snapshot, which is composed of its position and velocity at a certain timestamp. The status of an indexed object is not changed unless there is an update for it. Instead of capturing speed in an MBR, we enlarge the query rectangle to handle future queries. To support concurrent operations efficiently we employ sibling pointers like the B-link-tree and R-link-tree in the Buddy*-tree. An extensive experimental study was conducted and the results show that our proposed structure outperforms existing structures such as the TPR*-tree and Bx-tree by a wide margin. To this end, we believe that our contributions have successfully addressed some of the issues of moving objects indexing techniques.