Parallel R-tree search algorithm on DSVM

Abstract

Though parallel database systems have been extensively studied, as far as we know, the parallel algorithms of R-tree proposed so far are limited to one workstation with multiprocessors or multi disks, where a parallel sorting algorithm or concurrent I/O is used to improve the performance. For the searching of R-trees, multiple search paths from the root to leaves are traversed sequentially. This sequential traverse can be transformed into multiple parallel traverses based on multiple search paths, where the query is divided into subqueries which can be executed concurrently. Aiming at parallel I/O and CPU operations, we introduce a parallel R-tree search algorithm running on distributed shared virtual memory (DSVM), especially on Shusseuo which is an ODBMS providing global persistent object management on persistent DSVM. The related problems are discussed and the evaluations are made based on Shusseuo. Experimental results show that optimal performance can be reached in dealing with large volumes of data.