This is the User's Guide for a n-dimensional R-tree index based on the Informix/Illustra DataBlade technology. This originated as a class project for CS286 taught by Professor Joe Hellerstein. This extension consists of data types and functions to support the storage and retrievel of objects in n-dimensional Cartesian space. The routines have been verified to work with Illustra Server 3.2 Release and the Illustra Spatial DataBlade Release 1.3 Tue Sep 12 22:17:31 PDT 1995 on Sun Solaris 2.5 and compiled with SPARCcompiler 3.0.1.

The Illustra R-tree access method requires that the spatial objects be represented as n-dimensional boxes. N-dimensional boxes are represented as an Illustra arrayof(real) or equivalently a mi_varlena where the first half of the array represent the lower-left coordinates of the box and the second half of the array define the upper-right coordinates of the box. I have included a routine called NdPnt2NdBox which converts a point into a box representation by copying the lower-left coordinates to the upper-right coordinates.

For more information about the R-tree access method, please consult the original paper by Guttman R-Trees: A Dynamic Index Structure for Spatial Searching which can be found in Readings in Database Systems: Second Edition edited by Michael Stonebraker.

    Components - Stored in the compressed tar file nd.tar.Z
  1. ndrtree.sql - Defines the data type and opclass for n-dimensional R-trees
  2. ndspatial.c - Contains the C functions to support the n-dimensional opclass
  3. Makefile - The Makefile for ndspatial.c
    Installation
  1. There is a subdirectory under the Illustra installation directory called extend. Create a directory there called spatialnd and extract the compressed tar file using the UNIX command uncompress -c nd.tar.Z | tar -xvf -.
  2. Compile the shared object file by typing make ndspatial.so.
  3. Install the Illustra Spatial DataBlade for your database if you have not already done so. Consult the Illusta Spatial DataBlade Guide for further instructions.
  4. Install the n-dimensional opclass. Change directory to extend/spatialnd. Then type msql -v database < ndrtree.sql.

If you have any questions about the implementation, found some bugs or done something interesting with the code, please let me know!

Copyright 1996 Andy Dong / University of California at Berkeley / All Rights Reserved.