{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T02:29:35Z","timestamp":1790216975668,"version":"4.1.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T00:00:00Z","timestamp":1482105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003475","name":"Hasler Foundation","doi-asserted-by":"crossref","award":["#11072"],"award-info":[{"award-number":["#11072"]}],"id":[{"id":"10.13039\/501100003475","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Interact. Intell. Syst."],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>Recommender systems form the backbone of many interactive systems. They incorporate user feedback to personalize the user experience typically via personalized recommendation lists. As users interact with a system, an increasing amount of data about a user\u2019s preferences becomes available, which can be leveraged for improving the systems\u2019 performance. Incorporating these new data into the underlying recommendation model is, however, not always straightforward. Many models used by recommender systems are computationally expensive and, therefore, have to perform offline computations to compile the recommendation lists. For interactive applications, it is desirable to be able to update the computed values as soon as new user interaction data is available: updating recommendations in interactive time using new feedback data leads to better accuracy and increases the attraction of the system to the users. Additionally, there is a growing consensus that accuracy alone is not enough and user satisfaction is also dependent on diverse recommendations.<\/jats:p>\n          <jats:p>\n            In this work, we tackle this problem of updating personalized recommendation lists for interactive applications in order to provide both accurate and diverse recommendations. To that end, we explore algorithms that exploit random walks as a sampling technique to obtain diverse recommendations without compromising on efficiency and accuracy. Specifically, we present a novel graph vertex ranking recommendation algorithm called RP\n            <jats:sup>3<\/jats:sup>\n            <jats:sub>\u03b2<\/jats:sub>\n            that reranks items based on three-hop random walk transition probabilities. We show empirically that RP\n            <jats:sup>3<\/jats:sup>\n            <jats:sub>\u03b2<\/jats:sub>\n            provides accurate recommendations with high long-tail item frequency at the top of the recommendation list. We also present approximate versions of RP\n            <jats:sup>3<\/jats:sup>\n            <jats:sub>\u03b2<\/jats:sub>\n            and the two most accurate previously published vertex ranking algorithms based on random walk transition probabilities and show that these approximations converge with an increasing number of samples.\n          <\/jats:p>\n          <jats:p>To obtain interactively updatable recommendations, we additionally show how our algorithm can be extended for online updates at interactive speeds. The underlying random walk sampling technique makes it possible to perform the updates without having to recompute the values for the entire dataset.<\/jats:p>\n          <jats:p>\n            In an empirical evaluation with three real-world datasets, we show that RP\n            <jats:sup>3<\/jats:sup>\n            <jats:sub>\u03b2<\/jats:sub>\n            provides highly accurate and diverse recommendations that can easily be updated with newly gathered information at interactive speeds (\u226a 100\n            <jats:italic>ms<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/2955101","type":"journal-article","created":{"date-parts":[[2016,12,20]],"date-time":"2016-12-20T13:25:27Z","timestamp":1482240327000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Updatable, Accurate, Diverse, and Scalable Recommendations for Interactive Applications"],"prefix":"10.1145","volume":"7","author":[{"given":"Bibek","family":"Paudel","sequence":"first","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Christoffel","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Newell","sequence":"additional","affiliation":[{"name":"British Broadcasting Corporation, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abraham","family":"Bernstein","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,12,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 1st International Workshop on Novelty and Diversity in Recommender Systems (DiveRS\u201911)","author":"Adomavicius Gediminas","year":"2011","unstructured":"Gediminas Adomavicius and YoungOk Kwon . 2011 . Maximizing aggregate recommendation diversity: A graph-theoretic approach . In Proceedings of the 1st International Workshop on Novelty and Diversity in Recommender Systems (DiveRS\u201911) . Citeseer, 3--10. Gediminas Adomavicius and YoungOk Kwon. 2011. Maximizing aggregate recommendation diversity: A graph-theoretic approach. In Proceedings of the 1st International Workshop on Novelty and Diversity in Recommender Systems (DiveRS\u201911). Citeseer, 3--10."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.15"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312230"},{"key":"e_1_2_1_4_1","volume-title":"Reversible Markov chains and random walks on graphs. Unfinished Monograph","author":"Aldous David","unstructured":"David Aldous and Jim Fill . 2002. Reversible Markov chains and random walks on graphs. Unfinished Monograph . http:\/\/www.stat.berkeley.edu\/&sim;aldous\/RWG\/book.html. David Aldous and Jim Fill. 2002. Reversible Markov chains and random walks on graphs. Unfinished Monograph. http:\/\/www.stat.berkeley.edu\/&sim;aldous\/RWG\/book.html."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367618"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129116"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2nd International Workshop on Context-Aware Recommender Systems.","author":"Bogers Toine","year":"2010","unstructured":"Toine Bogers . 2010 . Movie recommendation using random walks over the contextual graph . In Proceedings of the 2nd International Workshop on Context-Aware Recommender Systems. Toine Bogers. 2010. Movie recommendation using random walks over the contextual graph. In Proceedings of the 2nd International Workshop on Context-Aware Recommender Systems."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.2"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers, 43--52","author":"Breese John S.","year":"1998","unstructured":"John S. Breese , David Heckerman , and Carl Kadie . 1998 . Empirical analysis of predictive algorithms for collaborative filtering . In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers, 43--52 . John S. Breese, David Heckerman, and Carl Kadie. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers, 43--52."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129090"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2792838.2800180"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2579244"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2042182.2042197"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1080.0974"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250939"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2005.9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043989"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/138859.138867"},{"key":"e_1_2_1_21_1","first-page":"24","article-title":"Profiting from the long tail","volume":"84","author":"Goldstein Daniel G.","year":"2006","unstructured":"Daniel G. Goldstein and Dominique C. Goldstein . 2006 . Profiting from the long tail . Harvard Business Review 84 , 6 (2006), 24 -- 28 . Daniel G. Goldstein and Dominique C. Goldstein. 2006. Profiting from the long tail. Harvard Business Review 84, 6 (2006), 24--28.","journal-title":"Harvard Business Review"},{"key":"e_1_2_1_22_1","first-page":"2766","article-title":"ItemRank: A random-walk based scoring algorithm for recommender engines","volume":"7","author":"Gori Marco","year":"2007","unstructured":"Marco Gori , Augusto Pucci , V. Roma , and I. Siena . 2007 . ItemRank: A random-walk based scoring algorithm for recommender engines . In IJCAI , Vol. 7. 2766 -- 2771 . Marco Gori, Augusto Pucci, V. Roma, and I. Siena. 2007. ItemRank: A random-walk based scoring algorithm for recommender engines. In IJCAI, Vol. 7. 2766--2771.","journal-title":"IJCAI"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/312624.312682"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/963770.963772"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/963770.963775"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557067"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/040619028"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398488"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1125451.1125659"},{"key":"e_1_2_1_36_1","volume-title":"Usability Engineering","author":"Nielsen Jakob","unstructured":"Jakob Nielsen . 1993. Usability Engineering . Morgan Kaufmann Publishers . Jakob Nielsen. 1993. Usability Engineering. Morgan Kaufmann Publishers."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_1_39_1","volume-title":"The Filter Bubble: What the Internet is Hiding From You","author":"Pariser Eli","unstructured":"Eli Pariser . 2011. The Filter Bubble: What the Internet is Hiding From You . Penguin . Eli Pariser. 2011. The Filter Bubble: What the Internet is Hiding From You. Penguin."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 452--461","author":"Rendle Steffen","year":"2009","unstructured":"Steffen Rendle , Christoph Freudenthaler , Zeno Gantner , and Lars Schmidt-Thieme . 2009 . BPR: Bayesian personalized ranking from implicit feedback . In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 452--461 . Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian personalized ranking from implicit feedback. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 452--461."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/192844.192905"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390267"},{"key":"e_1_2_1_43_1","first-page":"1","article-title":"Probabilistic matrix factorization","volume":"20","author":"Salakhutdinov Ruslan","year":"2011","unstructured":"Ruslan Salakhutdinov and Andriy Mnih . 2011 . Probabilistic matrix factorization . In NIPS , Vol. 20. 1 -- 8 . Ruslan Salakhutdinov and Andriy Mnih. 2011. Probabilistic matrix factorization. In NIPS, Vol. 20. 1--8.","journal-title":"NIPS"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390269"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372071"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940281.1940330"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-150176"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043955"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835896"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311916"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390465"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124300"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646025"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1000488107"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060754"}],"container-title":["ACM Transactions on Interactive Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2955101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:11Z","timestamp":1750221551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,19]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/2955101"],"URL":"https:\/\/doi.org\/10.1145\/2955101","relation":{},"ISSN":["2160-6455","2160-6463"],"issn-type":[{"value":"2160-6455","type":"print"},{"value":"2160-6463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,19]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}