Supporting hard queries over probabilistic preferences

Haoyue Ping, Julia Stoyanovich, Benny Kimelfeld

    Research output: Contribution to journalConference articlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)1134-1146
    Number of pages13
    JournalProceedings of the VLDB Endowment
    Issue number7
    StatePublished - 2020
    Event46th International Conference on Very Large Data Bases, VLDB 2020 - Virtual, Japan
    Duration: Aug 31 2020Sep 4 2020

    ASJC Scopus subject areas

    • Computer Science (miscellaneous)
    • General Computer Science


    Dive into the research topics of 'Supporting hard queries over probabilistic preferences'. Together they form a unique fingerprint.

    Cite this