Stanford InfoLab Publication Server

Evaluating, Combining and Generalizing Recommendations with Prerequisites

Parameswaran, Aditya and Garcia-Molina, Hector and Ullman, Jeffrey D. (2010) Evaluating, Combining and Generalizing Recommendations with Prerequisites. In: 19th International Conference on Information and Knowledge Management (CIKM 2010), October 26-30, 2010, Toronto, Canada.




We consider the problem of recommending the best set of k items when there is an inherent ordering between items, expressed as a set of prerequisites (e.g., the movie `Godfather I' is a prerequisite of `Godfather II'). Since this problem is NP-hard, we develop 3 approximate algorithms to solve this problem. We derive worst-case bounds for these algorithms for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs), and experimentally evaluate these algorithms on synthetic data. We also develop an algorithm to combine solutions in order to generate even better solutions, and compare the performance of this algorithm with the other three.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:recommendation algorithms, prerequisites, constraints, theory, algorithms
ID Code:939
Deposited By:Aditya Parameswaran
Deposited On:13 Aug 2009 11:11
Last Modified:01 Jul 2011 14:53

Download statistics

Repository Staff Only: item control page