Parallel implementation of R-trees on the GPU

Lijuan Luo, Martin D.F. Wong, Lance Leong

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

Abstract

R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30x speedup on R-tree query and more than 20x speedup on R-tree construction are achieved.

Original languageEnglish (US)
Title of host publicationASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
Pages353-358
Number of pages6
DOIs
StatePublished - Apr 26 2012
Event17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia
Duration: Jan 30 2012Feb 2 2012

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
CountryAustralia
CitySydney, NSW
Period1/30/122/2/12

Fingerprint

Data structures
Graphics processing unit
Experiments

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

Luo, L., Wong, M. D. F., & Leong, L. (2012). Parallel implementation of R-trees on the GPU. In ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference (pp. 353-358). [6164973] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2012.6164973

Parallel implementation of R-trees on the GPU. / Luo, Lijuan; Wong, Martin D.F.; Leong, Lance.

ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference. 2012. p. 353-358 6164973 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

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

Luo, L, Wong, MDF & Leong, L 2012, Parallel implementation of R-trees on the GPU. in ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference., 6164973, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 353-358, 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012, Sydney, NSW, Australia, 1/30/12. https://doi.org/10.1109/ASPDAC.2012.6164973
Luo L, Wong MDF, Leong L. Parallel implementation of R-trees on the GPU. In ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference. 2012. p. 353-358. 6164973. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2012.6164973
Luo, Lijuan ; Wong, Martin D.F. ; Leong, Lance. / Parallel implementation of R-trees on the GPU. ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference. 2012. pp. 353-358 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{e415c1eed8294867af6fb638ed7184e5,
title = "Parallel implementation of R-trees on the GPU",
abstract = "R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30x speedup on R-tree query and more than 20x speedup on R-tree construction are achieved.",
author = "Lijuan Luo and Wong, {Martin D.F.} and Lance Leong",
year = "2012",
month = "4",
day = "26",
doi = "10.1109/ASPDAC.2012.6164973",
language = "English (US)",
isbn = "9781467307727",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
pages = "353--358",
booktitle = "ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference",

}

TY - GEN

T1 - Parallel implementation of R-trees on the GPU

AU - Luo, Lijuan

AU - Wong, Martin D.F.

AU - Leong, Lance

PY - 2012/4/26

Y1 - 2012/4/26

N2 - R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30x speedup on R-tree query and more than 20x speedup on R-tree construction are achieved.

AB - R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30x speedup on R-tree query and more than 20x speedup on R-tree construction are achieved.

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

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

U2 - 10.1109/ASPDAC.2012.6164973

DO - 10.1109/ASPDAC.2012.6164973

M3 - Conference contribution

AN - SCOPUS:84859944365

SN - 9781467307727

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 353

EP - 358

BT - ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference

ER -