The Cell Tree: An Index for Geometric Databases

TitleThe Cell Tree: An Index for Geometric Databases
Publication TypeTechnical Report
Year of Publication1988
AuthorsGünther, O.
Other Numbers1215

This paper describes the design of the cell tree, an index structure for geometric databases. The data objects in the database are represented as unions of convex point sets (cells). The cell tree is a balanced tree structure whose leaves contain the cells and whose interior structure allows quick access to the cells (and thereby to the data objects), depending on their location in space. Furthermore, the cell tree is designed for paged memory: each node corresponds to a disk page. This minimizes the number of page faults occurring during a tree search. Point locations and range searches can therefore be carried out very efficiently using the cell tree.

Bibliographic Notes

ICSI Technical Report TR-88-002

Abbreviated Authors

O. Günther

ICSI Publication Type

Technical Report