Amortized analyses of self-organizing sequential search heuristics

ABSTRACT

The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Anderson, E.J.. Nash, P.. and Weber. R.R. A counterexample to a conjecture on optimal list ordering. \. Appt. Prob. 19, 3 (1982), 730- 732.
• 3: Bellows, M.U. Performance of self-organizing sequential search heuristics under stochastic reference models. Ph.D. dissertation, Dept. of Statistics, Carnegie-Mellon Univ.. Pittsburgh, Pa.. 1983.
• 4: James Richard Bitner, Heuristics that dynamically alter data structures to reduce their access time., 1976
• 5: Bitner. J.R. Heuristics that dynamically organize data structures. SIAM /. Comput. 8, 1 (Feb. 1979). 82-110.
• 6: J. R. Bitner, Two Results on Self-organizing Data Structures, University of Texas at Austin, Austin, TX, 1982
• 7: Burville. P.J., and Kingman. J.F.C. On a model for storage and search. 1. App/. Prob. IO. 3 (Sept. 1973). 697-701.
• 8: Gannet, G., Munro. J.I.. and Suwanda, H. Toward self-organizing sequential search heuristics. In Proceedings of 20th IEEE Symposium Foundations Compufer Science, (San Juan, Puerto Rico, 1979). 169-174.
• 9: Gannet. G., Munro. J.I., and Suwanda. H. Exegisis of self-organizing linear search. SIAM 1. Compuf. IO. 3 (Aug. 1981) 613-637.
• 10: Leo R. Gotlieb, Data Types and Structures, Prentice Hall PTR, Upper Saddle River, NJ, 1978
• 11: Hendricks, W.J. The stationary distribution of an interesting Markov chain. 1, Appl. Prob. 9, 1 (Mar. 1972). 231-233.
• 12: Hendricks. W.J. An extension of a theorem concerning an interesting Markov chain. 1. Appl. Prob. IO. 4 (Dec. 1973). 886-890.
• 13: Hendricks. W.J. An account of self-organizing systems. SIAM J Comput, 5.4 (Dec. 1976). 715-723.
• 14: Kan. Y.C.. and Ross. S.M. Optimal list order under partial memory constraints. \. Appl. Prob. 17, 4 (Dec. 1980) 1004-1015.
• 15: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 16: Lam. K.. Sui. M.K.. and Yu. CT. A generalized counter scheme. Theoretical Compuf. Sci. 16. 3 {Dec. 1981) 271-278.
• 17: McCabe, J. On serial files with relocatable records. Oper. Res. 13,
• 18: McCreight. E. Personal communication, Xerox Palo Alto Research Center,Palo Alto, CA, Feb. 1983.
• 19: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 20: Schay. G.. Jr., and Dauer. F.W. A probabilistic model of a self-organizing file system. SlAM J Appl. Mafh. 15, 4 (Feb. 1967). 874-888.
• 21: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983 [doi>10.1145/800061.808752]
• 22: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 23: Aaron Tenenbaum, Simulations of dynamic sequential search algorithms, Communications of the ACM, v.21 n.9, p.790-791, Sept. 1978 [doi>10.1145/359588.359616]
• 24: Tenenbaum. A.. and Nemes. R.M. Two spectra of self-organizing sequential search algorithms. SIAM J Compuf. II. 3 (Aug. 1982). 557-566.
• 25: Veinott, A.F. Optimal policy in a dynamic, single product, nonstationary inventory mode with several demand classes. Oper. Res. 13, (1965); 761-778

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues; Tables**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Measurement, Performance, Theory