Searching linear files on‐line

Abstract

Two types of linear on‐line search have been implemented on a data base of 100,000 INSPEC records, and compared with an inverted search program on the same file. It was found that the linear search which does a character‐by‐character scan of the whole file was too slow to be useful as an on‐line search, but that the second linear search, which uses a linear file of keys to select records for full scanning, was useable on‐line. An algorithm suitable for the on‐line searching of the linear file of keys is presented with run time nearly independent of the number of terms in the search query. Neither of the linear searches can compete with an inverted search in terms of user convenience, but they do not require as complex file‐maintenance software, they use less processing time to build indexes, and they have lower storage requirements than inverted files.

Citation

Hickey, T. (1977), "Searching linear files on‐line", Online Review, Vol. 1 No. 1, pp. 53-58. https://doi.org/10.1108/eb023935