Exegesis of Self-Organizing Linear Search

DOI10.1137/0210046zbMath0461.68064OpenAlexW2018317497MaRDI QIDQ3911408

Hendra Suwanda, Gaston H. Gonnet, J. Ian Munro

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0210046

zbMATH Keywords

asymptotic analysiscomplexity analysisself organizing files

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

Self-organizing sequential search and Hilbert's inequalities ⋮ An exact formula for the move-to-front rule for self-organizing lists ⋮ List update with probabilistic locality of reference ⋮ Deterministic optimal and expedient move-to-rear list organizing strategies ⋮ Stochastic rearrangement rules for self-organizing data structures ⋮ An optimal absorbing list organization strategy with constant memory requirements ⋮ Birthday paradox, coupon collectors, caching algorithms and self- organizing search ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ On the competitiveness of the move-to-front rule ⋮ Multiplicities of eigenvalues of some linear search schemes ⋮ On lookahead in the list update problem