Update-Efficient Main-Memory Indexing of Moving Objects

Student thesis: Master Thesis and HD Thesis

  • Jan Maffert Johansen
  • Donatas Saulys
  • Christian Christiansen
2. term, Computer Science, Master (Master Programme)
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.
Publication date2008
Number of pages26
Publishing institutionAAU, Institut for Datalogi
ID: 14466668