Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads

Darius Sidlauskas, Kenneth A. Ross, Christian Søndergaard Jensen, Simonas Saltenis

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

21 Citationer (Scopus)

Resumé

Modern processors consist of multiple cores that each support parallel processing by multiple physical threads, and they offer ample main-memory storage. This paper studies the use of such processors for the processing of update-intensive moving-object workloads that contain very frequent updates as well as contain queries.
The non-trivial challenge addressed is that of avoiding contention between long-running queries and frequent updates. Specifically, the paper proposes a grid-based indexing technique. A static grid indexes a near up-to-date snapshot of the data to support queries, while a live grid supports updates. An efficient cloning technique that exploits the memcpy system call is used to maintain the static grid.
An empirical study conducted with three modern processors finds that very frequent cloning, on the order of tens of milliseconds, is feasible, that the proposal scales linearly with the number of hardware threads, and that it significantly outperforms the previous state-of-the-art approach in terms of update throughput and query freshness.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind6849
Sider (fra-til)186-204
Antal sider19
ISSN0302-9743
DOI
StatusUdgivet - 2011
BegivenhedTwelffth International Symposium on Spatial and Temporal Databases - Mineapolis, USA
Varighed: 24 aug. 201126 jan. 2012
Konferencens nummer: 12

Konference

KonferenceTwelffth International Symposium on Spatial and Temporal Databases
Nummer12
LandUSA
ByMineapolis
Periode24/08/201126/01/2012

Fingerprint

Cloning
Moving Objects
Indexing
Thread
Workload
Update
Query
Grid
Processing
Throughput
Hardware
Data storage equipment
Snapshot
Contention
Parallel Processing
Empirical Study
Linearly

Citer dette

Sidlauskas, Darius ; Ross, Kenneth A. ; Jensen, Christian Søndergaard ; Saltenis, Simonas. / Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads. I: Lecture Notes in Computer Science. 2011 ; Bind 6849. s. 186-204.
@inproceedings{99f2e10f05fd45e6b10c873a9dc60a45,
title = "Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads",
abstract = "Modern processors consist of multiple cores that each support parallel processing by multiple physical threads, and they offer ample main-memory storage. This paper studies the use of such processors for the processing of update-intensive moving-object workloads that contain very frequent updates as well as contain queries.The non-trivial challenge addressed is that of avoiding contention between long-running queries and frequent updates. Specifically, the paper proposes a grid-based indexing technique. A static grid indexes a near up-to-date snapshot of the data to support queries, while a live grid supports updates. An efficient cloning technique that exploits the memcpy system call is used to maintain the static grid.An empirical study conducted with three modern processors finds that very frequent cloning, on the order of tens of milliseconds, is feasible, that the proposal scales linearly with the number of hardware threads, and that it significantly outperforms the previous state-of-the-art approach in terms of update throughput and query freshness.",
author = "Darius Sidlauskas and Ross, {Kenneth A.} and Jensen, {Christian S{\o}ndergaard} and Simonas Saltenis",
year = "2011",
doi = "10.1007/978-3-642-22922-0_12",
language = "English",
volume = "6849",
pages = "186--204",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Physica-Verlag",

}

Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads. / Sidlauskas, Darius; Ross, Kenneth A.; Jensen, Christian Søndergaard; Saltenis, Simonas.

I: Lecture Notes in Computer Science, Bind 6849, 2011, s. 186-204.

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

TY - GEN

T1 - Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads

AU - Sidlauskas, Darius

AU - Ross, Kenneth A.

AU - Jensen, Christian Søndergaard

AU - Saltenis, Simonas

PY - 2011

Y1 - 2011

N2 - Modern processors consist of multiple cores that each support parallel processing by multiple physical threads, and they offer ample main-memory storage. This paper studies the use of such processors for the processing of update-intensive moving-object workloads that contain very frequent updates as well as contain queries.The non-trivial challenge addressed is that of avoiding contention between long-running queries and frequent updates. Specifically, the paper proposes a grid-based indexing technique. A static grid indexes a near up-to-date snapshot of the data to support queries, while a live grid supports updates. An efficient cloning technique that exploits the memcpy system call is used to maintain the static grid.An empirical study conducted with three modern processors finds that very frequent cloning, on the order of tens of milliseconds, is feasible, that the proposal scales linearly with the number of hardware threads, and that it significantly outperforms the previous state-of-the-art approach in terms of update throughput and query freshness.

AB - Modern processors consist of multiple cores that each support parallel processing by multiple physical threads, and they offer ample main-memory storage. This paper studies the use of such processors for the processing of update-intensive moving-object workloads that contain very frequent updates as well as contain queries.The non-trivial challenge addressed is that of avoiding contention between long-running queries and frequent updates. Specifically, the paper proposes a grid-based indexing technique. A static grid indexes a near up-to-date snapshot of the data to support queries, while a live grid supports updates. An efficient cloning technique that exploits the memcpy system call is used to maintain the static grid.An empirical study conducted with three modern processors finds that very frequent cloning, on the order of tens of milliseconds, is feasible, that the proposal scales linearly with the number of hardware threads, and that it significantly outperforms the previous state-of-the-art approach in terms of update throughput and query freshness.

U2 - 10.1007/978-3-642-22922-0_12

DO - 10.1007/978-3-642-22922-0_12

M3 - Conference article in Journal

VL - 6849

SP - 186

EP - 204

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -