EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 31 / No 3 (1997) RAIRO-Theor. Inf. Appl., 31 3 (1997) 251-269 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 31, Number 3, 1997
Page(s) 251 - 269
DOI https://doi.org/10.1051/ita/1997310302511
Published online 01 February 2017
  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. [Google Scholar]
  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. [MR: 57518] [Zbl: 0048.11804] [Google Scholar]
  3. 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] [Google Scholar]
  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. [MR: 784129] [Zbl: 0587.68061] [Google Scholar]
  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. [Zbl: 0386.68024] [Google Scholar]
  6. 6. C. DOUGLAS, The ubiquitous B-tree, Computing Surveys, 1979, 11(2), pp. 121-137. [Zbl: 0419.68034] [Google Scholar]
  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. [MR: 1388961] [Zbl: 0871.68066] [Google Scholar]
  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. [MR: 539826] [Google Scholar]
  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. [Zbl: 0939.68599] [Google Scholar]
  10. 10. J. L. W. KESSELS, On-the-fly optimization of data structures, Comm. ACM, 1983, 26 (11), pp. 895-901. [Zbl: 0519.68025] [Google Scholar]
  11. 11. P. KIRSCHENHOFER and H. PRODINGER, The path length of random skip lists, Acta Informatica, 1994, to appear. [Zbl: 0804.60060] [MR: 1306099] [Google Scholar]
  12. 12. E. MCCREIGHT, Pagination of B* trees with variable length records, Communications of the ACM, 1977, 20, pp. 670-674. [Google Scholar]
  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. [MR: 1408046] [Zbl: 0849.68026] [Google Scholar]
  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. [Google Scholar]
  15. 15. O. NURMI, E. SOISALON-SOININEN and D. WOOD, Concurrent balancing and updating of avl trees, In 6th ACM PODS, 1987. [Zbl: 1001.68509] [Google Scholar]
  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. [MR: 620068] [Zbl: 0399.68069] [Google Scholar]
  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. [Google Scholar]
  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. [MR: 1172193] [Zbl: 0761.68030] [Google Scholar]
  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. [EuDML: 92196] [Zbl: 0521.68070] [Google Scholar]
  20. Also appeared as "Parallel computation on 2-3 trees", in RAIRO Informatique Théorique, 1983, pp. 397-404. [MR: 743897] [Google Scholar]
  21. 20. P. E. PFEIFFER, Probability for applications, Springer-Verlag, 1992. [MR: 1028549] [Zbl: 0693.60001] [Google Scholar]
  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. [Google Scholar]
  23. 22. W. PUGH, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, 1990, 33 (6), pp. 668-676. [MR: 1035787] [Google Scholar]
  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. [MR: 1407585] [Zbl: 0857.68030] [Google Scholar]
  25. 24. S. SEN, Some observations on skip-lists, Information Processing Letters, 1991, 39 (3), pp. 173-176. [MR: 1130745] [Zbl: 0735.68018] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.