The Cell Tree: An Index for Geometric Databases
| Title | The Cell Tree: An Index for Geometric Databases |
| Publication Type | Technical Report |
| Year of Publication | 1988 |
| Authors | Günther, O. |
| Other Numbers | 1215 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-88-002.pdf |
| Bibliographic Notes | ICSI Technical Report TR-88-002 |
| Abbreviated Authors | O. Günther |
| ICSI Publication Type | Technical Report |