Self-organizing linear search
- 1 September 1985
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 17 (3), 295-311
- https://doi.org/10.1145/5505.5507
Abstract
Algorithms that modify the order of linear search lists are surveyed. First the problem, including assumptions and restrictions, is defined. Next a summary of analysis techniques and measurements that apply to these algorithms is given. The main portion of the survey presents algorithms in the literature with absolute analyses when available. The following section gives relative measures that are applied between two or more algorithms. The final section presents open questions.Keywords
This publication has 11 references indexed in Scilit:
- Amortized analyses of self-organizing sequential search heuristicsCommunications of the ACM, 1985
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Self-Organizing Heuristics for Implicit Data StructuresSIAM Journal on Computing, 1984
- Exegesis of Self-Organizing Linear SearchSIAM Journal on Computing, 1981
- Heuristics That Dynamically Organize Data StructuresSIAM Journal on Computing, 1979
- Simulations of dynamic sequential search algorithmsCommunications of the ACM, 1978
- An Account of Self-Organizing SystemsSIAM Journal on Computing, 1976
- On self-organizing sequential search heuristicsCommunications of the ACM, 1976
- Properties of the working-set modelCommunications of the ACM, 1972
- On Serial Files with Relocatable RecordsOperations Research, 1965