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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2020
الحدث46th International Conference on Very Large Data Bases, VLDB 2020 - Virtual, اليابان
المدة: ٣١ أغسطس ٢٠٢٠٤ سبتمبر ٢٠٢٠

All Science Journal Classification (ASJC) codes

  • !!Computer Science (miscellaneous)
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Supporting hard queries over probabilistic preferences'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا