[prev] 29 [next]

Costs of Search in Multi-d Trees

Difficult to determine cost precisely.

Best case: pmr query where all attributes have known values

  • in kd-trees and quad-trees, follow single tree path
  • cost is equal to depth D of tree
  • in R-trees, may follow several paths (overlapping partitions)
Typical case: some attributes are unknown or defined by range
  • need to visit multiple sub-trees
  • how many depends on: range, choice-points in tree nodes
Note: can view unknown value X=? as range min(X) ≤ X ≤ max(X)