Skip Navigation

The Computer Journal 1996 39(5):427-438; doi:10.1093/comjnl/39.5.427
© 1996 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Hui, L. C. K.
Right arrow Articles by Martel, C. U.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Randomized Competitive Algorithms for Successful and Unsuccessful Search

L. C. K. Hui1 * and C. U. Martel2 §

1 Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260, 2 Department of Computer Science, University of California, Davis, CA 95616, USA

This paper studies the classical dictionary problem using a self-adjusting linear list. We designed and analyzed randomized, on-line algorithms for a sequence of successful and unsuccessful searches which are competitive with off-line algorithms. Our algorithms combined the ps bit technique which speeds up unsuccessful search with the randomized move-to-front scheme of Reingold et al., which they used to speed up successful search.

Received May 3, 1995. revised June 7, 1996.

* Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260

§ Department of Computer Science, University of California, Davis, Davis, CA 95616, USA Email: lhui{at}iscs.nus.sg


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.