Searching on a tape

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1990-10, Vol.39 (10), p.1265-1272
Main Authors: Hornick, S.W., Maddila, S.R., Mucke, E.P., Rosenberger, H., Skiena, S.S., Tollis, I.G.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Applied sciences
Computer science
Computer science
control theory
systems
Cost function
Data processing. List processing. Character string processing
Exact sciences and technology
Hidden Markov models
Magnetic heads
Memory organisation. Data processing
Probes
Programming
Read-write memory
Search problems
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.59856