Evaluating, combining and generalizing recommendations with prerequisites

Aditya G. Parameswaran; Hector Garcia-Molina; Jeffrey D. Ullman

doi:10.1145/1871437.1871555

Evaluating, combining and generalizing recommendations with prerequisites

Aditya G. Parameswaran, Hector Garcia-Molina, Jeffrey D. Ullman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, 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.

Original language	English (US)
Title of host publication	CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops
Pages	919-928
Number of pages	10
DOIs	https://doi.org/10.1145/1871437.1871555
State	Published - 2010
Externally published	Yes
Event	19th International Conference on Information and Knowledge Management and Co-located Workshops, CIKM'10 - Toronto, ON, Canada Duration: Oct 26 2010 → Oct 30 2010

Publication series

Name	International Conference on Information and Knowledge Management, Proceedings

Other

Other	19th International Conference on Information and Knowledge Management and Co-located Workshops, CIKM'10
Country/Territory	Canada
City	Toronto, ON
Period	10/26/10 → 10/30/10

Keywords

Graph theory
Prerequisites
Recommendation algorithms

ASJC Scopus subject areas

Decision Sciences(all)
Business, Management and Accounting(all)

Online availability

10.1145/1871437.1871555

Library availability

Discover UIUC Full Text

Cite this

Parameswaran, A. G., Garcia-Molina, H., & Ullman, J. D. (2010). Evaluating, combining and generalizing recommendations with prerequisites. In CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops (pp. 919-928). (International Conference on Information and Knowledge Management, Proceedings). https://doi.org/10.1145/1871437.1871555

Evaluating, combining and generalizing recommendations with prerequisites. / Parameswaran, Aditya G.; Garcia-Molina, Hector; Ullman, Jeffrey D.

CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops. 2010. p. 919-928 (International Conference on Information and Knowledge Management, Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Parameswaran, AG, Garcia-Molina, H & Ullman, JD 2010, Evaluating, combining and generalizing recommendations with prerequisites. in CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops. International Conference on Information and Knowledge Management, Proceedings, pp. 919-928, 19th International Conference on Information and Knowledge Management and Co-located Workshops, CIKM'10, Toronto, ON, Canada, 10/26/10. https://doi.org/10.1145/1871437.1871555

Parameswaran AG, Garcia-Molina H, Ullman JD. Evaluating, combining and generalizing recommendations with prerequisites. In CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops. 2010. p. 919-928. (International Conference on Information and Knowledge Management, Proceedings). doi: 10.1145/1871437.1871555

@inproceedings{f14aae5610184326a35db80b11369628,

title = "Evaluating, combining and generalizing recommendations with prerequisites",

abstract = "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 general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, 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.",

keywords = "Graph theory, Prerequisites, Recommendation algorithms",

author = "Parameswaran, {Aditya G.} and Hector Garcia-Molina and Ullman, {Jeffrey D.}",

year = "2010",

doi = "10.1145/1871437.1871555",

language = "English (US)",

isbn = "9781450300995",

series = "International Conference on Information and Knowledge Management, Proceedings",

pages = "919--928",

booktitle = "CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops",

note = "19th International Conference on Information and Knowledge Management and Co-located Workshops, CIKM'10 ; Conference date: 26-10-2010 Through 30-10-2010",

}

TY - GEN

T1 - Evaluating, combining and generalizing recommendations with prerequisites

AU - Parameswaran, Aditya G.

AU - Garcia-Molina, Hector

AU - Ullman, Jeffrey D.

PY - 2010

Y1 - 2010

N2 - 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 general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, 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.

AB - 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 general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, 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.

KW - Graph theory

KW - Prerequisites

KW - Recommendation algorithms

UR - http://www.scopus.com/inward/record.url?scp=78651276678&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78651276678&partnerID=8YFLogxK

U2 - 10.1145/1871437.1871555

DO - 10.1145/1871437.1871555

M3 - Conference contribution

AN - SCOPUS:78651276678

SN - 9781450300995

T3 - International Conference on Information and Knowledge Management, Proceedings

SP - 919

EP - 928

BT - CIKM'10 - Proceedings of the 19th International Conference on Information and Knowledge Management and Co-located Workshops

T2 - 19th International Conference on Information and Knowledge Management and Co-located Workshops, CIKM'10

Y2 - 26 October 2010 through 30 October 2010

ER -

Evaluating, combining and generalizing recommendations with prerequisites

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this