Разработка алгоритма индексирования данных на основе структуры данных CW-tree с применением параллельных вычислений

Цель данного научного исследования состояла в разработке алгоритма индексирования данных с использованием технологий параллельных вычислений, применение которого приводило бы к уменьшению времени на обработку запросов к базе данных. В ходе исследования был разработан алгоритм индексирования данных на основе специальной структуры хранения данных на базе дерева, получившей название CW-tree (Constantly-Wide tree). Проход по CW-tree в соответствии с предлагаемым алгоритмом индексирования осуществляется в асинхронном режиме, что достигается благодаря использованию дополнительных стартовых вершин. Как показало тестирование, по сравнению с существующими аналогами алгоритмов индексирования предложенный алгоритм на основе CW-tree обладает преимуществами, главным из которых является полное распараллеливание поиска данных как на верхнем уровне, так и на уровне листьев дерева. Для установления эффекта от использования алгоритма CW-tree было проведено сравнительное исследование, а именно: чтение данных с применением B-tree, которое широко используется практически во всех современных системах управления базами данных, и чтение данных с применением предложенного CW-tree. В ходе исследования запросы к базе данных строились таким образом, чтобы проводился поиск по определенному ключу, устанавливалось, какой подход быстрее обработает некоторое число запросов поиска. Результаты проведенного тестирования показали, что на поиск данных в CW-tree затрачивается значительно меньше времени, чем на поиск в B-tree.

1. Nouri Z., Tu Y. GPU-Based Parallel Indexing for Concurrent Spatial Query Processing; Distributed and Parallel Databases. SSDBM'18: Proceedings of the 30th International Confer-ence on Scientific and Statistical Database Management. 2018;1–12. Доступно по: https://doi.org/10.1145/3221269.3221296 (дата обращения: 20.02.2020)

2. Shun J., Blelloch G. E. A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction. Proceedings of the Thirteenth Workshop on Algorithm En-gineering and Experiments (ALENEX). 2011;(1):48–58.

3. Jarke M., Koch J. Query optimization in database systems. ACM Computing Surveys (CsUR). 1984;16(2):111–152.

4. Smith J. M., Chang P. Y. T. Optimizing the performance of a relational algebra database interface. Communications of the ACM (CACM). 1975;18(10):568-579.

5. Wu S., Li F., Mehrotra S., Chhin Ooi B. Query Optimization for Massively Parallel Data Processing. SoCC Conference. 2011;(12):1–13.

6. Shnaiderman L., Shmueli O. A Parallel Tree Pattern Query Processing Algorithm for Graph Databases using a GPGPU. Proceedings of the Workshops of the EDBT/ICDT 2015 Joint Conference (EDBT/ICDT). 2015;1330(24):141. Доступно по: http://ceur-ws.org/Vol-1330/paper-24.pdf (дата обращения: 20.01.2020)

7. Battre D., Angulo D. S. MPI framework for parallel searching in large biological data-bases. Journal of Parallel and Distributed Computing. 2006;66(12):1503–1511.

8. Dewan H. M., Stolfo S. J. Scalable Parallel and Distributed Expert Database Systems with Predictive Load Balancing. Journal of Parallel and Distributed Computing. 1994;22(3):506–522.

9. Ren D. Q. Algorithm level power efficiency optimization for CPU-GPU processing element in data intensive SIMD/SPMD computing. Journal of Parallel and Distributed Computing. 2011;72(2):245–253.

10. Liu P., Sun W., Zhang J., Zheng B. An automaton-based index scheme supporting twig queries for on-demand XML data broadcast. Journal of Parallel and Distributed Computing. 2015;(86):82–97.

11. Wani M. A., Bhat W. A. Dataset for forensic analysis of B-tree file system. Data in Brief. 2018;(18):2013–2018.