Title :
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
fDate :
10/1/1990 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
