Skip trees, an alternative data structure to skip lists in a concurrent approach
Messeguer, Xavier
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 251-269 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_3_251_0,
     author = {Messeguer, Xavier},
     title = {Skip trees, an alternative data structure to skip lists in a concurrent approach},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {251-269},
     mrnumber = {1483259},
     zbl = {0889.68115},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_3_251_0}
}

Messeguer, Xavier. Skip trees, an alternative data structure to skip lists in a concurrent approach. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 251-269. http://gdmltest.u-ga.fr/item/ITA_1997__31_3_251_0/

1. L. Bougé, J. Gabarró and X. Messeguer, Concurrent AVL revisited: self-balancing distributed search trees, Technical Report LSI-95-54, LSI-UPC, 1995. Also appeared as Tech. Rep. RR95-45, LIP, ENS Lyon.

2. H. Chernoff, A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations, Ann. Math. Statist., 1952, 23, pp. 493-507. | MR 57518 | Zbl 0048.11804

3. L. Devroye, A limit theory for random skip lists, The Annals of Applied Probability, 1992, 2 (3), pp. 597-609. | MR 1177901 | Zbl 0754.68039

4. G. Diehr and B. Faaland, Optimal pagination of B trees with variable-length items, Communications of the ACM, 1984, 27 (3), pp. 241-247. | MR 784129 | Zbl 0587.68061

5. E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens, On-the fly garbage collection: an exercise in cooperation, Communications of the ACM, 1978, 27, pp. 966-965. | Zbl 0386.68024

6. C. Douglas, The ubiquitous B-tree, Computing Surveys, 1979, 11(2), pp. 121-137. | Zbl 0419.68034

7. J. Gabarró, C. Martínez and X. Messeguer, A design of a parallel dictionary using skip lists, Theoretical Computer Science, 1996, 158, pp. 1-33. | MR 1388961 | Zbl 0871.68066

8. L. Guibas and R. Sedgewick, A dichromatic framework for balanced trees. In IEEE, editor, Proc. of 19th Symposium on Foundations of Computer Science, 1978, pp. 8-21. | MR 539826

9. L. Higham and E. Schenks, Maintaining B-trees on a EREW PRAM, J. of Parallel and Dist Comp., 1994, 22, pp. 329-335. | Zbl 0939.68599

10. J. L. W. Kessels, On-the-fly optimization of data structures, Comm. ACM, 1983, 26 (11), pp. 895-901. | Zbl 0519.68025

11. P. Kirschenhofer and H. Prodinger, The path length of random skip lists, Acta Informatica, 1994, to appear. | MR 1306099

12. E. Mccreight, Pagination of B* trees with variable length records, Communications of the ACM, 1977, 20, pp. 670-674.

13. O. Nurmi and E. Soisalon-Soininen, Chromatic binary search trees: A structure for concurrent rebalancing, Acta Informatica, 1995, 33 (6), pp. 547-557. Also appeared in l0th ACM PODS, 1991. | MR 1408046 | Zbl 0849.68026

14. O. Nurmi, E. Soisalon-Soininen and D. Wood, Concurrency control in database structures with relaxed balance, In 6th ACM PODS, 1987, pp. 170-176.

15. O. Nurmi, E. Soisalon-Soininen and D. Wood, Concurrent balancing and updating of avl trees, In 6th ACM PODS, 1987.

16. T. Ottmann, H. Six and D. Wood, On the correspondende between AVL trees and brother trees, Computing, 1979, 25 (1), pp. 43-54. | MR 620068 | Zbl 0399.68069

17. T. Papadakis, Skip Lists and Probabilistic Analysis of Algorithms, Ph.D. thesis, University of Waterloo, Available as Technical Report CS-93-28, 1993.

18. T. Papadakis, J. I. Munro and P. V. Poblete, Average search and update costs in skip lists, BIT, 1992, 32, pp. 316-332. | MR 1172193 | Zbl 0761.68030

19. W. Paul, Vishkin and H. Wagener, Parallel dictionaries on 2-3 trees, In J. DÍAZ Ed., Proc. 10th International Colloquium on Automata, Programming and Languages, LNCS 154, Springer-Verlag, 1983, pp. 597-609. | Zbl 0521.68070

Also appeared as "Parallel computation on 2-3 trees", in RAIRO Informatique Théorique, 1983, pp. 397-404. | Numdam | MR 743897

20. P. E. Pfeiffer, Probability for applications, Springer-Verlag, 1992. | MR 1028549 | Zbl 0693.60001

21. W. Pugh, Concurrent maintenance of skip lists, Technique Report CS-TR-2222.1, Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland, College Park, MD, Apr 1989. Also published as UMIACSTR-90-80.

22. W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, 1990, 33 (6), pp. 668-676. | MR 1035787

23. R. Seidel and R. Aragon, Randomized search trees, Algorithmica, 1996, 16(4/5), pp. 464-497. Appeared in Proc. of 30th Symposium on Foundations of Computer Science, 1989. | MR 1407585 | Zbl 0857.68030

24. S. Sen, Some observations on skip-lists, Information Processing Letters, 1991, 39 (3), pp. 173-176. | MR 1130745 | Zbl 0735.68018