Jump searching: a fast sequential search technique

ABSTRACT

When sequential file structures must be used and binary searching is not feasible, jump searching becomes an appealing alternative. This paper explores variants of the classic jump searching scheme where the optimum jump size is the square root of the number of records. Multiple level and variable size jump strategies are explored, appropriate applications are discussed and performance is evaluated.

REFERENCES

• 1: CODASYL Data Base Task Group Report, April 1971. Available from ACM, New York.
• 2: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Hwang, F.K., and Lin, S. A simple algorithm for merging two disjointed linearly ordered sets. SlAM J. Comptng. 1, 1 (March 1972), 31-39.
• 4: 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
• 5: James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 6: K. Maruyama , S. E. Smith, Analysis of design alternatives for virtual memory indexes, Communications of the ACM, v.20 n.4, p.245-254, April 1977 [doi>10.1145/359461.359471]
• 7: J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974 [doi>10.1145/356631.356634]
• 8: OS/VS Virtual Storage Method (VSAM) Planning Guide. Order No. GC26-3799, IBM Corp., White Plains, N.Y.
• 9: Pippenger, N. Group testing. IBM Res. Rep. RC.6218, IBM T. J. Watson Res. Ctr., Yorktown Heights, N.Y., Sept. 1976.
• 10: Shneiderman, B. Polynomial search. Software--Practice and Experience 3 (1973), 5-8.
• 11: Shneiderman, B. A model for optimizing indexed file structures. Int. J. Comptr. and Inform. Sci. 3, 1 (1974).
• 12: Ben Shneiderman, Batched searching of sequential and tree structured files, ACM Transactions on Database Systems (TODS), v.1 n.3, p.268-275, Sept. 1976 [doi>10.1145/320473.320487]
• 13: Strong, H.R., Markowsky, G., and Chandra, A.K. Searching within a page. IBM Res. Rep. RJ 2080, IBM Res. Lab., San Jose, Calif., Sept. 1977.
• 14: Wagner, R.E. Indexing design considerations. IBM Syst. J. 10, 4 (1973), 351-367.

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design, Management, Performance, Theory

Keywords:
database structures, file management, index searching, jump searching, search strategies, sequential files