Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

In recent years, management of moving objects has emerged as anactive topic of spatial access methods. Various data structures(indexes) have been proposed to handle queries of moving points, forexample, the well-known B^x-tree uses a novel mapping mechanism toreduce the index update costs. However, almost all the existingindexes for predictive queries are not applicable in certaincircumstances when the update frequencies of moving objects becomehighly variable and when the system needs to balance the performanceof updates and queries. In this paper, we introduce two kinds ofnovel indexes, named B^y-tree and \al \rm B^y-tree. By associatinga \em prediction life period with every moving object, the proposedindexes are applicable in the environments with highly variableupdate frequencies. In addition, the \al \rm B^y-tree can balance theperformance of updates and queries depending on a balance parameter.Experimental results show that the B^y-tree and \al \rm B^y-treeoutperform the B^x-tree in various conditions.