research-article

On the complexity of package recommendation problems

Authors:

Floris GeertsAuthors Info & Claims

PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems

Pages 261 - 272

https://doi.org/10.1145/2213556.2213592

Published: 21 May 2012 Publication History

Abstract

Recommendation systems aim to recommend items that are likely to be of interest to users. This paper investigates several issues fundamental to such systems.

We model recommendation systems for packages of items. We use queries to specify multi-criteria for item selections and express compatibility constraints on items in a package, and use functions to compute the cost and usefulness of items to a user.

We study recommendations of points of interest, to suggest top-k packages. We also investigate recommendations of top-k items, as a special case. In addition, when sensible suggestions cannot be found, we propose query relaxation recommendations to help users revise their selection criteria, or adjustment recommendations to guide vendors to modify their item collections.

We identify several problems, to decide whether a set of packages makes a top-k recommendation, whether a rating bound is maximum for selecting top-k packages, whether we can relax the selection query to find packages that users want, and whether we can update a bounded number of items such that the users' requirements can be satisfied. We also study function problems for computing top-k packages, and counting problems to find how many packages meet the user's criteria.

We establish the upper and lower bounds of these problems, all matching, for combined and data complexity. These results reveal the impact of variable sizes of packages, the presence of compatibility constraints, as well as a variety of query languages for specifying selection criteria and compatibility constraints, on the analyses of these problems.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[2]

G. Adomavicius and A. Tuzhilin. Multidimensional recommender systems: A data warehousing approach. In WELCOM, 2001.

Digital Library

[3]

G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. TKDE, 17(6):734--749, 2005.

Digital Library

[4]

S. Amer-Yahia. Recommendation projects at Yahoo! IEEE Data Eng. Bull., 34(2):69--77, 2011.

[5]

S. Amer-Yahia, S. B. Roy, A. Chawla, G. Das, and C. Yu. Group recommendation: Semantics and efficiency. PVLDB, 2(1):754--765, 2009.

Digital Library

[6]

A. Angel, S. Chaudhuri, G. Das, and N. Koudas. Ranking objects based on relationships and fixed associations. In EDBT, 2009.

Digital Library

[7]

A. Brodsky, S. Henshaw, and J. Whittle. CARD: A decision-guidance framework and application for recommending composite alternatives. In RecSys, 2008.

Digital Library

[8]

S. Chaudhuri. Generalization and a framework for query modification. In ICDE, 1990.

Digital Library

[9]

S. Chaudhuri and M. Y. Vardi. On the equivalence of recursive and nonrecursive Datalog programs. JCSS, 54(1):61--78, 1997.

Digital Library

[10]

S. Cohen and Y. Sagiv. An incremental algorithm for computing ranked full disjunctions. JCSS, 73(4):648--668, 2007.

Digital Library

[11]

A. Durand, M. Hermann, and P. G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. TCS, 340(3):496--513, 2005.

Digital Library

[12]

R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. JCSS, 66(4):614--656, 2003.

Digital Library

[13]

T. Gaasterland and J. Lobo. Qualifying answers according to user needs and preferences. Fundam. Inform., 32(2):121--137, 1997.

Digital Library

[14]

K. Golenberg, B. Kimelfeld, and Y. Sagiv. Optimizing and parallelizing ranked enumeration. PVLDB, 4(11):1028--1039, 2011.

Digital Library

[15]

L. A. Hemaspaandra and H. Vollmer. The satanic notations: counting classes beyond #P and other definitional adventures. SIGACT News, 26(1):2--13, 1995.

Digital Library

[16]

I. F. Ilyas, G. Beskales, and M. A. Soliman. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv., 40(4):11:1--11:58, 2008.

Digital Library

[17]

A. Kadlag, A. V. Wanjari, J. Freire, and J. R. Haritsa. Supporting exploratory queries in databases. In DASFAA, 2004.

[18]

N. Koudas, C. Li, A. K. H. Tung, and R. Vernica. Relaxing join and selection queries. In VLDB, 2006.

Digital Library

[19]

G. Koutrika, B. Bercovitz, and H. Garcia-Molina. FlexRecs: expressing and combining flexible recommendations. In SIGMOD, 2009.

Digital Library

[20]

M. W. Krentel. Generalizations of Opt P to the polynomial hierarchy. TCS, 97(2):183--198, 1992.

Digital Library

[21]

R. E. Ladner. Polynomial space counting problems. SIAM J. Comput., 18(6):1087--1097, 1989.

Digital Library

[22]

T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in social networks. In KDD, 2009.

Digital Library

[23]

C. Li, M. A. Soliman, K. C.-C. Chang, and I. F. Ilyas. RankSQL: supporting ranking queries in relational database management systems. In VLDB, 2005.

Digital Library

[24]

A. Natsev, Y.-C. Chang, J. R. Smith, C.-S. Li, and J. S. Vitter. Supporting incremental join queries on ranked inputs. In VLDB, 2001.

Digital Library

[25]

C. H. Papadimitriou. Computational Complexity. AW, 1994.

[26]

A. G. Parameswaran, H. Garcia-Molina, and J. D. Ullman. Evaluating, combining and generalizing recommendations with prerequisites. In CIKM, 2010.

Digital Library

[27]

A. G. Parameswaran, P. Venetis, and H. Garcia-Molina. Recommendation systems with complex constraints: A course recommendation perspective. TOIS, 29(4), 2011.

