Parallel construction of binary tree based on sorting
Introduction. Algorithms for the parallel binary tree construction are developed. The algorithms are based on sorting and described in a constructive form. For the Nelement set, the time complexity has T(R) = O(1) and T(R) = O(log2 N) estimates, where R = (N2-N)/2 is the number of processors. The tr...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Don State Technical University
2018-12-01
|
| Series: | Advanced Engineering Research |
| Subjects: | |
| Online Access: | https://www.vestnik-donstu.ru/jour/article/view/1440 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849408918838575104 |
|---|---|
| author | Ya. E. Romm D. A. Chabanyuk |
| author_facet | Ya. E. Romm D. A. Chabanyuk |
| author_sort | Ya. E. Romm |
| collection | DOAJ |
| description | Introduction. Algorithms for the parallel binary tree construction are developed. The algorithms are based on sorting and described in a constructive form. For the Nelement set, the time complexity has T(R) = O(1) and T(R) = O(log2 N) estimates, where R = (N2-N)/2 is the number of processors. The tree is built with the uniqueness property. The algorithms are invariant with respect to the input sequence type. The work objective is to develop and study ways of accelerating the process of organizing and transforming the tree-like data structures on the basis of the stable maximum parallel sorting algorithms for their application to the basic operations of information retrieval on databases.Materials and Methods. A one-to-one relation between the input element set and the binary tree built for it is established using a stable address sorting. The sorting provides maximum concurrency, and, in an operator form, establishes a one-to-one mapping of input and output indices. On this basis, methods for the mutual transformation of the binary data structures are being developed.Research Results. An efficient parallel algorithm for constructing a binary tree based on the address sorting with time complexity of T(N2) = O(log2 N) is obtained. From the well-known analogues, the algorithm differs in structure and logarithmic estimation of time complexity, which makes it possible to achieve the acceleration of O(Nα), α≥1 order analogues. As an advanced version, an algorithm modification, which provides the maximum parallel construction of the binary tree based on a stable address sorting and a priori calculation of the stored subtree root indices is suggested. The algorithm differs in structure and estimation of T(1) = O(1) time complexity. A similar estimate is achieved in a sequential version of the modified algorithm, which allows obtaining the acceleration of known analogs O(Nα), α>1 order.Discussion and Conclusions. The results obtained are focused on the creation of effective methods for the dynamic database processing. The proposed methods and algorithms can form an algorithmic basis for an advanced deterministic search on the relational databases and information systems. |
| format | Article |
| id | doaj-art-01ee2010592e49b4b148468de04a0c40 |
| institution | Kabale University |
| issn | 2687-1653 |
| language | Russian |
| publishDate | 2018-12-01 |
| publisher | Don State Technical University |
| record_format | Article |
| series | Advanced Engineering Research |
| spelling | doaj-art-01ee2010592e49b4b148468de04a0c402025-08-20T03:35:40ZrusDon State Technical UniversityAdvanced Engineering Research2687-16532018-12-0118444945410.23947/1992-5980-2018-18-4-449-4541392Parallel construction of binary tree based on sortingYa. E. Romm0D. A. Chabanyuk1Taganrog Chekhov Institute, Rostov State University of Economics (RINH) branchTaganrog Chekhov Institute, Rostov State University of Economics (RINH) branchIntroduction. Algorithms for the parallel binary tree construction are developed. The algorithms are based on sorting and described in a constructive form. For the Nelement set, the time complexity has T(R) = O(1) and T(R) = O(log2 N) estimates, where R = (N2-N)/2 is the number of processors. The tree is built with the uniqueness property. The algorithms are invariant with respect to the input sequence type. The work objective is to develop and study ways of accelerating the process of organizing and transforming the tree-like data structures on the basis of the stable maximum parallel sorting algorithms for their application to the basic operations of information retrieval on databases.Materials and Methods. A one-to-one relation between the input element set and the binary tree built for it is established using a stable address sorting. The sorting provides maximum concurrency, and, in an operator form, establishes a one-to-one mapping of input and output indices. On this basis, methods for the mutual transformation of the binary data structures are being developed.Research Results. An efficient parallel algorithm for constructing a binary tree based on the address sorting with time complexity of T(N2) = O(log2 N) is obtained. From the well-known analogues, the algorithm differs in structure and logarithmic estimation of time complexity, which makes it possible to achieve the acceleration of O(Nα), α≥1 order analogues. As an advanced version, an algorithm modification, which provides the maximum parallel construction of the binary tree based on a stable address sorting and a priori calculation of the stored subtree root indices is suggested. The algorithm differs in structure and estimation of T(1) = O(1) time complexity. A similar estimate is achieved in a sequential version of the modified algorithm, which allows obtaining the acceleration of known analogs O(Nα), α>1 order.Discussion and Conclusions. The results obtained are focused on the creation of effective methods for the dynamic database processing. The proposed methods and algorithms can form an algorithmic basis for an advanced deterministic search on the relational databases and information systems.https://www.vestnik-donstu.ru/jour/article/view/1440data structuresdata processing algorithmsbinary treealgorithms for parallel sorting |
| spellingShingle | Ya. E. Romm D. A. Chabanyuk Parallel construction of binary tree based on sorting Advanced Engineering Research data structures data processing algorithms binary tree algorithms for parallel sorting |
| title | Parallel construction of binary tree based on sorting |
| title_full | Parallel construction of binary tree based on sorting |
| title_fullStr | Parallel construction of binary tree based on sorting |
| title_full_unstemmed | Parallel construction of binary tree based on sorting |
| title_short | Parallel construction of binary tree based on sorting |
| title_sort | parallel construction of binary tree based on sorting |
| topic | data structures data processing algorithms binary tree algorithms for parallel sorting |
| url | https://www.vestnik-donstu.ru/jour/article/view/1440 |
| work_keys_str_mv | AT yaeromm parallelconstructionofbinarytreebasedonsorting AT dachabanyuk parallelconstructionofbinarytreebasedonsorting |