Технология выполнения поисковых запросов к базе данных на основе метода индексации данных CW-tree

На сегодняшний день в информационных технологиях наблюдается тенденция к многократному увеличению объемов хранимых данных. Наращивание объемов данных обусловлено глобальной цифровизацией различных сфер жизнедеятельности человека, распространения использования датчиков мониторинга, диагностирования и управления различными объектами. Несмотря на растущие объемы, по-прежнему требуется обработка данных. Методы обработки включают важный этап поиска, скорость выполнения которого сказывается на эффективности всей обработки. Поэтому разработки в области ускоренного поиска необходимых данных для интеллектуального анализа в различных базах данных являются актуальными. В данной статье предлагается разработанный авторами алгоритм на основе структуры данных CW-tree, который позволяет индексировать данные, максимально используя возможности вычислительной системы в условиях многопоточной обработки запросов. Структура данных CW-tree, также предложенная авторами, содержит два уровня: уровень ветвей, который предназначен для поиска вершины по заданному в запросе пользователем условию, и уровень листьев, который предназначен для хранения данных. В настоящей работе описан метод прохода по уровню листьев CW-tree при выполнении поискового запроса к базе данных. Также приведены результаты тестирования предложенного метода на тестовой базе данных, результаты сравнительного анализа выполнения поисковых запросов к базе данных, основанной на структуре CW-tree, и базе данных под управлением СУБД MySQL.

1. Research and Markets. The world’s largest market research store. Доступен по: https://www.researchandmarkets.com (дата обращения: 05.02.2021)

2. Reinsel D., Gantz J., Rydning J. The Digitization of the World From Edge to Core. Framingham: International Data Corporation. 2018. Доступно по: https://www.seagate.com/files/www-content/our-story/trends/files/idc-seagate-dataage-whitepaper.pdf (дата обращения: 05.02.2021)

3. Vladislav Shevskiy. Constantly Wide Tree for Parallel Processing. 2019 Information Systems and Technologies in Modeling and Control on CEUR-WS.org (ISSN 1613-0073). ISTMC 2019 Conference. 2019;50-56.

4. Berchtold S.; Keim D.A., Kriegel H-P. The X-Tree: An Index Structure for High-Dimensional Data. Readings in multimedia computing and networking. 2001;451

5. Wang X., Meng W., Zhang M. A novel information retrieval method based on R-tree index for smart hospital information system. International Journal of Advanced Computer Research. 2019;9(42):133-45. DOI: 10.19101/IJACR.2019.940030.

6. Roumelis G., Vassilakopoulos M., Corral A., Manolopoulos Y. Efficient query processing on large spatial databases: A performance study. Journal of Systems and Software. 2017;132:165-85. DOI: 132. 10.1016/j.jss.2017.07.005.

7. Lehman T. J., Carey M. J. A study of index structures for main memory database management systems. University of Wisconsin-Madison Department of Computer Sciences. 1985.

8. Leis V., Kemper A., Neumann T. The adaptive radix tree: ARTful indexing for main-memory databases. 2013 IEEE 29th International Conference on Data Engineering (ICDE). 2013;38-49. Доступно по: https://db.in.tum.de/~leis/papers/ART.pdf (дата обращения: 05.02.2021). DOI: 10.1109/ICDE.2013.6544812.

9. Kim Ch., Chhugani J., Satish N., Sedlar E., Nguyen A., Kaldewey T., Lee V. W., Brandt S. A., Dubey P. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010;339-350. Доступно по: http://kaldewey.com/pubs/FAST__SIGMOD10.pdf (дата обращения: 05.02.2021). DOI: 10.1145/1807167.1807206.

10. Guang-Ho Ch., Chin-Wan Ch. The GC-tree: a high-dimensional index structure for similarity search in image databases. IEEE Transactions on Multimedia. 2002;4(2):235-247. DOI: 10.1109/TMM.2002.1017736.

11. Deniziak S., Michno T. New content-based image retrieval database structure using query by approximate shapes. 2017 Federated Conference on Computer Science and Information Systems (FedCSIS). 2017;613-621. DOI: 10.15439/2017F457.

12. Nowakova J., Prilepok M., Snasel V. Medical Image Retrieval Using Vector Quantization and Fuzzy S-tree. Journal of Medical Systems. 2017;41(2):1-6. DOI: 10.1007/s10916-016-0659-2.

13. Fonseca M. J., Jorge J. A. NB-Tree: An Indexing Structure for Content-Based Retrieval in Large Databases. In Proceedings of the 8th Int. Conf. on Database Systems for Advanced Applications. 2003;267-274

14. Shetty P., Spillane R., Malpani R., Andrews B., Seyster J., Zadok E. Building workload-independent storage with VT-trees. 11th {USENIX} Conference on File and Storage Technologies ({FAST} 13). 2013;17-30.

15. Ngu H. C. V., Huh J. B+-tree construction on massive data with Hadoop. Cluster Computing. 2019;22(1):1011–1021. Доступно по: https://doi.org/10.1007/s10586-017-1183-y (дата обращения: 05.02.2021)

16. Byung H. S., Lee B., Kyung T. K., Hee Y. Y. Enhanced query processing using weighted predicate tree in edge computing environment. 2017 IEEE Conference on Standards for Communications and Networking (CSCN). 2017;48-53. Доступно по: https://ieeexplore.ieee.org/abstract/document/8088597 (дата обращения: 05.02.2021) DOI: 10.1109/CSCN.2017.8088597.

17. Kubiatowicz J. Introduction to Parallel Architectures and Pthreads. Short Course on Parallel Programming. 2013.