Next: Evaluation Up: Performance Previous: Structure Operations

### Proximity Queries

The analysis of the neighbor finding routines in the Resize function is performed by calculating the number of nodes that are visited in the process. For the purpose of the Resize function only the nearest common ancestor is needed. The algorithm climbs up the tree until the lowest G-Node in the direction of the resize that is not the first or last child is returned, depending on the direction. Thus, the nodes at every other level are examined. In the worst-case, half of the nodes up the root need to be traversed, which costs O(d/2), d is the depth of the tree.

For an average case analysis, let's assume that the tree has w children at each node, and thus the depth of the tree is . Assume that the node is at index i and at level j. With probability , it is the first or last child, with probability it is in between. Thus, the number of nodes to be examined is as below:

This can be simplified to yield , which is as j goes to infinity.

The FindWindow function makes a point query, i.e. given the coordinates of a point finds the lowest-level rectangle it encapsulates. The algorithm, starting form the root node, traverses the tree down in the hierarchy on encapsulating nodes. Assuming, that each node has w children, in the worst case it costs if a linear search is made when determining the overlapping window over each children nodes. Performing a binary search will be much faster especially when w is large, in which case the algorithm performs in , i.e. , actually independent on the number children on the average.

Eser Kandogan
Sun Sep 13 18:34:46 EDT 1998

Web Accessibility