On efficient unsuccessful search

ABSTRACT

This paper introduces a general technique for speeding up unsuccessful search using very little extra space (2 bits per key). This technique is applicable to many data structures including linear lists, and search trees. For linear lists we get on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. In a virtual memory environment our self-adjusting algorithm for multi-way search trees is competitive with an optimal static multi-way tree and will often outperform the static tree.

REFERENCES

• Bay72: R. Bayer. Symmetric binary b-trees: data structure and maintenance algorithms. Acta Jn/ormactica, 1(4):290-306, 1972.
• BM83: J. Bentley and C. McGeoch. Worst-case analysis of self-organizing sequential search heuristics. In Proceedings of ~Oth Allerton Conference on Communication, Control, and Computing, pages 452-461, 1983.
• Fre84: Greg N. Frederickson, Self-organizing heuristics for implicit data structures, SIAM Journal on Computing, v.13 n.2, p.277-291, May 1984 [doi>10.1137/0213020]
• Fre85: Greg N. Frederickson, Implicit data structures for weighted elements, Information and Control, v.66 n.1-2, p.61-82, July/Aug. 1985 [doi>10.1016/S0019-9958(85)80013-9]
• Got81: L. Gotlieb. Optimal multi-way search trees. SIAM Journal on Computing, 10(3):422-433, 1981.
• HM91: L. Hui and C. Martel. On efficient unsuccess/ul search. Technical Report CSE-91-6, Computer Science Division, UC Davis, 1991.
• Knu73: 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
• Mar91: Charles Martel, Self-adjusting multi-way search trees, Information Processing Letters, v.38 n.3, p.135-141, May 7, 1991 [doi>10.1016/0020-0190(91)90235-A]
• McC65: J. McCabe. On serial files with relocatable records. Oper. Res., 12:609-618, 1965.
• MP91: A. Moffat and O. Petersson. Historical searching and sorting. 1991. manuscript.
• NMM88: D. Naor, C. Martel, and N. Matloff. Per/ormance o/ Priority Queue Structures in a Virtual Memory Environment. Technical Report (~SE-88-7, Computer Science Division, U C Davis, 1988.
• She89: Murray Sherk, Self-Adjusting k-ary Search Trees, Proceedings of the Workshop on Algorithms and Data Structures, p.381-392, August 17-19, 1989
• She90: M. Sherk. $el/-adjustin# k-ary search trees and sel/.adjusting balanced search trees. Technical Report 234/90, University of Toronto, February 1990.
• ST85a: 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]
• ST85b: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory, Verification