Searching on a tape

Author

Hornick, Scot W. ; Maddila, Sanjeev R. ; MÜcke, Ernst P. ; Rosenberger, Harald ; Skiena, Steven Sol ; Tollis, Ioannis G.

Author_Institution

Andersen Consulting Center for Strategic Technol. Res., Chicago, IL, USA

Volume

39

Issue

10

fYear

1990

fDate

10/1/1990 12:00:00 AM

Firstpage

1265

Lastpage

1272

Abstract

The problem of minimizing the average time to search for a key in a stored list of keys in a sequential access machine model (SAM) (e.g. a magnetic tape) is considered. The time to access a key in the list and the time to compare it to the given search key are taken into account. The time to access a key in the list is assumed proportional to the distance the head moves from its current location to reach the key. The time to read and compare the key to the search key is taken to be constant. Two classes of algorithms are analyzed and a matching lower bound on the average search time is presented. These results answer an open problem posed by S. Nishihara and H. Nishino (1987) regarding the optimal search algorithm for such a model. It is shown that the organization of the input data is crucial in determining the SAM complexity of the search problem

Keywords

search problems; SAM complexity; average search time; head; input data organisation; key access; key comparison; key search; lower bound; magnetic tape; optimal search algorithm; read; search key; sequential access machine model; stored list; Algorithm design and analysis; Computer science; Cost function; Hidden Markov models; Magnetic heads; Probes; Programming; Read-write memory; Search problems;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.59856

Filename

59856