Load balancing for processing spatio-temporal queries in multi-core settings

Anan Yaagoub*, Goce Trajcevski, Peter I Scheuermann, Nikos Hardavellas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We address the problem of efficiently parallelizing the processing of spatio-temporal range queries in multicore settings. Although the data set can be partitioned and assigned to individual cores for processing a collection of range queries, one cannot achieve an "ideal" assignment for all the cores' load. Hence, the cores should collaborate in a dynamic manner: ones that have completed their (sub)tasks should take part of the load from the cores that are still processing some of the data. We provide algorithms and synchronization data structures that achieve such collaborative behavior and we investigate their impact in different initial load-partitioning strategies. Our experiments demonstrate that about 40% speed-up can be gained when compared to static load-partitioning and that the proposed approach scales well.

Original languageEnglish (US)
Title of host publicationMobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012
Pages53-57
Number of pages5
DOIs
StatePublished - Jul 9 2012
Event11th ACM International Workshop on Data Engineering for Wireless and Mobile Access, MobiDE 2012 - In Conjunction with ACM SIGMOD / PODS 2012 - Scottsdale, AZ, United States
Duration: May 20 2012May 20 2012

Publication series

NameMobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012

Other

Other11th ACM International Workshop on Data Engineering for Wireless and Mobile Access, MobiDE 2012 - In Conjunction with ACM SIGMOD / PODS 2012
CountryUnited States
CityScottsdale, AZ
Period5/20/125/20/12

Fingerprint

Resource allocation
Processing
Data structures
Synchronization
Experiments

Keywords

  • Moving objects databases
  • Multicore processing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Cite this

Yaagoub, A., Trajcevski, G., Scheuermann, P. I., & Hardavellas, N. (2012). Load balancing for processing spatio-temporal queries in multi-core settings. In MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012 (pp. 53-57). (MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012). https://doi.org/10.1145/2258056.2258067
Yaagoub, Anan ; Trajcevski, Goce ; Scheuermann, Peter I ; Hardavellas, Nikos. / Load balancing for processing spatio-temporal queries in multi-core settings. MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012. 2012. pp. 53-57 (MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012).
@inproceedings{5db033538ee2467eb2d3155db05c9da8,
title = "Load balancing for processing spatio-temporal queries in multi-core settings",
abstract = "We address the problem of efficiently parallelizing the processing of spatio-temporal range queries in multicore settings. Although the data set can be partitioned and assigned to individual cores for processing a collection of range queries, one cannot achieve an {"}ideal{"} assignment for all the cores' load. Hence, the cores should collaborate in a dynamic manner: ones that have completed their (sub)tasks should take part of the load from the cores that are still processing some of the data. We provide algorithms and synchronization data structures that achieve such collaborative behavior and we investigate their impact in different initial load-partitioning strategies. Our experiments demonstrate that about 40{\%} speed-up can be gained when compared to static load-partitioning and that the proposed approach scales well.",
keywords = "Moving objects databases, Multicore processing",
author = "Anan Yaagoub and Goce Trajcevski and Scheuermann, {Peter I} and Nikos Hardavellas",
year = "2012",
month = "7",
day = "9",
doi = "10.1145/2258056.2258067",
language = "English (US)",
isbn = "9781450314428",
series = "MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012",
pages = "53--57",
booktitle = "MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012",

}

Yaagoub, A, Trajcevski, G, Scheuermann, PI & Hardavellas, N 2012, Load balancing for processing spatio-temporal queries in multi-core settings. in MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012. MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012, pp. 53-57, 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access, MobiDE 2012 - In Conjunction with ACM SIGMOD / PODS 2012, Scottsdale, AZ, United States, 5/20/12. https://doi.org/10.1145/2258056.2258067

Load balancing for processing spatio-temporal queries in multi-core settings. / Yaagoub, Anan; Trajcevski, Goce; Scheuermann, Peter I; Hardavellas, Nikos.

MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012. 2012. p. 53-57 (MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Load balancing for processing spatio-temporal queries in multi-core settings

AU - Yaagoub, Anan

AU - Trajcevski, Goce

AU - Scheuermann, Peter I

AU - Hardavellas, Nikos

PY - 2012/7/9

Y1 - 2012/7/9

N2 - We address the problem of efficiently parallelizing the processing of spatio-temporal range queries in multicore settings. Although the data set can be partitioned and assigned to individual cores for processing a collection of range queries, one cannot achieve an "ideal" assignment for all the cores' load. Hence, the cores should collaborate in a dynamic manner: ones that have completed their (sub)tasks should take part of the load from the cores that are still processing some of the data. We provide algorithms and synchronization data structures that achieve such collaborative behavior and we investigate their impact in different initial load-partitioning strategies. Our experiments demonstrate that about 40% speed-up can be gained when compared to static load-partitioning and that the proposed approach scales well.

AB - We address the problem of efficiently parallelizing the processing of spatio-temporal range queries in multicore settings. Although the data set can be partitioned and assigned to individual cores for processing a collection of range queries, one cannot achieve an "ideal" assignment for all the cores' load. Hence, the cores should collaborate in a dynamic manner: ones that have completed their (sub)tasks should take part of the load from the cores that are still processing some of the data. We provide algorithms and synchronization data structures that achieve such collaborative behavior and we investigate their impact in different initial load-partitioning strategies. Our experiments demonstrate that about 40% speed-up can be gained when compared to static load-partitioning and that the proposed approach scales well.

KW - Moving objects databases

KW - Multicore processing

UR - http://www.scopus.com/inward/record.url?scp=84863448202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863448202&partnerID=8YFLogxK

U2 - 10.1145/2258056.2258067

DO - 10.1145/2258056.2258067

M3 - Conference contribution

AN - SCOPUS:84863448202

SN - 9781450314428

T3 - MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012

SP - 53

EP - 57

BT - MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012

ER -

Yaagoub A, Trajcevski G, Scheuermann PI, Hardavellas N. Load balancing for processing spatio-temporal queries in multi-core settings. In MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012. 2012. p. 53-57. (MobiDE 2012 - Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access - In Conjunction with ACM SIGMOD / PODS 2012). https://doi.org/10.1145/2258056.2258067