Making data structures persistent. (English) Zbl 0667.68026

Making a change in an ordinary data structure destroys the old version, leaving only the new one. This paper investigates the problem of realizing persistent data structures in the sense that all the versions in the history of the data structure are available for use. Two kind of persistence are identified: partial persistence in which only the newest version may be updated and fully persistence in which an update operation may apply to any version. The authors study the case of linked data structures for which they propose two paradigms for making them persistent. These techniques are used to devise persistent forms of binary search trees with efficient implementations of the access, insertion and deletion operations.
Reviewer: M.Zimand


68P05 Data structures
68P10 Searching and sorting
68W99 Algorithms in computer science
Full Text: DOI Link


[1] Bayer, R.; McCreight, E., Organization of large ordered indexes, Acta inform., 1, 173-189, (1972) · Zbl 0226.68008
[2] Bentley, J.L.; Saxe, J.B., Decomposable searching problems 1: static-to-dynamic transformations, J. algorithms, 1, 301-358, (1980) · Zbl 0461.68065
[3] Blum, N.; Mehlhorn, K., On the average number of rebalancing operations in weight-balanced trees, Theoret. comput. sci., 11, 303-320, (1980) · Zbl 0435.68051
[4] Brown, M.R.; Tarjan, R.E., Design and analysis of a data structure for representing sorted lists, SIAM J. comput., 9, 594-614, (1980) · Zbl 0446.68047
[5] Chazelle, B., Filtering search: A new approach to query-answering, SIAM J. comput., 15, 703-724, (1986) · Zbl 0612.68088
[6] Chazelle, B., How to search in history, Inform. and control, 77, 77-99, (1985) · Zbl 0575.68062
[7] Chazelle, B.; Gubias, L.J., Fractional cascading: A data structuring technique with geometric applications (extended abstract), (), 90-100
[8] Chazelle, B.; Guibas, L.J., Fractional cascading I: A data structuring technique, Algorithmica, 1, 138-162, (1986) · Zbl 0639.68056
[9] Cole, R., Searching and storing similar lists, J. algorithms, 7, 202-220, (1986) · Zbl 0605.68053
[10] Dietz, P., Maintaining order in a linked List, (), 62-69
[11] Dietz, P.; Sleator, D.D., Two algorithms for maintaining order in a List, (), 365-372
[12] Dobkin, D.P.; Munro, J.I., Efficient uses of the past, (), 200-206
[13] Guibas, L.J.; Sedgewick, R., A dichromatic framework for balanced trees, (), 8-21
[14] Hood, R.; Melville, R., Real-time queue operations in pure LISP, Inform. process. lett., 13, 50-54, (1981)
[15] Huddleston, S.; Mehlhorn, K., Robust balancing in B-trees, (), 234-244
[16] Huddlfston, S.; Mehlhorn, K., A new data structure for representing sorted lists, Acta inform., 17, 157-184, (1982) · Zbl 0481.68061
[17] Huddleston, S., An efficient scheme for fast local updates in linear lists, (1981), Dept. of Information and Computer Science, University of California Irvine, CA
[18] Kosaraju, S.R., Localized search in sorted lists, (), 62-69
[19] Krijnen, T.; Meertens, L.G.L.T., Making B-trees work for B, (1983), The Mathematical Centre Amsterdam, The Netherlands, IW 219/83
[20] Maier, D.; Salveter, S.C., Hysterical B-trees, Inform. process. lett., 12, 199-202, (1981)
[21] Myers, E.W., AVL dags, (1982), Dept. of Computer Science, The University of Arizona Tucson, AZ, TR 82-9
[22] Myers, E.W., An applicative random-access stack, Inform. process. left., 17, 241-248, (1983) · Zbl 0572.68013
[23] Myers, E.W., Efficient applicative data types, (), 66-75
[24] Nievergelt, J.; Reingold, E.M., Binary search trees of bounded balance, SIAM J. comput., 2, 33-43, (1973) · Zbl 0262.68012
[25] {\scM. H. Overmars}, Searching in the past, I, Inform. and Computation, in press.
[26] Overmars, M.H., Searching in the past II: general transforms, ()
[27] Reps, T.; Teitelbaum, T.; Demers, A., Incremental context-dependent analysis for language-based editors, ACM trans. program. system. lang., 5, 449-477, (1983)
[28] Sarnak, N., Persistent data structures, () · Zbl 0667.68026
[29] Sarnak, N.; Tarjan, R.E., Planar point location using persistent search trees, Comm. ACM, 29, 669-679, (1986)
[30] Swart, G.F., Efficient algorithms for computing geometric intersections, ()
[31] Tarjan, R.E., Data structures and network algorithms, (1983), Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0584.68077
[32] Tarjan, R.E., Updating a balanced search tree in O(1) rotations, Inform. process. lett., 16, 253-257, (1983) · Zbl 0508.68041
[33] Tarjan, R.E., Amortized computational complexity, SIAM J. algebraic discrete methods, 6, 306-318, (1985) · Zbl 0599.68046
[34] Tsakalidis, A.K., Maintaining order in a generalized linked List, Acta inform., 21, 101-112, (1984) · Zbl 0515.68038
[35] Tsakalidis, A.K., AVL-trees for localized search, Inform. and control, 67, 173-194, (1985) · Zbl 0588.68033
[36] Tsakalidis, A.K., An optimal implementation for localized search, (1984), Fachbereich Angewandte Mathematik and Informatik, Universität des Saarlandes Saarbrücken, West Germany, A84/06
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.