Blog
About

266
views
1
recommends
+1 Recommend
1 collections
    31
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Parallelizing DSW Trees

      Preprint

        , 1

      ScienceOpen

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          A parallelization of the Day-Stout-Warren algorithm for balancing binary trees. As its input, this algorithm takes an arbitrary binary tree and returns an equivalent tree which is balanced so as to preserve the θ(log(n)) lookup time for elements of the tree. The sequential Day-Stout-Warren algorithm has a linear runtime and uses constant space. This new parallelization of the Day-Stout-Warren algorithm attempts to do the same while providing a speedup which is as near as possible to linear to the number of processing elements. Also, ideally it should do so in an online fashion, without blocking new reads, inserts, and deletes.

          Related collections

          Most cited references 8

          • Record: found
          • Abstract: not found
          • Article: not found

          An Efficient Wait-Free Vector

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A Wait-Free Hash Map

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists

                Bookmark

                Author and article information

                Journal
                ScienceOpen
                8 April 2019
                Affiliations
                [1 ] University of Central Florida
                Article
                10.14293/S2199-1006.1.SOR-.PPUPWPJ.v1

                This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

                Computer science

                Comments

                Comment on this article