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!
cited_by cdi_FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3
cites cdi_FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3
container_end_page 1272
container_issue 10
container_start_page 1265
container_title IEEE transactions on computers
container_volume 39
creator Hornick, S.W.
Maddila, S.R.
Mucke, E.P.
Rosenberger, H.
Skiena, S.S.
Tollis, I.G.
description 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.< >
doi_str_mv 10.1109/12.59856
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_12_59856</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>59856</ieee_id><sourcerecordid>28629704</sourcerecordid><originalsourceid>FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3</originalsourceid><addsrcrecordid>eNpFz71LA0EQBfBFFIxREKzs0ig2F2e_d0sJfkHAQq2Xvbk5Pbncxd2k8L_39IJWU8yPx3uMnXKYcw7-mou59k6bPTbhWtvCe2322QSAu8JLBYfsKOcPADAC_ISdPVNM-N50b7O-m8XZJq7pmB3Usc10srtT9np3-7J4KJZP94-Lm2WBEtSmsFJgqWvrASoCaRVqijVhSUZyVbmy4liVlg8FSuERozCldM4rZb3BSHLKLsfcdeo_t5Q3YdVkpLaNHfXbHIQzwltQA7waIaY-50R1WKdmFdNX4BB-Vgcuwu_qgV7sMmPG2NYpdtjkf--ddNzLwZ2PriGiv_eY8Q2G81xG</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>28629704</pqid></control><display><type>article</type><title>Searching on a tape</title><source>IEEE Xplore (Online service)</source><creator>Hornick, S.W. ; Maddila, S.R. ; Mucke, E.P. ; Rosenberger, H. ; Skiena, S.S. ; Tollis, I.G.</creator><creatorcontrib>Hornick, S.W. ; Maddila, S.R. ; Mucke, E.P. ; Rosenberger, H. ; Skiena, S.S. ; Tollis, I.G.</creatorcontrib><description>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.&lt; &gt;</description><identifier>ISSN: 0018-9340</identifier><identifier>EISSN: 1557-9956</identifier><identifier>DOI: 10.1109/12.59856</identifier><identifier>CODEN: ITCOB4</identifier><language>eng</language><publisher>New York, NY: IEEE</publisher><subject>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</subject><ispartof>IEEE transactions on computers, 1990-10, Vol.39 (10), p.1265-1272</ispartof><rights>1991 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3</citedby><cites>FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/59856$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,777,781,27905,27906,54777</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=19838193$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Hornick, S.W.</creatorcontrib><creatorcontrib>Maddila, S.R.</creatorcontrib><creatorcontrib>Mucke, E.P.</creatorcontrib><creatorcontrib>Rosenberger, H.</creatorcontrib><creatorcontrib>Skiena, S.S.</creatorcontrib><creatorcontrib>Tollis, I.G.</creatorcontrib><title>Searching on a tape</title><title>IEEE transactions on computers</title><addtitle>TC</addtitle><description>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.&lt; &gt;</description><subject>Algorithm design and analysis</subject><subject>Applied sciences</subject><subject>Computer science</subject><subject>Computer science; control theory; systems</subject><subject>Cost function</subject><subject>Data processing. List processing. Character string processing</subject><subject>Exact sciences and technology</subject><subject>Hidden Markov models</subject><subject>Magnetic heads</subject><subject>Memory organisation. Data processing</subject><subject>Probes</subject><subject>Programming</subject><subject>Read-write memory</subject><subject>Search problems</subject><subject>Software</subject><issn>0018-9340</issn><issn>1557-9956</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1990</creationdate><recordtype>article</recordtype><recordid>eNpFz71LA0EQBfBFFIxREKzs0ig2F2e_d0sJfkHAQq2Xvbk5Pbncxd2k8L_39IJWU8yPx3uMnXKYcw7-mou59k6bPTbhWtvCe2322QSAu8JLBYfsKOcPADAC_ISdPVNM-N50b7O-m8XZJq7pmB3Usc10srtT9np3-7J4KJZP94-Lm2WBEtSmsFJgqWvrASoCaRVqijVhSUZyVbmy4liVlg8FSuERozCldM4rZb3BSHLKLsfcdeo_t5Q3YdVkpLaNHfXbHIQzwltQA7waIaY-50R1WKdmFdNX4BB-Vgcuwu_qgV7sMmPG2NYpdtjkf--ddNzLwZ2PriGiv_eY8Q2G81xG</recordid><startdate>19901001</startdate><enddate>19901001</enddate><creator>Hornick, S.W.</creator><creator>Maddila, S.R.</creator><creator>Mucke, E.P.</creator><creator>Rosenberger, H.</creator><creator>Skiena, S.S.</creator><creator>Tollis, I.G.</creator><general>IEEE</general><general>Institute of Electrical and Electronics Engineers</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19901001</creationdate><title>Searching on a tape</title><author>Hornick, S.W. ; Maddila, S.R. ; Mucke, E.P. ; Rosenberger, H. ; Skiena, S.S. ; Tollis, I.G.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1990</creationdate><topic>Algorithm design and analysis</topic><topic>Applied sciences</topic><topic>Computer science</topic><topic>Computer science; control theory; systems</topic><topic>Cost function</topic><topic>Data processing. List processing. Character string processing</topic><topic>Exact sciences and technology</topic><topic>Hidden Markov models</topic><topic>Magnetic heads</topic><topic>Memory organisation. Data processing</topic><topic>Probes</topic><topic>Programming</topic><topic>Read-write memory</topic><topic>Search problems</topic><topic>Software</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hornick, S.W.</creatorcontrib><creatorcontrib>Maddila, S.R.</creatorcontrib><creatorcontrib>Mucke, E.P.</creatorcontrib><creatorcontrib>Rosenberger, H.</creatorcontrib><creatorcontrib>Skiena, S.S.</creatorcontrib><creatorcontrib>Tollis, I.G.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on computers</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hornick, S.W.</au><au>Maddila, S.R.</au><au>Mucke, E.P.</au><au>Rosenberger, H.</au><au>Skiena, S.S.</au><au>Tollis, I.G.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Searching on a tape</atitle><jtitle>IEEE transactions on computers</jtitle><stitle>TC</stitle><date>1990-10-01</date><risdate>1990</risdate><volume>39</volume><issue>10</issue><spage>1265</spage><epage>1272</epage><pages>1265-1272</pages><issn>0018-9340</issn><eissn>1557-9956</eissn><coden>ITCOB4</coden><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.&lt; &gt;</abstract><cop>New York, NY</cop><pub>IEEE</pub><doi>10.1109/12.59856</doi><tpages>8</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0018-9340
ispartof IEEE transactions on computers, 1990-10, Vol.39 (10), p.1265-1272
issn 0018-9340
1557-9956
language eng
recordid cdi_crossref_primary_10_1109_12_59856
source IEEE Xplore (Online service)
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
title Searching on a tape
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-19T09%3A10%3A15IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Searching%20on%20a%20tape&rft.jtitle=IEEE%20transactions%20on%20computers&rft.au=Hornick,%20S.W.&rft.date=1990-10-01&rft.volume=39&rft.issue=10&rft.spage=1265&rft.epage=1272&rft.pages=1265-1272&rft.issn=0018-9340&rft.eissn=1557-9956&rft.coden=ITCOB4&rft_id=info:doi/10.1109/12.59856&rft_dat=%3Cproquest_cross%3E28629704%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c304t-732cb5f7900de0374c5eafecbe6314d8bd1cdb71956b29cca26b388944796cae3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=28629704&rft_id=info:pmid/&rft_ieee_id=59856&rfr_iscdi=true