Heuristics That Dynamically Organize Data Structures
James R. Bitner · SIAM Journal on Computing · 1979
We first consider heuristics that dynamically alter linked lists, causing more frequently accessed keys to move nearer the “top” of the list. We show that the move to front rule reduces the access time much more quickly than the transposition rule, then give a “hybrid” of these two rules which decreases the access time quickly and has low asymptotic cost. We also discuss rules that assume a counter is associated with each key. Second, we consider rules for binary search trees. The monotonic tree rule performs well only when the entropy of the probability distribution for key requests is low; otherwise, it does not reduce the access time. A final class of rules using rotations give nearly optimal performance.
Cited by 139 works. doi:10.1137/0208007
Authors
References
- An Introduction to Probability Theory and Its Applications, Vol. 2
- Principles of mathematical analysis
- Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
- On self-organizing sequential search heuristics
- The stationary distribution of an interesting Markov chain
- Algorithm 230: Matrix Permutation
- On a model for storage and search
- On Serial Files with Relocatable Records
- A TOP-DOWN ALGORITHM FOR CONSTRUCTING NEARLY OPTIMAL LEXICOGRAPHIC TREES††This research was supported in part by the National Research Council of Canada.
- An extension of a theorem concerning an interesting Markov chain