Ромм Яков Евсеевич, заведующий кафедрой «Информатика», доктор технических наук, профессор
РФ, 347936, г. Таганрог, ул. Инициативная, д. 48
Romm, Yakov Ye. - Head of the Information Technology Department, Dr.Sci. (Eng.), professor
48, Initsiativnaya St., Taganrog, RF
Чабанюк Денис Андреевич, доцент кафедры «Теоретическая, общая физика и технологии»
РФ, 347936, г. Таганрог, ул. Инициативная, д. 48
Chabanyuk, Denis A. - associate professor of the Theoretical, General Physics and Technologies Department
48, Initsiativnaya St., Taganrog, RF
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.
Введение. Разработаны алгоритмы параллельного построения двоичного дерева. Алгоритмы выполнены на основе сортировки и описаны в конструктивной форме. Для множества из N элементов временная сложность имеет оценки T(R) = O(1) и T(R) = O(log2 N), где число процессоров R = (N2-N)/2. Дерево строится со свойством единственности. Алгоритмы инвариантны относительно вида входной последовательности. Целью работы являлась разработка и исследование способов ускорения процесса организации и преобразований древовидных структур данных на основе алгоритмов устойчивой максимально параллельной сортировки для их применения к базовым операциям информационного поиска в базах данных.
Материалы и методы. Взаимно однозначное соответствие множества входных элементов и построенного для него двоичного дерева устанавливается при помощи устойчивой адресной сортировки. Сортировка обладает максимальным параллелизмом, в операторной форме устанавливает взаимно однозначное соответствие входных и выходных индексов. На этой основе разрабатываются методы взаимного преобразования двоичных структур данных.
Результаты исследования. Получен эффективный параллельный алгоритм построения двоичного дерева на основе адресной сортировки с временной сложностью T(N2) = O(log2 N). От известных аналогов алгоритм отличается структурой и логарифмической оценкой временной сложности, позволяющей достигать ускорения аналогов порядка O(Nα), α≥1. В качестве усовершенствованного варианта предложена модификация алгоритма, обеспечивающая максимально параллельное построение двоичного дерева на основе устойчивой адресной сортировки и априорного вычисления хранимых индексов корней поддеревьев. Алгоритм отличается структурой и оценкой временной сложности T(1) = O(1). Аналогичная оценка достигается в последовательном варианте модифицированного алгоритма, что позволяет достигать ускорения известных аналогов порядка O(Nα), α>1.
Обсуждения и заключение. Полученные результаты направлены на организацию эффективных способов динамической обработки баз данных. Предложенные способы и алгоритмы могут составить алгоритмическую основу для ускоренного детерминированного поиска в реляционных базах данных и информационных системах.
The authors declare that there are no conflicts of interest present.