@inproceedings{774368d975194b2daa0865452270adf6,
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 30× speedup on R-tree query and more than 20× speedup on R-tree construction are achieved.",
keywords = "Graphics processing unit, Parallel processing, Arrays, Kernel, Sorting, Loading, Indexes",
author = "Lijuan Luo and Wong, {Martin D.F.} and Lance Leong",
note = "Funding Information: This work was partially supported by the National Science Foundation under grant CCF-1017516. Publisher copyright: {\textcopyright} 2012, IEEE; 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 ; Conference date: 30-01-2012 Through 02-02-2012",
year = "2012",
month = jan,
day = "30",
doi = "10.1109/ASPDAC.2012.6164973",
language = "English",
isbn = "9781467307703",
series = "Proceedings of the ASP-DAC Asia South Pacific Design Automation Conference",
publisher = "IEEE",
pages = "353--358",
booktitle = "17th Asia and South Pacific Design Automation Conference",
address = "United States",
}