Skip trees, an alternative data structure to skip lists in a concurrent approach

Xavier Messeguer

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)

  • Volume: 31, Issue: 3, page 251-269
  • ISSN: 0988-3754

How to cite

top

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 31.3 (1997): 251-269. <http://eudml.org/doc/92561>.

@article{Messeguer1997,
author = {Messeguer, Xavier},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Skip trees; Skip lists; sequential update algorithms; B-trees},
language = {eng},
number = {3},
pages = {251-269},
publisher = {EDP-Sciences},
title = {Skip trees, an alternative data structure to skip lists in a concurrent approach},
url = {http://eudml.org/doc/92561},
volume = {31},
year = {1997},
}

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
PB - EDP-Sciences
VL - 31
IS - 3
SP - 251
EP - 269
LA - eng
KW - Skip trees; Skip lists; sequential update algorithms; B-trees
UR - http://eudml.org/doc/92561
ER -

References

top
  1. 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. 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. Zbl0048.11804MR57518
  3. 3. L. DEVROYE, A limit theory for random skip lists, The Annals of Applied Probability, 1992, 2 (3), pp. 597-609. Zbl0754.68039MR1177901
  4. 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. Zbl0587.68061MR784129
  5. 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. Zbl0386.68024
  6. 6. C. DOUGLAS, The ubiquitous B-tree, Computing Surveys, 1979, 11(2), pp. 121-137. Zbl0419.68034
  7. 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. Zbl0871.68066MR1388961
  8. 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. MR539826
  9. 9. L. HIGHAM and E. SCHENKS, Maintaining B-trees on a EREW PRAM, J. of Parallel and Dist Comp., 1994, 22, pp. 329-335. Zbl0939.68599
  10. 10. J. L. W. KESSELS, On-the-fly optimization of data structures, Comm. ACM, 1983, 26 (11), pp. 895-901. Zbl0519.68025
  11. 11. P. KIRSCHENHOFER and H. PRODINGER, The path length of random skip lists, Acta Informatica, 1994, to appear. Zbl0804.60060MR1306099
  12. 12. E. MCCREIGHT, Pagination of B* trees with variable length records, Communications of the ACM, 1977, 20, pp. 670-674. 
  13. 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. Zbl0849.68026MR1408046
  14. 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. 15. O. NURMI, E. SOISALON-SOININEN and D. WOOD, Concurrent balancing and updating of avl trees, In 6th ACM PODS, 1987. Zbl1001.68509
  16. 16. T. OTTMANN, H. SIX and D. WOOD, On the correspondende between AVL trees and brother trees, Computing, 1979, 25 (1), pp. 43-54. Zbl0399.68069MR620068
  17. 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. 18. T. PAPADAKIS, J. I. MUNRO and P. V. POBLETE, Average search and update costs in skip lists, BIT, 1992, 32, pp. 316-332. Zbl0761.68030MR1172193
  19. 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. Zbl0521.68070
  20. Also appeared as "Parallel computation on 2-3 trees", in RAIRO Informatique Théorique, 1983, pp. 397-404. MR743897
  21. 20. P. E. PFEIFFER, Probability for applications, Springer-Verlag, 1992. Zbl0693.60001MR1028549
  22. 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. 
  23. 22. W. PUGH, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, 1990, 33 (6), pp. 668-676. MR1035787
  24. 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. Zbl0857.68030MR1407585
  25. 24. S. SEN, Some observations on skip-lists, Information Processing Letters, 1991, 39 (3), pp. 173-176. Zbl0735.68018MR1130745

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.