Indexing moving objects in main memory

The number of users of location-based services is increasing rapidly. Spatio-temporal databases for indexing geographical positions of such users or other types of moving objects either suffer from large update costs or poor query performance. Since main memory sizes grow and many location-based services value efficiency over persistence, main memory databases become increasingly feasible. Database indexes are traditionally implemented as tree-based structures, but recent work indicates that grid-based structures work are more update-efficient. We propose two grid-based index structures residing in main memory. A simple grid structure that uses a point-based update policy, and an advanced grid structure, called the Dual Grid, which uses a vector-based update policy and stores velocity vectors as points by using so-called duality transformations. We conduct a number of tests to compare the update and query performance.