Trees or Grids? Indexing Moving Objects in Main Memory

Darius Sidlauskas, Simonas Saltenis, Christian Winther Christiansen, Jan M. Johansen, Donatas Saulys

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

62 Citations (Scopus)

Abstract

New application areas, such as location-based services, rely on the efficient management of large collections of mobile objects. Maintaining accurate, up-to-date positions of these objects results in massive update loads that must be supported by spatial indexing structures and main-memory indexes are usually necessary to provide high update performance. Traditionally, the R-tree and its variants were used for indexing spatial data, but most of the recent research assumes that a simple, uniform grid is the best choice for managing moving objects in main memory.

We perform an extensive experimental study to compare the two approaches on modern hardware. As the result of numerous design-and-experiment iterations, we propose the update- and query-efficient variants of the R-tree and the grid. The experiments with these indexes reveal a number of interesting insights. First, the coupling of a spatial index, grid or R-tree, with a secondary index on object IDs boosts the update performance significantly. Next, the R-tree, when combined with such a secondary index, can provide update performance competitive with the grid. Finally, the grid can compete with the R-tree in terms of the query performance and it is surprisingly robust to varying parameters of the workloads. In summary, the study shows that, in most cases, the choice of the index boils down to the issues such as the ease of implementation or the support for spatially extended objects.

Original languageEnglish
Title of host publicationProceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Number of pages10
Volume17
PublisherAssociation for Computing Machinery
Publication date2009
Pages236-245
ISBN (Print)978-1-60558-649-6
DOIs
Publication statusPublished - 2009
Event17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2009 - Seattle, United States
Duration: 4 Nov 20096 Nov 2009
Conference number: 17

Conference

Conference17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2009
Number17
Country/TerritoryUnited States
CitySeattle
Period04/11/200906/11/2009
SeriesGeographic Information Systems (GIS 09)
Number17

Keywords

  • Grid
  • R-tree
  • Indexing moving objects
  • Main-memory indexes

Fingerprint

Dive into the research topics of 'Trees or Grids? Indexing Moving Objects in Main Memory'. Together they form a unique fingerprint.

Cite this