| A distribution sensitive data structure is one whose runtime performance can be measured in terms of some distributional statistic of the operations performed on the structure. In the first half of this thesis, distribution sensitive runtime characterizations of static, comparison-based dictionaries the relationships amongst and limitations of these characterizations are explored. It is conjectured that one existing runtime characterization, the working set property, is optimal when the total ordering of the underlying data is arbitrary. A new distribution sensitive characterization that is superior to all other known runtime characterizations of a comparison-based dictionary, the unified property, is introduced. In the second half of the thesis, data structures are presented that possess the desirable runtime characterizations formulated in the first half. Two new data structures, the working set structure and the unified structure, are presented and have their runtimes; bound by the working set property and the unified property, respectively. The unified structure satisfies the tightest known asymptotic bounds on its runtime of any known static, comparison-based dictionary. The working set structure has many of the desirable asymptotic properties of known structures, is easy to implement, and has excellent worst-case performance. The runtime characteristics presented can also be used to bound the runtime of some non-dictionary data structures. It is shown that the runtime of pairing heaps, a type of self adjusting heap, may be bounded by a variant of the working set property. A new data structure for planar point location that is asymptotically optimal when the point location queries are independently drawn from a known fixed distribution is also presented. |
