Parallel implementation of R-trees on the GPU

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

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

35 Citations (Scopus)

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 30× speedup on R-tree query and more than 20× speedup on R-tree construction are achieved.
Original languageEnglish
Title of host publication17th Asia and South Pacific Design Automation Conference
PublisherIEEE Canada
Pages353-358
Number of pages6
ISBN (Electronic)9781467307727, 9781467307710
ISBN (Print)9781467307703
DOIs
Publication statusPublished - 30 Jan 2012
Event17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia
Duration: 30 Jan 20122 Feb 2012

Publication series

NameProceedings of the ASP-DAC Asia South Pacific Design Automation Conference
PublisherIEEE
ISSN (Print)2153-6961
ISSN (Electronic)2153-697X

Conference

Conference17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
Period30/01/122/02/12

User-Defined Keywords

  • Graphics processing unit
  • Parallel processing
  • Arrays
  • Kernel
  • Sorting
  • Loading
  • Indexes

Fingerprint

Dive into the research topics of 'Parallel implementation of R-trees on the GPU'. Together they form a unique fingerprint.

Cite this