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

Research output: Contribution to journalJournal articleResearchpeer-review

13 Citations (Scopus)

Abstract

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
Volume23
Issue number5
Pages (from-to)817-841
Number of pages25
ISSN1066-8888
DOIs
Publication statusPublished - Oct 2014

Fingerprint

Semantics
Data storage equipment
Processing
Data structures
Hardware

Keywords

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

Cite this

@article{b5f2b7aa905a41528a047e22e3b446c0,
title = "Processing of Extreme Moving-Object Update and Query Workloads in Main Memory",
abstract = "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 andthus are able to benefit from increasing on-chip parallelism.",
keywords = "Spatio-temporal indexing, Thread-level parallelism, Concurrency",
author = "Darius Sidlauskas and Simonas Saltenis and Jensen, {Christian S{\o}ndergaard}",
year = "2014",
month = "10",
doi = "10.1007/s00778-014-0353-2",
language = "English",
volume = "23",
pages = "817--841",
journal = "V L D B Journal",
issn = "1066-8888",
publisher = "Springer",
number = "5",

}

Processing of Extreme Moving-Object Update and Query Workloads in Main Memory. / Sidlauskas, Darius; Saltenis, Simonas; Jensen, Christian Søndergaard.

In: The VLDB Journal, Vol. 23, No. 5, 10.2014, p. 817-841.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

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

AU - Sidlauskas, Darius

AU - Saltenis, Simonas

AU - Jensen, Christian Søndergaard

PY - 2014/10

Y1 - 2014/10

N2 - 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 andthus are able to benefit from increasing on-chip parallelism.

AB - 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 andthus are able to benefit from increasing on-chip parallelism.

KW - Spatio-temporal indexing

KW - Thread-level parallelism

KW - Concurrency

U2 - 10.1007/s00778-014-0353-2

DO - 10.1007/s00778-014-0353-2

M3 - Journal article

VL - 23

SP - 817

EP - 841

JO - V L D B Journal

JF - V L D B Journal

SN - 1066-8888

IS - 5

ER -