Создание частичного индексирования таблицы для оптимизации поисковых запросов

Аннотация

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

Сведения об авторах

Artem Igorevich Mironov, Смоленский государственный университет

аспирант физико-математического факультета

Victor Iosifovich Munerman, Смоленский государственный университет

доцент кафедры информатики физико-математического факультета, кандидат технических наук, доцент

Литература

1. Abdel-Basset M., Manogaran G., Abdel-Fatah L., Mirjalili S. An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems. Personal and Ubiquitous Computing. 2018;22(5-6):1117-1132. doi: https://doi.org/10.1007/s00779-018-1132-7
2. Chamoso P., Rivas A., Sánchez-Torres R., Rodríguez S. Social computing for image matching. PLOS ONE. 2018;13(5):e0197576. doi: https://doi.org/10.1371/journal.pone.0197576
3. Das S., Grbic M., Ilic I., Jovandic I., Jovanovic A., Narasayya V.R., Radulovic M., Stikic M., Xu G., Chaudhuri S. Automatically Indexing Millions of Databases in Microsoft Azure SQL Database. In: Proceedings of the 2019 International Conference on Management of Data (SIGMOD'19). New York, NY, USA: Association for Computing Machinery; 2019. p. 666-679. doi: https://doi.org/10.1145/3299869.3314035
4. Dodonov A., Mukhin V., Zavgorodnii V., Kornaga Ya., Zavgorodnya A., Mukhin O. Method of Parallel Information Object Search in Unified Information Spaces. International Journal of Computer Network and Information Security. 2021;13(4):1-13. doi: https://doi.org/10.5815/ijcnis.2021.04.01
5. Gorokhovatskyi V.A., Gorokhovatskiy A.V., Peredrii Ye.О. Hashing of structural descriptions at building of the class image descriptor, computing of relevance and classification of the visual objects. Telecommunications and Radio Engineering. 2018;77(13):1159-1168. Available at: https://openarchive.nure.ua/server/api/core/bitstreams/00ab1f8f-d40e-49ee-8540-da9d745c1be4/content (accessed 23.06.2022).
6. Graefe G. Modern B-Tree Techniques. Foundations and Trends® in Databases. 2011;3(4):203-402. doi: http://dx.doi.org/10.1561/1900000028
7. Haynes D., Ray S., Manson S.M., Soni A. High performance analysis of big spatial data. In: 2015 IEEE International Conference on Big Data (Big Data). Santa Clara, CA, USA: IEEE Computer Society; 2015. p. 1953-1957. doi: https://doi.org/10.1109/BigData.2015.7363974
8. Pan V.Y., Yu Y., Stewart C. Algebraic and Numerical Techniques for the Computation of Matrix Determinants. Computers & Mathematics with Applications. 1997;34(1):43-70. doi: https://doi.org/10.1016/S0898-1221(97)00097-7
9. Kirikova A., Mironov A. Using Metadata-indexing to Improve the Efficiency of Complex Operations. In: 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg, Moscow, Russia: IEEE Computer Society; 2021. p. 2124-2127. doi: https://doi.org/10.1109/ElConRus51938.2021.9396274
10. Kirikova A., Mironov A., Munerman V. The Method of Composition Hash-functions for Optimize a Task of Searching Images in Dataset. In: 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). St. Petersburg and Moscow, Russia: IEEE Computer Society; 2020. p. 1983-1986. doi: https://doi.org/10.1109/EIConRus49466.2020.9038919
11. Levin N.A., Munerman V.I. Models of Big Data Processing in Massively Parallel Systems. Highly Available Systems. 2013;9(1):035-043. Available at: https://www.elibrary.ru/item.asp?id=18928468 (accessed 23.06.2022).
12. Lomet D. The evolution of effective B-tree: Page organization and techniques: A personal account. ACM SIGMOD Record. 2001;30(3):64-69. doi: https://doi.org/10.1145/603867.603878
13. Lvovich I., Lvovich Y., Preobrazhenskiy A., Choporov O. Modeling and Optimization of Processing Large Data Arrays in Information Systems. In: 2021 International Conference on Information Technology and Nanotechnology (ITNT). Samara, Russian Federation: IEEE Computer Society; 2021. p. 1-5. doi: https://doi.org/10.1109/ITNT52450.2021.9649229
14. Monga V., Evans B.L. Perceptual image hashing via feature points: performance evaluation and tradeoffs. IEEE Transactions on Image Processing. 2006;15(11):3452-3465. doi: https://doi.org/10.1109/TIP.2006.881948
15. Munerman V., Munerman D. Realization of Distributed Data Processing on the Basis of Container Technology. In: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). Saint Petersburg and Moscow, Russia; IEEE Computer Society; 2019. p. 1740-1744. doi: https://doi.org/10.1109/EIConRus.2019.8656766
16. Munerman V., Munerman D., Samoilova T. The Heuristic Algorithm For Symmetric Horizontal Data Distribution. In: 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg, Moscow, Russia: IEEE Computer Society; 2021. p. 2161-2165. doi: https://doi.org/10.1109/ElConRus51938.2021.9396510
17. Alam K.S., Shishir T.A., Azharul Hasan K.M. Efficient Partitioning Algorithm for Parallel Multidimensional Matrix Operations by Linearization. In: Senjyu T., Mahalle P.N., Perumal T., Joshi A. (eds.). Information and Communication Technology for Intelligent Systems. ICTIS 2020. Smart Innovation, Systems and Technologies. Vol. 195. Singapore: Springer; 2021. p. 141-149. doi: https://doi. org/10.1007/978-981-15-7078-0_13
18. Pushpa R. Suri, Sudesh Rani. A New Classification for Architecture of Parallel Databases. Information Technology Journal. 2008;7(7):983-991. doi: https://doi.org/10.3923/itj.2008.983.991
19. Chen Y., Li K., Yang W., Xiao G., Xie X., Li T. Performance-Aware Model for Sparse Matrix-Matrix Multiplication on the Sunway TaihuLight Supercomputer. IEEE Transactions on Parallel and Distributed Systems. 2019;30(4):923-938. doi: https://doi. org/10.1109/TPDS.2018.2871189
20. Sridhar R., Chandrasekaran M., Sriramya C., Page T. Optimization of heterogeneous Bin packing using adaptive genetic algorithm. IOP Conference Series: Materials Science and Engineering. 2017;183(1):012026. doi: https://doi.org/10.1088/1757-899X/183/1/012026
21. Syrotkina O., Aleksieiev M., Moroz B., Matsiuk S., Shevtsova O., Kozlovskyi A. Mathematical Methods for optimizing Big Data Processing. In: 2020 10th International Conference on Advanced Computer Information Technologies (ACIT). Deggendorf, Germany: IEEE Computer Society; 2020. p. 170-176. doi: https://doi.org/10.1109/ACIT49673.2020.9208940
22. Wajszczyk B., Gruszka I.M. Analysis of possibilities to increase the efficiency of the relative database management system using the methods of parallel processing. Proceedings SPIE. Radioelectronic Systems Conference. 2019;11442:1144215. doi: https://doi.org/10.1117/12.2565744
23. Zakharov V., Kirikova A., Munerman V., Samoilova T. Architecture of Software-Hardware Complex for Searching Images in Database. In: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). Saint Petersburg and Moscow, Russia: IEEE Computer Society; 2019. p. 1735-1739. doi: https://doi.org/10.1109/EIConRus.2019.8657241
24. Zaki M.J. Parthasarathy S., Ogihara M. Parallel Algorithms for Discovery of Association Rules. Data Mining and Knowledge Discovery. 1997;1:343-373. Available at: http://www.cs.rpi.edu/~zaki/PaperDir/DMKD97.pdf (accessed 23.06.2022).
25. Zobel J., Moffat A., Sacks-Davis R. An Efficient Indexing Technique for Full Text Databases. In: Proceedings of the 18th International Conference on Very Large Data Bases (VLDB'92). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1992. p. 352-362. Available at: https://www.vldb.org/conf/1992/P353.PDF (accessed 23.06.2022).
Опубликована
2022-10-24
Как цитировать
MIRONOV, Artem Igorevich; MUNERMAN, Victor Iosifovich. Создание частичного индексирования таблицы для оптимизации поисковых запросов. Современные информационные технологии и ИТ-образование, [S.l.], v. 18, n. 3, p. 558-565, oct. 2022. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/894>. Дата доступа: 24 feb. 2024 doi: https://doi.org/10.25559/SITITO.18.202203.558-565.
Раздел
Параллельное и распределенное программирование, грид-технологии

Наиболее читаемые статьи этого автора (авторов)