DOI: https://doi.org/10.32515/2664-262X.2021.4(35).8-16

Методи та структури даних для реалізації бази даних рекомендаційної системи соціальної мережі

В.В. Міхав, Є.В. Мелешко, С.В. Шимко

Об авторах

В.В. Міхав, асіпрант, Центральноукраїнський національний технічний уіверситет, м. Кропивницький, Україна, e-mail: mihaw.wolodymyr@gmail.com, ORCID ID: 0000-0003-4816-4680

Є.В. Мелешко, доцент, доктор технічних наук, Центральноукраїнський національний технічний університет, м. Кропивницький, Україна, e-mail: elismeleshko@gmail.com, ORCID ID: 0000-0001-8791-0063

С.В. Шимко, асіпрант , Центральноукраїнський національний технічний університет, м. Кропивницький, Україна, e-mail: shymko97@gmail.com, ORCID ID: 0000-0002-1132-484X

Анотація

Метою даної роботи є дослідження та програмна реалізація методів і структур даних для побудови бази даних рекомендаційної системи, щоб порівняти ефективність їх використання за затратами часу та пам’яті. Наявність великої кількості різних методів реалізації баз даних викликає необхідність порівняльного аналізу та вибору оптимального методу і структури даних для зберігання інформації у рекомендаційних системах. Було проведено дослідження різних структур даних, які можна використати для створення бази даних рекомендаційної системи, зокрема, досліджені зв’язний список, розгорнутий зв’язний список, хеш-таблиця, B-дерево, B+-дерево та бінарна діаграма рішень. Також було проведено серію експериментів на програмній імітаційній моделі рекомендаційної системи з різною кількістю агентів, предметів та сесій. Відповідно до результатів проведених експериментів, розгорнутий список показав найкращі показники швидкодії та використання пам’яті. Структура B+-дерево показала результати, близькі до хеш-таблиці. Час доступу до окремого елементу в обох випадках сталий, але B+-дерево має певні переваги – елементи зберігаються відсортованими, а при зміні розміру немає необхідності розширювати область пам’яті. Найгірші результати показала структура даних бінарна діаграма рішень як за затратами часу, так і за затратами пам’яті. Профілювання показало, що 75% часу роботи тесту варіанту з розгорнутим списком зайняло генерування випадкових даних для програмного імітаційного моделювання агентів та предметів рекомендаційної системи, тож, саме сховище даних має високі показники ефективності. Профілювання варіанту із інвертованим списком показало, що доступ до випадкових блоків займає більше часу через неможливість закешувати їх, тож, за умов реального навантаження час вставки нових даних буде більшим, а відносна ефективність застосування інвертованого списку зросте. Для найбільш ефективного використання пам’яті розмір блоку зв’язного списку має бути адаптований таким чином, щоб блоки були максимально заповнені. Блоки малого розміру зменшують втрати пам’яті, але збільшують час обходу всіх елементів списку та збільшують накладні витрати пам’яті.

Ключові слова

рекомендаційні системи, бази даних, структури даних, програмна імітаційна модель

Повний текст:

PDF

Посилання

1. Editors Ricci, F., Rokach, L., Shapira, B. & Kantor, P.B. (2010). Recommender Systems Handbook. New York, NY, USA: Springer-Verlag New York, Inc [in English].

2. Valois, B.Jr.C. & Oliveira, M.A. (2011). Recommender systems in social networks. JISTEM J.Inf.Syst. Technol. Manag., Vol.8, No.3. 681-716. Retrieved from https://www.scielo.br/scielo.php?script=sci_arttext&pid=S1807-17752011000300009 [in English].

3. Fauler, M., Sadaladzh, P. Dzh. (2013). NoSQL: Novaja metodologija razrabotki nereljacionnyh baz dannyh [NoSQL: A new methodology for the development of non-relational databases]. Williams Publishing House, Moscow. [in Russian].

4. Meier, A. & Kaufmann, M. (2019). SQL & NoSQL Databases. Springer Vieweg, Wiesbaden. 201-218. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.468.7089&rep=rep1&type=pdf [in English].

5. Cure, O., Blin, G. (2014). RDF Database Systems: Triples Storage and SPARQL Query Processing. Elsevier Science [in English].

6. Yi, N., Li, C., Feng, X. & Shi, M. (2017). Design and implementation of movie recommender system based on graph database. 14th Web Information Systems and Applications Conference (WISA), IEEE. 132-135[in English].

7. Angles, R. (2012). A comparison of current graph database models. IEEE 28th International Conference on Data Engineering Workshops, IEEE, 171-177 [in English].

8. Zasjadko, G.E. & Karpov, A.V. (2017). Problemy razrabotki grafovyh baz dannyh [Problems in the development of graph databases]. Inzhenernyj vestnik Dona – Engineering journal of Don. №1 (44). Retrieved from https://cyberleninka.ru/article/n/problemy-razrabotki-grafovyh-baz-dannyh [in Russian].

9. Melkov, S., Musatov, D. & Savvateev, A. (2013) Modelirovanie social'nyh setej [Social networks' modeling]. Retrieved from https://kpfu.ru/docs/F117464271/MMS_socnet_cities.pdf [in Russian].

