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

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