## A Population Analysis for Hierachical Data Structures

Randal C. Nelson and Hanan Samet

Department of Computer Science

University of Rochester, University of Maryland

Rochester, NY 14627

**Abstract:**
A new method termed population analysis is presented for approximating
the distribution of node occupancies in hierarchical data structures
which store a variable number of geometric data items
per node.
The basic idea is to describe a dynamic data structure as a set of
populations which are permitted to transform into one another
according to certain rules.
The transformation rules are used
to obtain a set of equations describing a population distribution
which is stable under
insertion of additional information into the structure.
These equations can then be solved, either analytically or numerically, to
obtain the population distribution.
Hierarchical data structures are modeled by letting each population
represent the nodes of a given occupancy.
A detailed analysis of quadtree data structures for storing point data
is presented, and the results are compared to experimental data.
Two phenomena referred to as *aging*
and *phasing* are defined and shown to
account for the differences between the experimental results
and those predicted by the model.
The population technique is compared with statistical methods of analyzing
similar data structures.