Blog
About

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

      Parallelize DSW Algorithm

      Preprint

      1 ,   , 1 , 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

          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.

          Related collections

          Most cited references 12

          • Record: found
          • Abstract: not found
          • Conference Proceedings: not found

          A dichromatic framework for balanced trees

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

            Efficient locking for concurrent operations on B-trees

             s. Yao,  Philip Lehman (1981)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              An Efficient Wait-Free Vector

                Bookmark

                Author and article information

                Journal
                ScienceOpen
                8 April 2019
                Affiliations
                [1 ] University of Central Florida
                Article
                10.14293/S2199-1006.1.SOR-.PPVOWYS.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