Abstract
This paper studies the classical Dictionary problem using a self-adjusting linear list. We design and analyze randomized, on-line algorithms for a sequence of successful and unsuccessful searches which are competitive with off-line algorithms. Our algorithms combine our ps bit technique which speeds up unsuccessful search with the randomized move-to-front scheme of Reingold, Westbrook, and Sleator, which they used to speed up successful search.
This work was supported by US National Science Foundation Grant CCR 90-23727
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Bentley and C. McGeoch. Worst-case analysis of self-organizing sequential search heuristics. In Proc. of 20th Allerton Conf. on Communication, Control, and Computing, pages 452–461, 1983.
G. Frederickson. Self-organizing heuristics for implicit data structures. SIAM Journal on Computing, 13(2):277–291, 1984.
L. Hui and C. Martel. On efficient unsuccessful search. In Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 217–227, 1992.
S. Irani, N. Reingold, J. Westbrook, and D. Sleator. Randomized competitive algorithms for the list update problem. In Proc. of the 2nd ACM-SIAM Symposium on Discrete Algorithms, pages 251–260, 1991.
J. McCabe. On serial files with relocatable records. Oper. Res., 12:609–618, 1965.
N. Reingold, J. Westbrook, and D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica, to appear.
D. Sleator and R. Tarjan. Amortized efficiency of list update and paging rules. Commun. of the A.C.M., 28(2):202–208, 1985.
D. Sleator and R. Tarjan. Self-adjusting binary search trees. J.A.C.M., 32(3):652–686, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hui, L.C.K., Martel, C.U. (1993). Randomized competitive algorithms for successful and unsuccessful search on self-adjusting linear lists. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds) Algorithms and Computation. ISAAC 1993. Lecture Notes in Computer Science, vol 762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57568-5_274
Download citation
DOI: https://doi.org/10.1007/3-540-57568-5_274
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57568-9
Online ISBN: 978-3-540-48233-8
eBook Packages: Springer Book Archive