File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Unsuccessful Search in Self-Adjusting Data Structures

TitleUnsuccessful Search in Self-Adjusting Data Structures
Authors
Issue Date1993
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 1993, v. 15 n. 3, p. 447-481 How to Cite?
AbstractThis paper introduces a general technique for speeding up unsuccessful search using very little extra space (two bits per key). This technique is applicable to many data structures including linear lists and search trees. For linear lists we obtain on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. In a virtual memory environment our self-adjusting algorithm for multiway search trees is competitive with an optimal static multiway tree and will often outperform the static tree. We are also able to extend several other results for successful search to include both successful and unsuccessful searches. © 1993 Academic Press. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152380
ISSN
2011 Impact Factor: 0.5
2012 SCImago Journal Rankings: 0.469
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHui, LCKen_US
dc.contributor.authorMartel, Cen_US
dc.date.accessioned2012-06-26T06:37:47Z-
dc.date.available2012-06-26T06:37:47Z-
dc.date.issued1993en_US
dc.identifier.citationJournal Of Algorithms, 1993, v. 15 n. 3, p. 447-481en_US
dc.identifier.issn0196-6774en_US
dc.identifier.urihttp://hdl.handle.net/10722/152380-
dc.description.abstractThis paper introduces a general technique for speeding up unsuccessful search using very little extra space (two bits per key). This technique is applicable to many data structures including linear lists and search trees. For linear lists we obtain on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. In a virtual memory environment our self-adjusting algorithm for multiway search trees is competitive with an optimal static multiway tree and will often outperform the static tree. We are also able to extend several other results for successful search to include both successful and unsuccessful searches. © 1993 Academic Press. All rights reserved.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_US
dc.relation.ispartofJournal of Algorithmsen_US
dc.titleUnsuccessful Search in Self-Adjusting Data Structuresen_US
dc.typeArticleen_US
dc.identifier.emailHui, LCK:hui@cs.hku.hken_US
dc.identifier.authorityHui, LCK=rp00120en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1006/jagm.1993.1049en_US
dc.identifier.scopuseid_2-s2.0-3743101751en_US
dc.identifier.volume15en_US
dc.identifier.issue3en_US
dc.identifier.spage447en_US
dc.identifier.epage481en_US
dc.identifier.isiWOS:A1993MB99500005-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridHui, LCK=8905728300en_US
dc.identifier.scopusauthoridMartel, C=35589077100en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats