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
Pages37-48
ISBN (print)978-1-4503-1247-9
DOIs
Publication statusPublished - 2012
Event2012 ACM SIGMOD International Conference on Management of Data - Scottsdale, AZ, United States
Duration: 20 May 201225 May 2012

Conference

Conference2012 ACM SIGMOD International Conference on Management of Data
LandUnited States
ByScottsdale, AZ
Periode20/05/201225/05/2012

See relations at Aarhus University Citationformats

ID: 52196003