Tree-based access methods for spatial databases: implementation and performance evaluation

Experiences with the implementation of the cell tree dynamic access method for spatial databases are reported, and the results of an experimental performance comparison with the R-tree of A. Guttman (1984) and with the R-tree of T. Sellis et al. (1987) are given. Cell tree design and implementation are discussed. Although the cell tree often requires more storage space and more CPU time to answer a search query, it usually obtains the results with a lower number of disk accesses than the two rival structures