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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

15 Citationer (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.
TidsskriftThe VLDB Journal
Udgave nummer5
Sider (fra-til)817-841
Antal sider25
StatusUdgivet - okt. 2014


Dyk ned i forskningsemnerne om 'Processing of Extreme Moving-Object Update and Query Workloads in Main Memory'. Sammen danner de et unikt fingeraftryk.