Stochastic rearrangement rules for self-organizing data structures

DOI10.1007/BF01759046MaRDI QIDQ922688zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 2102775
• Comparison of self-organizing linear search rules
• List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations
• Efficient reorganization of binary search trees
• The Move-to-Front Rule for Multiple Lists

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3519671 (Why is no real title available?)
• An Account of Self-Organizing Systems
• Exegesis of Self-Organizing Linear Search
• Heuristics That Dynamically Organize Data Structures
• On Serial Files with Relocatable Records
• On self-organizing sequential search heuristics
• Self-adjusting binary search trees
• Self-organizing files with dependent accesses

Cited in

(14)

• scientific article; zbMATH DE number 480526 (Why is no real title available?)
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Self-Organizing Doubly-Linked Lists
• Self-organizing lists and independent references: A statistical synergy
• Properties of the promotion Markov chain on linear extensions
• An exact formula for the move-to-front rule for self-organizing lists
• Combinatorial Markov chains on linear extensions
• Random shuffles on trees using extended promotion
• Data structures with dynamical random transitions
• Markov Chains for Promotion Operators
• scientific article; zbMATH DE number 2102775 (Why is no real title available?)
• Eigenvalues of LRU via a linear algebraic approach
• Markov incremental constructions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922688)