Supporting hard queries over probabilistic preferences

Haoyue Ping, Julia Stoyanovich, Benny Kimelfeld

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים

תקציר

Preference analysis is widely applied in various domains such as social choice and e-commerce. A recently proposed frame- work augments the relational database with a preference re- lation that represents uncertain preferences in the form of statistical ranking models, and provides methods to evaluate Conjunctive Queries (CQs) that express preferences among item attributes. In this paper, we explore the evaluation of queries that are more general and harder to compute. The main focus of this paper is on a class of CQs that cannot be evaluated by previous work. These queries are provably hard since relate variables that represent items be- ing compared. To overcome this hardness, we instantiate these variables with their domain values, rewrite hard CQs as unions of such instantiated queries, and develop several exact and approximate solvers to evaluate these unions of queries. We demonstrate that exact solvers that target specific common kinds of queries are far more efficient than gen- eral solvers. Further, we demonstrate that sophisticated ap- proximate solvers making use of importance sampling can be orders of magnitude more efficient than exact solvers, while showing good accuracy. In addition to supporting provably hard CQs, we also present methods to evaluate an important family of count queries, and of top-k queries.

שפה מקוריתאנגלית
עמודים (מ-עד)1134-1146
מספר עמודים13
כתב עתProceedings of the VLDB Endowment
כרך13
מספר גיליון7
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2020
אירוע46th International Conference on Very Large Data Bases, VLDB 2020 - Virtual, יפן
משך הזמן: 31 אוג׳ 20204 ספט׳ 2020

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1701???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Supporting hard queries over probabilistic preferences'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי