Multidimensional range searching using G-tree and B*-tree indexing

Searching for ranges of values within a data space when those values are present within a single dimension or data field within the space may often be a simple extension of common indexing constructs such as red-black trees or B-Trees. However, when searches must occur to isolate records containing arbitrary ranges of values within two or more data fields of a data's schema, those constructs become less appropriate and may introduce substantial inefficiencies within the search operation. Hence, a significant amount of work has been done to address the problem of multi-dimensional range searching or indexing such that more sophisticated data structures may be applied to yield higher performance. These data structures include both grid-based partitioning methods as well as modified search tree constructs. Work presented here focuses on the G-Tree, a previously studied data structure that combines elements of both grid and tree based methods. More specifically, highly flexible disk and memory-based implementations of the G-Tree indexing construct have been created that rely on optimized versions of a B*-Tree data structure. In addition to describing the details of these implementations, performance results are also presented within the context of other competing strategies that highlight the strengths and superiority of G-Tree indexing. The created disk-based implementation was then used within a number of varied and diverse applications that could substantially benefit from its more performance oriented range search capabilities. Many of these applications utilize the G-Tree to index large data sets consisting of many gigabytes of data where the indexing structure was shown to be stable and scale gracefully. A summary of these applications within the areas of structural indexing, neural networks, and computational geometry is also presented.*; *This material is based upon work supported by the National Science Foundation under Grant No. 0239356.