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

      Parallelizing DSW Trees

      Preprint
      In review
      research-article
        1 ,
      ScienceOpen
      Bookmark

            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.

            Content

            Author and article information

            Journal
            ScienceOpen
            8 April 2019
            Affiliations
            [1 ] University of Central Florida
            Author information
            https://orcid.org/0000-0002-1281-826X
            Article
            10.14293/S2199-1006.1.SOR-.PPUPWPJ.v1
            aea3608c-7e12-4d26-a6cd-15af0a225114

            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 .

            History

            Computer science

            Comments

            Comment on this article