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) no. 3, pp. 251-269. 
@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},
     pages = {251--269},
     publisher = {EDP-Sciences},
     volume = {31},
     number = {3},
     year = {1997},
     mrnumber = {1483259},
     zbl = {0889.68115},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1997__31_3_251_0/}
}
TY  - JOUR
AU  - Messeguer, Xavier
TI  - Skip trees, an alternative data structure to skip lists in a concurrent approach
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1997
SP  - 251
EP  - 269
VL  - 31
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1997__31_3_251_0/
LA  - en
ID  - ITA_1997__31_3_251_0
ER  - 
%0 Journal Article
%A Messeguer, Xavier
%T Skip trees, an alternative data structure to skip lists in a concurrent approach
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1997
%P 251-269
%V 31
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1997__31_3_251_0/
%G en
%F 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) no. 3, pp. 251-269. http://archive.numdam.org/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 | Zbl

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

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 | Zbl

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

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

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 | Zbl

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

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

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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

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 | Zbl

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