Processing of Extreme Moving-Object Update and Query Workloads in Main Memory

Research output: Contribution to journalJournal articleResearchpeer-review

15 Citations (Scopus)


The efficient processing of workloads that interleave moving-object updates and queries is challenging. In addition to the conflicting needs for update-efficient versus query-efficient data structures, the increasing parallel capabilities of multi-core processors yield challenges. To prevent concurrency anomalies and to ensure correct system behavior, conflicting update and query operations must be serialized. In this setting, it is a key concern to avoid that operations are blocked, which leaves processing cores idle.

To enable efficient processing, we first examine concurrency degrees from traditional transaction processing in the context of our target domain and propose new semantics that enable a high degree of parallelism and ensure up-to-date query results. We define the new semantics for range and k-nearest neighbor queries. Then we present a main-memory indexing technique called PGrid that implements the proposed semantics as well as two other variants supporting different semantics. This enables us to quantify the effects different degrees of consistency have on performance. We also present an alternative time-partitioning approach. Empirical studies with the above and three existing proposals conducted on modern processors show that our proposals scale near-linearly with the number of hardware threads and
thus are able to benefit from increasing on-chip parallelism.
Original languageEnglish
JournalThe VLDB Journal
Issue number5
Pages (from-to)817-841
Number of pages25
Publication statusPublished - Oct 2014


  • Spatio-temporal indexing
  • Thread-level parallelism
  • Concurrency


Dive into the research topics of 'Processing of Extreme Moving-Object Update and Query Workloads in Main Memory'. Together they form a unique fingerprint.

Cite this