Examining the I/O-Efficiency of Range Search on the Linear-Space
Multi-Level Grid File

by Stuart MacGillivray

We explore the use of multi-level grid files for I/O-efficient
orthogonal range search of a set of N points in d-dimensional space. The
multi-level extensions to the grid file remove previous bounds on its 
capacity, while maintaining its linear space complexity.

Joint work with Bradford G. Nickerson (UNB Faculty of Computer Science)