Parallel main-memory indexing for moving-object query and update workloads

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

  • Darius Šidlauskas, Aalborg University, Denmark
  • Simonas Šaltenis, Aalborg University, Denmark
  • Christian S. Jensen, Denmark

We are witnessing a proliferation of Internet-worked, geo-positioned mobile devices such as smartphones and personal navigation devices. Likewise, location-related services that target the users of such devices are proliferating. Consequently, server-side infrastructures are needed that are capable of supporting the location-related query and update workloads generated by very large populations of such moving objects.

This paper presents a main-memory indexing technique that aims to support such workloads. The technique, called PGrid, uses a grid structure that is capable of exploiting the parallelism offered by modern processors. Unlike earlier proposals that maintain separate structures for updates and queries, PGrid allows both long-running queries and rapid updates to operate on a single data structure and thus offers up-to-date query results. Because PGrid does not rely on creating snapshots, it avoids the stop-the-world problem that occurs when workload processing is interrupted to perform such snapshotting. Its concurrency control mechanism relies instead on hardware-assisted atomic updates as well as object-level copying, and it treats updates as non-divisible operations rather than as combinations of deletions and insertions; thus, the query semantics guarantee that no objects are missed in query results.

Empirical studies demonstrate that PGrid scales near-linearly with the number of hardware threads on four modern multi-core processors. Since both updates and queries are processed on the same current data-store state, PGrid outperforms snapshot-based techniques in terms of both query freshness and CPU cycle-wise efficiency.
Original languageEnglish
Title of host publication Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data
Number of pages12
PublisherAssociation for Computing Machinery
Publication year2012
ISBN (print)978-1-4503-1247-9
Publication statusPublished - 2012
Event2012 ACM SIGMOD International Conference on Management of Data - Scottsdale, AZ, United States
Duration: 20 May 201225 May 2012


Conference2012 ACM SIGMOD International Conference on Management of Data
LandUnited States
ByScottsdale, AZ

See relations at Aarhus University Citationformats

ID: 52196003