TY - GEN
T1 - Parallel implementation of R-trees on the GPU
AU - Luo, Lijuan
AU - Wong, Martin D.F.
AU - Leong, Lance
PY - 2012
Y1 - 2012
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
T2 - 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
Y2 - 30 January 2012 through 2 February 2012
ER -