Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Darius Sidlauskas, Aalborg University, Denmark
  • Kenneth A. Ross, Columbia University, United States
  • Christian S. Jensen
  • ,
  • Simonas Saltenis, Daisy – Center for Data-intensive Systemer, Denmark
Modern processors consist of multiple cores that each support parallel processing by multiple physical threads, and they offer ample main-memory storage. This paper studies the use of such processors for the processing of update-intensive moving-object workloads that contain very frequent updates as well as contain queries.
The non-trivial challenge addressed is that of avoiding contention between long-running queries and frequent updates. Specifically, the paper proposes a grid-based indexing technique. A static grid indexes a near up-to-date snapshot of the data to support queries, while a live grid supports updates. An efficient cloning technique that exploits the memcpy system call is used to maintain the static grid.
An empirical study conducted with three modern processors finds that very frequent cloning, on the order of tens of milliseconds, is feasible, that the proposal scales linearly with the number of hardware threads, and that it significantly outperforms the previous state-of-the-art approach in terms of update throughput and query freshness.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)186-204
Number of pages19
Publication statusPublished - 2011
Event12th International Symposium on Spatial and Temporal Databasses. - Minneapolis, MN, United States
Duration: 24 Aug 201126 Aug 2011


Conference12th International Symposium on Spatial and Temporal Databasses.
CountryUnited States
CityMinneapolis, MN

Bibliographical note

Title of the vol.: Advances in Spatial and Temporal Databases. Proceedings / Dieter Pfoser, Yufei Tao, Kyriakos Mouratidis, Mario A. Nascimento, Mohamed Mokbel, Shashi Shekhar and Yan Huang (eds.)
ISBN: 978-3-642-22921-3

See relations at Aarhus University Citationformats

ID: 41486087