An Advanced Bulk Loading Method for R-Tree with a Bucket Sort
Nam-Woo Kim, Miyoung Lee · 2012
Due to the explosive growth in use of LBS based mobile services, Global Positioning System (GPS) and Radio Frequency IDentification (RFID), the location and spatial data are growing exponentially. The index structure based on R tree is typically used in order to retrieve a large spatial data quickly. The Sort-Tile-Recursive (STR) method that is an efficient way to create R-tree index from large amounts of spatial data is widely known. The most time consuming part of STR method is to sort spatial data. To reduce sorting time, this paper proposes a method for creating an R-tree index which uses a bucket sort method to sort spatial data. The proposed method replaces a Sort Tile to a bucket sort to reduce indexing time. Experimental results show that the proposed method enhances the performance more than 7 times compared to STR method and it enhances the performance more than 19 times by using Graphic Processing Unit (GPU).