Preview

Вестник Донского государственного технического университета

Расширенный поиск

Параллельное построение двоичного дерева на основе сортировки

https://doi.org/10.23947/1992-5980-2018-18-4-449-454

Полный текст:

Аннотация

Введение. Разработаны алгоритмы параллельного построения двоичного дерева. Алгоритмы выполнены на основе сортировки и описаны в конструктивной форме. Для множества из 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.

Обсуждения и заключение. Полученные результаты направлены на организацию эффективных способов динамической обработки баз данных. Предложенные способы и алгоритмы могут составить алгоритмическую основу для ускоренного детерминированного поиска в реляционных базах данных и информационных системах.

Об авторах

Я. Е. Ромм
Таганрогский институт имени А. П. Чехова (филиал) Ростовского государственного экономического университета (РИНХ)
Россия

Ромм Яков Евсеевич, заведующий кафедрой «Информатика», доктор технических наук, профессор

РФ, 347936, г. Таганрог, ул. Инициативная, д. 48



Д. А. Чабанюк
Таганрогский институт имени А. П. Чехова (филиал) Ростовского государственного экономического университета (РИНХ)
Россия

Чабанюк Денис Андреевич, доцент кафедры «Теоретическая, общая физика и технологии»

РФ, 347936, г. Таганрог, ул. Инициативная, д. 48



Список литературы

1. Ромм, Я. Е. Сравнение слов с единичной временной сложностью / Я. Е. Ромм, Д. А. Чабанюк // Известия Южного федер. ун-та. Технические науки. — 2014. — №7 (156). — С. 230–238.

2. Ромм, Я. Е. Параллельная сортировка слиянием по матрицам сравнений. II / Я. Е. Ромм // Кибернетика и системный анализ. — 1995. — № 4. — С. 13–37.

3. Ромм, Я. Е. Построение двоичного дерева на основе параллельной сортировки / Я. Е. Ромм, Д. А. Чабанюк // Фундаментальные исследования. — 2015. — Т. 8., № 3. — С. 509–513.

4. Ромм, Я. Е. Параллельное построение двоичного дерева на основе сортировки / Я. Е. Ромм, Д. А. Чабанюк // Аспекты развития науки, образования и модернизации промышленности : матер. Всеросс. научно-практ. конф. — Таганрог, 2017. — Т. 1. — С. 77–84.

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

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

7. Гавриков, А. В. Т-неприводимые расширения для ориентированных бинарных деревьев / А. В. Гавриков // Компьютерные науки и информационные технологии. — 2016. — № 6. — С. 123–125. — https://doi.org/10.17223/20710410/34/6

8. Гриценко, Н. С. Построение двоичного дерева на основе модифицированной схемы хранения деревьев общего вида «left child»-«right sibling» (LCRS) / Н. С. Гриценко, Ю. С. Белов // Инженерный журнал : наука и инновации. — 2014. — № 3. — С. 75–84. — https://doi.org/10.18698/2308-6033-2014-3-1281.

9. Amir A. Adaptive dictionary matching / A. Amir, M. Farach // Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. — IEEE, 1991. — P. 760-766. — https://doi.org/10.1109/SFCS.1991.185445

10. Fischer J. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE / J. Fischer, V. Heun // Combinatorial Pattern Matching – Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. – Vol. 4009. – P. 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. – № 56. — P. 410-423. https://doi.org/10.1109/FOCS.2015.32


Для цитирования:


Ромм Я.Е., Чабанюк Д.А. Параллельное построение двоичного дерева на основе сортировки. Вестник Донского государственного технического университета. 2018;18(4):449-454. https://doi.org/10.23947/1992-5980-2018-18-4-449-454

For citation:


Romm Y.E., Chabanyuk D.A. Parallel construction of binary tree based on sorting. Vestnik of Don State Technical University. 2018;18(4):449-454. (In Russ.) https://doi.org/10.23947/1992-5980-2018-18-4-449-454

Просмотров: 91


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)