Параллельное построение двоичного дерева на основе сортировки
Автор: Ромм Я.Е., Чабанюк Д.А.
Журнал: Вестник Донского государственного технического университета @vestnik-donstu
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 4 т.18, 2018 года.
Бесплатный доступ
Введение. Разработаны алгоритмы параллельного построения двоичного дерева. Алгоритмы выполнены на основе сортировки и описаны в конструктивной форме. Для множества из N элементов временная сложность имеет оценки T(R) = O(1) и T(R) = O(log2 N), где число процессоров R = (N2-N)/2. Дерево строится со свойством единственности. Алгоритмы инвариантны относительно вида входной последовательности. Целью работы являлась разработка и исследование способов ускорения процесса организации и преобразований древовидных структур данных на основе алгоритмов устойчивой максимально параллельной сортировки для их применения к базовым операциям информационного поиска в базах данных.Материалы и методы. Взаимно однозначное соответствие множества входных элементов и построенного для него двоичного дерева устанавливается при помощи устойчивой адресной сортировки. Сортировка обладает максимальным параллелизмом, в операторной форме устанавливает взаимно однозначное соответствие входных и выходных индексов...
Структуры данных, алгоритмы обработки данных, двоичное дерево, алгоритмы параллельной сортировки
Короткий адрес: https://sciup.org/142217059
IDR: 142217059 | DOI: 10.23947/1992-5980-2018-18-4-449-454
Список литературы Параллельное построение двоичного дерева на основе сортировки
- Ромм, Я. Е. Сравнение слов с единичной временной сложностью/Я. Е. Ромм, Д. А. Чабанюк//Известия Южного федер. ун-та. Технические науки. -2014. -№7 (156). -С. 230-238.
- Ромм, Я. Е. Параллельная сортировка слиянием по матрицам сравнений. II/Я. Е. Ромм//Кибернетика и системный анализ. -1995. -№ 4. -С. 13-37.
- Ромм, Я. Е. Построение двоичного дерева на основе параллельной сортировки/Я. Е. Ромм, Д. А. Чабанюк//Фундаментальные исследования. -2015. -Т. 8., № 3. -С. 509-513.
- Ромм, Я. Е. Параллельное построение двоичного дерева на основе сортировки/Я. Е. Ромм, Д. А. Чабанюк//Аспекты развития науки, образования и модернизации промышленности: матер. Всеросс. научно-практ. конф. -Таганрог, 2017. -Т. 1. -С. 77-84.
- 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
- 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
- Гавриков, А. В. Т-неприводимые расширения для ориентированных бинарных деревьев/А. В. Гавриков//Компьютерные науки и информационные технологии. -2016. -№ 6. -С. 123-125. -https://doi.org/10.17223/20710410/34/6
- Гриценко, Н. С. Построение двоичного дерева на основе модифицированной схемы хранения деревьев общего вида «left child»-«right sibling» (LCRS)/Н. С. Гриценко, Ю. С. Белов//Инженерный журнал: наука и инновации. -2014. -№ 3. -С. 75-84. -https://doi.org/10.18698/2308-6033-2014-3-1281.
- 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
- 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.
- 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
