The goal of this work is to research and program implementation of methods and data structures for building a database of a recommendation system in order to compare the efficiency of their use in terms of time and memory costs. The presence of a large number of different methods of database implementation necessitates a comparative analysis and selection of the optimal method and data structure for storing information in recommendation systems. A research on various data structures that can be used to create a recommendation system database, in particular, the linked list, unrolled linked list, hash table, B-tree, B+-tree, and binary decision diagram were examined was conducted. A series of experiments on a software simulation model of a recommendation system with a different number of agents, items and sessions was also carried out. The following research results were obtained. According to the results of the experiments, the unrolled linked list showed the best time and memory effectiveness. The B+-tree structure showed results close to a hash table. The access time to an individual element is stable in both cases, but the B+-tree has certain advantages – the elements are kept sorted, and when resizing, there is no need to expand the memory area. The worst results were shown by the data structure of the binary decision diagram, both in terms of time consumption and memory consumption. Profiling showed that 75% of the test run time for the option with an unrolled list was taken by generating random data for software simulation of agents and items of the recommendation system, therefore, the data warehouse itself has high performance indicators. Profiling of the variant with an inverted list showed that access to random blocks takes longer due to the inability to cache them, therefore, under real load conditions, the time for inserting new data will be longer, and the relative efficiency of using the inverted list will increase. For the most efficient use of memory, the block size of the linked list should be adapted so that the blocks are as full as possible. Small blocks reduce memory waste, but increase the time to traverse all the elements of the list and increase memory overhead.

recommendation systems, databases, data structures, computer simulation model

Full Text:

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].

Copyright (c) 2021 Volodymyr Mikhav, Yelyzaveta Meleshko, Serhii Shymko