Stochastic rearrangement rules for self-organizing data structures

DOI10.1007/BF01759046zbMath0711.68033OpenAlexW2062290471MaRDI QIDQ922688

Sanjiv Kapoor, Edward M. Reingold

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01759046

zbMATH Keywords

binary treesmove-to-front ruleslinear listsself-organizing data structures

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

An exact formula for the move-to-front rule for self-organizing lists ⋮ Eigenvalues of LRU via a linear algebraic approach ⋮ Markov Chains for Promotion Operators ⋮ Random shuffles on trees using extended promotion ⋮ A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements ⋮ Markov incremental constructions ⋮ Combinatorial Markov chains on linear extensions ⋮ Properties of the promotion Markov chain on linear extensions ⋮ Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement ⋮ Data structures on event graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Self-organizing files with dependent accesses
• Self-adjusting binary search trees
• Exegesis of Self-Organizing Linear Search
• On self-organizing sequential search heuristics
• An Account of Self-Organizing Systems
• Heuristics That Dynamically Organize Data Structures
• On Serial Files with Relocatable Records

This page was built for publication: Stochastic rearrangement rules for self-organizing data structures