Item

Abstract

We consider search trees under time-varying access probabilities. Let $S = \{
B_1 , \cdots ,B_n \} $ and let $p_i^t $ be the number of accesses to object
$B_i $ up to time $t$, $W^t = \sum {p_i^t } $. We introduce D-trees with the
following properties.1) A search for $X = B_i $ at time $t$ takes time $O(\log
W^t /p_i^t )$. This is nearly optimal.2) Update time after a search is at most
proportional to search time, i.e. the overhead for administration is small.