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(log₂ N) estimates, where R = (N²-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(N²) = O(log₂ 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.

1. Romm, Ya.E., Chabanyuk, D.A. Sravnenie slov s edinichnoy vremennoy slozhnost'yu. [Comparison of words with the complexity of identity] Izvestiya SFedU. Engineering Sciences. 2014, no. 7 (156), pp. 230–238 (in Russian).

2. Romm, Ya.E. Parallel'naya sortirovka sliyaniem po matritsam sravneniy. II [Parallel sorting by merging on comparison matrices. II] Cybernetics and Systems Analysis, 1995, no. 4, pp. 13–37 (in Russian).

3. Romm, Y.E., Chabanyuk, D.A. Postroenie dvoichnogo dereva na osnove parallel'noy sortirovki. [Constructing binary tree based on parallel sorting algorithm.] Fundamental Research, 2015, vol. 8., no. 3, pp. 509–513 (in Russian).

4. Romm, Ya.E., Chabanyuk, D.A. Parallel'noe postroenie dvoichnogo dereva na osnove sortirovki. [Parallel construction of binary tree based on sorting algorithm.] Aspekty razvitiya nauki, obrazovaniya i modernizatsii promyshlennosti: mater. Vseross. nauchno-prakt. konf. [Aspects of development of science, education and industrial modernization: Proc. All-Russian Sci.-Pract. Conf.] Taganrog, 2017, vol. 1, pp. 77–84 (in Russian).

5. Laganà A., Kumar, A., Tan, V.C. Computational Science and Its Applications: Lecture Notes in Computer Science. Assisi: Springer Science & Business Media, 2004, 1044 p. – DOI: 10.1007/b98048

6. Chalermsook, P., Goswami, M., eds. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015). Piscataway, NJ: IEEE, 2015, pp. 410-423 – DOI: 10.1109/FOCS.2015.98

7. Gavrikov, A.V. T-neprivodimye rasshireniya dlya orientirovannykh binarnykh derev'yev. [T-irreducible extensions of directed binary trees.] Computer Sciences and Information Technologies, 2016, no. 6, pp. 123–125 – DOI 10.17223/20710410/34/6 (in Russian).

8. Gritsenko, N.S., Belov, Yu.S. Postroenie dvoichnogo dereva na osnove modifitsirovannoy skhemy khraneniya derev'yev obshchego vida «left child»-«right sibling» (LCRS). [Creation of a binary tree based on the modified storage diagram of general appearance trees "left child - right sibling" (LCRS).] Engineering Journal: Science and Innovation ,2014, no. 3, pp. 75–84 — DOI: 10.18698/2308-6033-2014-3-1281 (in Russian).

9. Amir, A., Farach, M., Adaptive dictionary matching. Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. IEEE, 1991, pp. 760-766 – DOI: 10.1109/SFCS.1991.185445

10. Fischer, J., Heun, V. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. Combinatorial Pattern Matching. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, vol. 4009, pp. 36-48.

11. Institute of Electrical and Electronics Engineers. Pattern-Avoiding Access in Binary Search Trees. Computer Society. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), 2015, no. 56, pp. 410-423 - DOI: 10.1109/FOCS.2015.32