Indexing large moving objects from past to future with PCFI

Indexing large moving objects from past to future with PCFI

In moving object database, the moving objects' current position must be kept in memory, also to the trajectory, in some case, as same as the future. But the current existing indexes such as SEB tree, SETI tree, 2+3R tree, 2 3RT tree and etc. can only provide the capability for past and current query, and the TPR Tree, TPR * Tree and etc. can only provide the capability for current and future query. None of them can provide a strategy for indexing the past, current and also the future information of moving objects. In this paper, we propose the past current future Index (PCFI Index) to index the past, current & future information of the moving objects. It is the combination of SETI tree and TPR * tree, the SETI liking index is used for indexing the historical trajectory segments except the front line structure, and the moving objects' current positions, velocities are indexed via the in memory frontline structure which mainly implemented with TPR * tree. Considering the large update operations on TPR tree of large population, a hash table considering cache sensitivity is also introduced. It works with the frontline part, leading a bottom up update of the tree. The performance analysis proves that the PCFI index can handle most of the query efficiently and provides a uniform solution for the trajectory query, time slice query, internal query and moving query.