Abstract

The number of location-based services for monitoring and querying large numbers of moving objects is increasing rapidly. The services are facilitated by spatio-temporal databases that continuously receive updated position data from objects. This has inspired the development of indexing structures that perform well with dynamic spatio-temporal data, since traditional spatial indexing structures suffer from large update costs or poor query performance when used in spatio-temporal settings. In recent years, memory prices have dropped, making main-memory databases a viable option. The transition from disk-based to memory-based databases means that existing knowledge on database index performance needs to be revised. Several index structure optimizations for memory implementation have therefore been proposed. Unfortunately, the results of individual proposals cannot easily be compared, as each proposal carries its own individual setting. This motivates the need for a performance benchmark of the most significant spatio-temporal indexing structures in a main-memory setting. We modify an existing disk-based performance benchmark, enabling us to evaluate and compare main-memory spatio-temporal indexes. We propose main-memory variants of a Grid and an R-tree, along with a simple array structure, examine their performance in a variety of settings and compare the results. We conclude that the Grid is generally the faster of the three indexes. Non-local updates in the R-tree are slower, because the tree structure has to be maintained. The Array performs the fastest updates and the slowest queries, although for some workloads, the combined performance is comparable. However, we believe that LBS end-users value fast queries, which is why the Array is not suitable for query efficient LBSs. Though the results show query times that favour the Grid, considering the higher versatility of the R-tree, we find that both indexes are highly suited for indexing the positions of dynamic spatio-temporal moving objects.

Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.

If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.

A master thesis from Aalborg University

Update-Efficient Main-Memory Indexing of Moving Objects