Composite recommendations: from items to packages

Abstract

Classical recommender systems provide users with a list of recommendations where each recommendation consists of a single item, e.g., a book or DVD. However, several applications can benefit from a system capable of recommending packages of items, in the form of sets. Sample applications include travel planning with a limited budget (price or time) and twitter users wanting to select worthwhile tweeters to follow, given that they can deal with only a bounded number of tweets. In these contexts, there is a need for a system that can recommend the top-k packages for the user to choose from.

Motivated by these applications, we consider composite recommendations, where each recommendation comprises a set of items. Each item has both a value (rating) and a cost associated with it, and the user specifies a maximum total cost (budget) for any recommended set of items. Our composite recommender system has access to one or more component recommender systems focusing on different domains, as well as to information sources which can provide the cost associated with each item. Because the problem of decidingwhether there is a recommendation (package)whose cost is under a given budget and whose value exceeds some threshold is NP-complete, we devise several approximation algorithms for generating the top-k packages as recommendations. We analyze the efficiency as well as approximation quality of these algorithms. Finally, using two real and two synthetic datasets, we subject our algorithms to thorough experimentation and empirical analysis. Our findings attest to the efficiency and quality of our approximation algorithms for the top-k packages compared to exact algorithms.

Keywords

recommendation algorithms / optimization / top-k query processing

References

[1] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 734-749

[2] Weng J, Lim E, Jiang J, He Q. Twitterrank: finding topic-sensitive influential twitterers. In: Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. 2010, 261-270

[3] Kellerer H, Pferschy U, Pisinger D. Knapsack Problems. Berlin: Springer, 2004

[4] Brodsky A, Morgan Henshaw S, Whittle J. CARD: a decisionguidance framework and application for recommending composite alternatives. In: Proceedings of the 2008 ACM Conference on Recommender Systems. 2008, 171-178

[5] Koutrika G, Bercovitz B, Garcia-Molina H. FlexRecs: expressing and combining flexible recommendations. In: Proceedings of the 35th SIGMOD International Conference on Management of Data. 2009, 745-758

[6] Angel A, Chaudhuri S, Das G, Koudas N. Ranking objects based on relationships and fixed associations. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. 2009, 910-921

[7] Parameswaran A, Garcia-Molina H. Recommendations with prerequisites. In: Proceedings of the 3rd ACM Conference on Recommender Systems. 2009, 353-356

[8] Parameswaran A, Garcia-Molina H, Ullman J. Evaluating, combining and generalizing recommendations with prerequisites. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010, 919-928

[9] Parameswaran A, Venetis P, Garcia-Molina H. Recommendation systems with complex constraints: A course recommendation perspective. ACM Transactions on Information Systems, 2011, 29(4): 1-33

[10] Lappas T, Liu K, Terzi E. Finding a team of experts in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009, 467-476

[11] Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 2003, 66(4): 614-656

[12] Xie M, Lakshmanan L, Wood P. Breaking out of the box of recommendations: from items to packages. In: Proceedings of the 4th ACM Conference on Recommender Systems. 2010, 151-158

[13] De Choudhury M, Feldman M, Amer-Yahia S, Golbandi N, Lempel R, Yu C. Automatic construction of travel itineraries using social breadcrumbs. In: Proceedings of the 21st ACM Conference on Hypertext and Hypermedia. 2010, 35-44

[14] Finger J, Polyzotis N. Robust and efficient algorithms for rank join evaluation. In: Proceedings of the 35th SIGMOD International Conference on Management of Data. 2009, 415-428

[15] Tran Q T, Chan C Y, Wang G. Evaluation of set-based queries with aggregation constraints. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. 2011, 1495-1504

[16] Roy S B, Amer-Yahia S, Chawla A, Das G, Yu C. Constructing and exploring composite items. In: Proceedings of the 36th SIGMOD International Conference on Management of Data. 2010, 843-854

[17] Papadimitriou C H. Computational Complexity. Chichester: Wiley, 1994

[18] Ibarra O, Kim C. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 1975, 22(4): 463-468

[19] Vazirani V. Approximation Algorithms. Berlin: Springer, 1999

[20] Marchetti-Spaccamela A, Vercellis C. Stochastic on-line knapsack problems. Mathematical Programming, 1995, 68(1): 73-104

[21] Kimelfeld B, Sagiv Y.Finding and approximating top-k answers in keyword proximity search. In: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2006, 173-182

[22] Lawler E. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 1972, 401-405

[23] Jävelin K, Kekäläinen J. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems, 2002, 20(4): 422-446

[24] Xie M, Lakshmanan L, Wood P. Efficient rank join with aggregation constraints. Proceedings of the VLDB Endowment, 2011, 4(11): 1201-1212

[25] Xie M, Lakshmanan L, Wood P. Comprec-trip: a composite recommendation system for travel planning. In: Proceedings of the 27th International Conference on Data Engineering. 2011, 1352-1355

[26] Chekuri C, Pal M. A recursive greedy algorithm for walks in directed graphs. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. 2005, 245-253

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg