Parallel R-Tree Search Algorithm on DSVM.

@inproceedings{DBLP:conf/dasfaa/WangHKM99,
  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, http://dblp.uni-trier.de}
}

Abstract

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.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Online Edition: IEEE Computer Society Digital Library

References

[1]

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

[2]

R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
BibTeX

[3]

Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167 BibTeX

[4]

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

[5]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[6]

Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204 BibTeX

[7]

Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX

[8]

Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX

[9]

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

[10]

Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX

[11]

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265 BibTeX

[12]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[13]

...

[14]

...