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

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.

1. Research and Markets. The world’s largest market research store. Available at: https://www.researchandmarkets.com (accessed 05.02.2021)

2. Reinsel D., Gantz J., Rydning J. The Digitization of the World From Edge to Core. Framingham: International Data Corporation. 2018. Available at: https://www.seagate.com/files/www-content/our-story/trends/files/idc-seagate-dataage-whitepaper.pdf (accessed 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. Available at: https://db.in.tum.de/~leis/papers/ART.pdf (accessed 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. Available at: http://kaldewey.com/pubs/FAST__SIGMOD10.pdf (accessed 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. Available at: https://doi.org/10.1007/s10586-017-1183-y (accessed 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. Available at: https://ieeexplore.ieee.org/abstract/document/8088597 (accessed 05.02.2021) DOI: 10.1109/CSCN.2017.8088597.

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