Parallel R-Tree Search Algorithm on DSVM.

Botao Wang, Hiroyuki Horinokuchi, Kunihiko Kaneko, Akifumi Makinouchi: Parallel R-Tree Search Algorithm on DSVM. DASFAA 1999: 237-245
  author    = {Botao Wang and
               Hiroyuki Horinokuchi and
               Kunihiko Kaneko and
               Akifumi Makinouchi},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {Parallel R-Tree Search Algorithm on DSVM},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {237-245},
  ee        = {db/conf/dasfaa/WangHKM99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP,}


Though parallel database systems have been extensively studied, as far as we know, the parallel algorithms of R-tree propsed so far are limited to one workstation with multiprocessors or multi disks, where parallel sorting algorithm or concurrent I/O is used to improve the performance.

For the search of R-tree, 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.

In the paper, 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 volume of data.

Copyright © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


CDROM Version: Load the CDROM "DiSC, Volume 2 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Online Edition: IEEE Computer Society Digital Library

Citation Page


Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson: High-Performance Sorting on Networks of Workstations. SIGMOD Conference 1997: 243-254 BibTeX
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167 BibTeX
Ge Yu, Kunihiko Kaneko, Guangyi Bai, Akifumi Makinouchi: Transaction Management for a Distributed Object Storage System WAKASHI - Design, Implementation and Performance. ICDE 1996: 460-468 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204 BibTeX
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
DASFAA 1999 Proceedings: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:05:38 2009