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

      Parallelize DSW Algorithm

      Preprint
      In review
      research-article
        1 ,   1 , , 1
      ScienceOpen
      Bookmark

            Abstract

            In this project, we propose a parallelized DSW algorithm, useful to periodically rebalance an arbitrary unbalanced BST. The proposed algorithm splits the tree into several subtrees and concurrently do ``Tree-to-Vine'' to these subtrees using multiple threads, and finally connects them into a complete vine; It also splits the vine into several semi-equal sized subvines and do ``Vine-to-Tree'' to these subvines using multiple threads, and combines them into a complete balanced tree. Our extensive experiments including BST generation, ``Tree-to-Vine'', and ``Vine-to-Tree'' parallelization comparisons show that this parallelized DSW algorithm performs much better compared to its counterpart sequential DSW algorithm.

            Content

            Author and article information

            Journal
            ScienceOpen
            8 April 2019
            Affiliations
            [1 ] University of Central Florida
            Author information
            https://orcid.org/0000-0001-7803-4575
            Article
            10.14293/S2199-1006.1.SOR-.PPVOWYS.v1
            424b7593-24e7-4052-b310-2137f8ee9f0b

            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