10. Bernovski, M.M. & Kuzjurin, N.N. (2012). Sluchajnye grafy, modeli i generatory bezmasshtabnyh grafov [Random Graphs, Models, and Scaleless Graph Generators]. Trudy ISP RAN – Proceedings of the Institute for System Programming of the Russian Academy of Sciences. 419-432. Retrieved from https://cyberleninka.ru/article/n/sluchaynye-grafy-modeli-i-generatory-bezmasshtabnyh-grafov [in Russian].

11. Rajgorodskij, A.M. (2012). Matematicheskie modeli Interneta [Mathematical models of the Internet]. “Kvant” – “Quantum”, No 4. 12-16. Retrieved from https://elementy.ru/nauchno-populyarnaya_biblioteka/431792 [in Russian].

12. Meleshko, Ye. (2019). Computer model of virtual social network with recommendation system. Scientific journal Innovative Technologies and Scientific Solutions for Industries, Kharkiv: NURE, Issue 2(8). 80-84 [in English].

13. Robinson, Ja., Veber, D., Jeifrem, Je. (2016). Grafovye bazy dannyh: novye vozmozhnosti dlja raboty so svjazannymi dannymi [Graph databases: new possibilities for working with related data]. Мoskow: DMK Press [in Russian].

14. Neo4j Documentation (2020). neo4j.com. Retrieved from https://neo4j.com/docs [in English].

15. Aho, A., Hopcroft, J., Ullman, J. (2000). Struktury dannyh i algoritmy [Data Structures and Algorithms]. Williams Publishing House, Moscow. [in Russian].

16. Minato, S. (2001). Zero-suppressed BDDs and their applications. International Journal on Software Tools for Technology Transfer, №3.2. 156-170 [in English].

17. Knuth, D.E. (2013). Iskusstvo programmirovanija [The art of programming], Tom 4A. Kombinatornye algoritmy. Chast' 1 [Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1]. Williams Publishing House, Moscow. [in Russian].

Пристатейна бібліографія ГОСТ

  • Editors Ricci F., Rokach L., Shapira B., Kantor P. B. Recommender Systems Handbook. New York, NY, USA: Springer-Verlag New York, Inc., 2010. 842 p.
  • Valois B.Jr.C., Oliveira M.A. Recommender systems in social networks. JISTEM J.Inf.Syst. Technol. Manag. 2011. Vol.8 No.3. P. 681-716. URL: https://www.scielo.br/scielo.php?script=sci_arttext&pid=S1807-17752011000300009 (Last accessed: 02.04.2021)
  • Фаулер М., Садаладж П. Дж. NoSQL: Новая методология разработки нереляционных баз данных. М.: Издательский дом «Вильямс». 2013. 192 с.
  • Meier A., Kaufmann M. SQL & NoSQL Databases. Springer Vieweg, Wiesbaden. 2019. P. 201-218. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.468.7089&rep=rep1&type=pdf (Last accessed: 02.04.2021)
  • Cure O., Blin G. RDF Database Systems: Triples Storage and SPARQL Query Processing. Elsevier Science. 2014. 256 p.
  • Yi N., Li C., Feng X., Shi M. Design and implementation of movie recommender system based on graph database. 14th Web Information Systems and Applications Conference (WISA), IEEE. 2017. P. 132-135.
  • Angles R. A comparison of current graph database models. IEEE 28th International Conference on Data Engineering Workshops, IEEE. 2012. P. 171-177.
  • Засядко Г.Е., Карпов А.В. Проблемы разработки графовых баз данных. Инженерный вестник Дона. 2017. №1(44). URL: https://cyberleninka.ru/article/n/problemy-razrabotki-grafovyh-baz-dannyh (дата обращения: 02.04.2021)
  • Мелков С., Мусатов Д., Савватеев А. Моделирование социальных сетей. 2013. URL: https://kpfu.ru/docs/F117464271/MMS_socnet_cities.pdf (дата обращения: 02.04.2021)
  • Берновски М.М., Кузюрин Н.Н. Случайные графы, модели и генераторы безмасштабных графов. Труды ИСП РАН. 2012. URL: https://cyberleninka.ru/article/n/sluchaynye-grafy-modeli-i-generatory-bezmasshtabnyh-grafov (дата обращения: 02.04.2021)
  • Райгородский А.М. Математические модели Интернета. “Квант”. 2012. №4. С. 12-16. URL: https://elementy.ru/nauchno-populyarnaya_biblioteka/431792 (дата обращения: 02.04.2021)
  • Meleshko Ye. Computer model of virtual social network with recommendation system. Scientific journal Innovative Technologies and Scientific Solutions for Industries, Kharkiv, NURE. 2019. Issue 2(8). P. 80-84.
  • Робинсон Я., Вебер Д., Эифрем Э. Графовые базы данных: новые возможности для работы со связанными данными. М.: ДМК Пресс. 2016. 256 с.
  • Neo4j Documentation. 2020. URL: https://neo4j.com/docs (Last accessed: 02.04.2021)
  • Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2000. 384 с.
  • Minato S. Zero-suppressed BDDs and their applications. International Journal on Software Tools for Technology Transfer. 2001. №3.2. pp. 156-170.
  • Кнут Д.Э. Искусство программирования, Том 4А. Комбинаторные алгоритмы. Часть 1. М.: Вильямс. 2013. 960 с.

    • Copyright (c) 2021 В.В. Міхав, Є.В. Мелешко, С.В. Шимко