Digital Library

[28]

K. Schnaitter and N. Polyzotis. Evaluating rank joins with optimal cost. In PODS, 2008.

Digital Library

[29]

K. Stefanidis, G. Koutrika, and E. Pitoura. A survey on representation, composition and application of preferences in database systems. TODS, 36(3), 2011.

Digital Library

[30]

L. J. Stockmeyer. The polynomial-time hierarchy. TCS, 3(1):1--22, 1976.

[31]

L. Valiant. The complexity of computing the permanent. TCS, 8(2):189--201, 1979.

[32]

M. Y. Vardi. The complexity of relational query languages. In STOC, 1982.

Digital Library

[33]

M. Wooldridge and P. E. Dunne. On the computational complexity of qualitative coalitional games. Artif. Intell., 158(1):27--73, 2004.

Digital Library

[34]

M. Xie, L. V. S. Lakshmanan, and P. T. Wood. Breaking out of the box of recommendations: from items to packages. In RecSys, 2010.

Digital Library

Cited By

Sato RSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Enumerating Fair Packages for Group RecommendationsProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498432(870-878)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498432
Li MBao XChang LXu ZLi L(2020)A Survey of Researches on Personalized Bundle Recommendation TechniquesMachine Learning for Cyber Security10.1007/978-3-030-62460-6_26(290-304)Online publication date: 8-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-62460-6_26
Brucato MAbouzied AMeliou A(2019)Scalable computation of high-order optimization queriesCommunications of the ACM10.1145/329988162:2(108-116)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3299881
Show More Cited By

Index Terms

On the complexity of package recommendation problems
1. Information systems
  1. World Wide Web
    1. Web applications
    2. Web services
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On recommendation problems beyond points of interest

Recommendation systems aim to recommend items or packages of items that are likely to be of interest to users. Previous work on recommendation systems has mostly focused on recommending points of interest (POI), to identify and suggest top-k items or ...
On the Complexity of Package Recommendation Problems

Recommendation systems aim to recommend items that are likely to be of interest to users. This paper investigates several issues fundamental to such systems: (1) We model recommendation systems for packages (sets) of items. We use queries to specify ...
Improving package recommendations through query relaxation
Data4U '14: Proceedings of the First International Workshop on Bringing the Value of "Big Data" to Users (Data4U 2014)

Recommendation systems aim to identify items that are likely to be of interest to users. In many cases, users are interested in package recommendations as collections of items. For example, a dietitian may wish to derive a dietary plan as a collection ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems

May 2012

332 pages

ISBN:9781450312486

DOI:10.1145/2213556

Editor:
Markus Krötzsch
University of Oxford, UK
,
General Chair:
Maurizio Lenzerini
University of Rome La Sapienza, Italy
,
Program Chair:
Michael Benedikt
University of Oxford, UK

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '12

Sponsor:

SIGMOD

SIGMOD/PODS '12: International Conference on Management of Data

May 21 - 23, 2012

Arizona, Scottsdale, USA

Acceptance Rates

PODS '12 Paper Acceptance Rate 26 of 101 submissions, 26%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
371
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sato RSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Enumerating Fair Packages for Group RecommendationsProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498432(870-878)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498432
Li MBao XChang LXu ZLi L(2020)A Survey of Researches on Personalized Bundle Recommendation TechniquesMachine Learning for Cyber Security10.1007/978-3-030-62460-6_26(290-304)Online publication date: 8-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-62460-6_26
Brucato MAbouzied AMeliou A(2019)Scalable computation of high-order optimization queriesCommunications of the ACM10.1145/329988162:2(108-116)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3299881
Liu YLi J(2019)Drawing CoCo Core-Sets from Incomplete Relational DataWeb and Big Data10.1007/978-3-030-26072-9_5(61-76)Online publication date: 18-Jul-2019
https://doi.org/10.1007/978-3-030-26072-9_5
Brucato MAbouzied AMeliou A(2018)Package queriesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-017-0483-427:5(693-718)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s00778-017-0483-4
Brucato MAbouzied AMeliou A(2017)A Scalable Execution Engine for Package QueriesACM SIGMOD Record10.1145/3093754.309376146:1(24-31)Online publication date: 12-May-2017
https://dl.acm.org/doi/10.1145/3093754.3093761
Brucato MBeltran JAbouzied AMeliou A(2016)Scalable package queries in relational database systemsProceedings of the VLDB Endowment10.14778/2904483.29044899:7(576-587)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.14778/2904483.2904489
Mengash HBrodsky A(2016)Tailoring Group Package Recommendations to Large Heterogeneous Groups Based on Multi-criteria OptimizationProceedings of the 2016 49th Hawaii International Conference on System Sciences (HICSS)10.1109/HICSS.2016.194(1537-1546)Online publication date: 5-Jan-2016
https://dl.acm.org/doi/10.1109/HICSS.2016.194
Bordino ILalmas MMejova YVan Laere O(2016)Beyond entities: promoting explorative search with bundlesInformation Retrieval10.1007/s10791-016-9283-519:5(447-486)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s10791-016-9283-5
Deng TFan WGeerts F(2015)On recommendation problems beyond points of interestInformation Systems10.1016/j.is.2014.08.00248:C(64-88)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.is.2014.08.002
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents