METHOD FOR STORING DATA OF A RECOMMENDER SYSTEM BASED ON BINARY DECISION DIAGRAMS
DOI:
https://doi.org/10.26906/SUNZ.2020.2.085Keywords:
recommender systems, binary solution diagrams, linked lists, hash tables, computer simulationAbstract
The paper is devoted to researching of methods for storing data of recommender systems. Usage of binary decision diagrams for saving such data is proposed and studied. Due to the large size of recommender systems, there are significant limitations on RAM. The purpose of the work is to develop a method of storing data of a recommender system as binary decision diagrams and to compare it with storing methods based on other data structures. The data of a recommender system is stored as a graph with vertices representing users and items of the system, and the edges representing the actions users, similarity relations, relationships of recommendations, et cetera. To increase efficiency in the case of intensive graph editing, data storing based on “hot” (hash table) and “cold” (binary decision diagram) storages is proposed. A series of experiments was made to test the efficiency of the developed method of data storing, for this a software model of a simplified recommender system was developed and the work algorithm of such a system was described. In the numerical experiment the proposed method of storing data based on binary decision trees is compared with three others: based on bit maps, linked lists and hash tables. The advantages and disadvantages of implementing for each of these methods are considered. During the experiment, for various values of the number of agents, items, sessions and preferences, it were investigated the maximum and minimum values of the used RAM, along with time for generating of likes, sessions and recommendations. It has been found that in the case of binary decision diagrams, the amount of used RAM is lower than other methods but at lower speeds, the latter can be partially compensated by several applied optimizations. Due to the less usage of RAM, it is possible to store information about a larger amount of preferences, it may be useful in the cases of large size of the recommender system graph. The ability for binary decision diagrams of data search by partial keys additionally allows to store larger dataDownloads
References
“Recommender Systems Handbook” (2010) Editors F. Ricci, L. Rokach, B. Shapira, P. B. Kantor, New York, NY, USA: Springer-Verlag New York, Inc., 842 p.
Jones M. (2013) “Recommender systems, Part 1. Introduction to approaches and algorithms. Learn about the concepts that underlie web recommendation engines”, URL: https://www.ibm.com/developerworks/opensource/library/osrecommender1/index.html?s_tact=105agx99&s_cmp=cp
Фаулер М., Садаладж П. Дж. (2013) “NoSQL: новая методология разработки нереляционных баз данных”, Издательский дом «Вильямс», Москва, 192 с.
Meier A., Kaufmann M. (2019) “SQL & NoSQL Databases”, Springer Vieweg, Wiesbaden, P. 201-218. – URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.468.7089&rep=rep1&type=pdf
Cure O., Blin G. (2014) “RDF Database Systems: Triples Storage and SPARQL Query Processing”, Elsevier Science, 256 p.
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, P. 132-135.
Angles R. (2012) “A comparison of current graph database models”, IEEE 28th International Conference on Data Engineering Workshops, IEEE, 2012, P. 171-177.
Засядко Г.Е., Карпов А.В. (2017) “Проблемы разработки графовых баз данных”, // ИВД. No1 (44), URL: https://cyberleninka.ru/article/n/problemy-razrabotki-grafovyh-baz-dannyh
Мелков С., Мусатов Д., Савватеев А. (2013), “Моделирование социальных сетей”, URL: https://kpfu.ru/docs/F117464271/MMS_socnet_cities.pdf
Берновски М.М., Кузюрин Н.Н. (2012) “Случайные графы, модели и генераторы безмасштабных графов” // Труды ИСП РАН. URL: https://cyberleninka.ru/article/n/ sluchaynye-grafy-modeli-i-generatory-bezmasshtabnyh-grafov
Райгородский А.М. (2012) “Математические модели Интернета”, “Квант” No4, С. 12-16, URL: https://elementy.ru/nauchno-populyarnaya_biblioteka/431792
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), P. 80-84
Робинсон Я., Вебер Д., Эифрем Э. (2016) “Графовые базы данных: новые возможности для работы со связанными данными”, М.: ДМК Пресс, 256 с.
“Neo4j Documentation” (2020) URL: https://neo4j.com/docs
Храбров Д. (2006) “Способы хранения графов в памяти компьютера”, URL: https://dexp.in/russian/graph-storage/
Кнут Д.Э. (2013) “Искусство программирования, том 4А. Комбинаторные алгоритмы. Часть 1”, М.: "Вильямс", 960 с.
Minato S. (2001) “Zero-suppressed BDDs and their applications”, International Journal on Software Tools for Technology Transfer, No3.2 – pp. 156– 170.
Міхав В.В. (2019) “Програмне забезпечення для моделювання мереж репутації користувачів соціальних веб-ресурсів на основі бінарних діаграм рішень”, Системи управління, навігації та зв’язку, Т.5., No57, С. 78-83. – URL: http://journals.nupp.edu.ua/sunz/article/download/1720/140
