References

moitvivt

Моделирование, оптимизация и информационные технологии

Modeling, Optimization and Information Technology

2310-6018

Издательство

10.26102/2310-6018/2021.32.1.014

913

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

Technology for executing retrieval queries to a database based on the CW-tree data indexing method

0000-0001-5121-201X

Шевский

Владислав Сергеевич

Shevskiy

Vladislav Sergeevich

immortalghost@yandex.ru aff-1

0000-0001-7140-1686

Шичкина

Юлия Александровна

Shichkina

Yulia Alexandrovna

strange.y@mail.ru aff-2

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина) Saint Petersburg Electrotechnical University "LETI"

01 01 2026

1 1

10.26102/2310-6018/2021.32.1.014

2026

This work is licensed under a Creative Commons Attribution 4.0 International License

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

Today in information technology there is a tendency to a multiple increase in the volume of stored data. The increase in data volumes is due to the global digitalization of various spheres of human life, the spread of the use of sensors for monitoring, diagnosing and controlling various objects. Despite the growing volumes, data still needs to be processed. Processing methods include an important retrieval step, the speed of which affects the efficiency of the entire processing. Therefore, developments in the field of accelerated retrieval for the necessary data for mining in various databases are relevant. This article proposes an algorithm developed by the authors based on the CW-tree data structure, which allows data to be indexed by maximizing the capabilities of a computing system in conditions of multithreaded query processing. The CW-tree data structure, also proposed by the authors, contains two levels which are the branch level, which is designed to retrieval for a vertex according to a user-specified query, and the leaf level, which is used to store data. This paper describes a method for traversing the CW-tree leaf level when executing a retrieval query to the database. The results of testing the proposed method on a test database are also given, and the results of a comparative analysis of the execution of retrieval queries to a database based on the CW-tree structure and a database controlled by the MySQL DBMS are presented.

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

database management systems tree algorithms data indexing multithreading database query optimization cW-tree

Исследование выполнено без спонсорской поддержки.

The study was performed without external funding.

References 1

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

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)

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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)

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.

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

The authors declare that there are no conflicts of interest present.