A spatial hash join algorithm suited for small buffer size
Miguel Rodrigues Fornari, Cirano Iochpe · 2004
In this paper, a new algorithm for spatial join operations is introduced. The so-called NRQB (No Replication with Quadtrees and Buckets Spatial Merge Join) enhances the original PBSM by partitioning the space according to the spatial distribution of the objects. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. The paper also presents a performance evaluation of the proposed algorithm relying on the results obtained by the execution of a series of test cases concerning different spatial join scenarios. In each test case, the response time of NRQB is compared with that of some well-known algorithms. The test cases were conducted with both synthetic and real data sets. The results showed that the new algorithm is best suited for smaller buffer sizes, which are typical of mobile devices and database systems for desktop computers.