A Query Engine for Probabilistic Preferences
A Query Engine for Probabilistic Preferences
复制标题
概率偏好的查询引擎
DOI：
10.1145/3183713.3196923
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Stoyanovich, Julia
中科院分区：
文献类型：
--
作者：
Cohen, Uzi;Kenig, Batya;Ping, Haoyue;Kimelfeld, Benny;Stoyanovich, Julia
具有不确定偏好的模型，如毛坯模型，由于其应用领域过多而被广泛研究。在最近的一项工作中，提出了一个概念和理论框架，用于在关系数据库中支持作为一等公民的不确定偏好。所得到的数据库是概率的，因此，查询评估需要推断查询答案的边际概率。在本文中，我们着手于这一框架的实际实现的挑战。我们首先描述一个查询引擎的实现，该引擎支持在查询关系数据的同时查询概率偏好。我们的系统以重复插入模型(RIM)的一般形式容纳了偏好分布，该模型推广了Mlowers和其他模型。然后，我们设计了一种新的RIM上的合取查询推理算法，并证明了该算法在渐近执行代价和经验执行代价方面都明显优于现有技术。我们还开发了基于在工作负载中的不同推理任务之间分担计算的性能优化。最后，我们进行了广泛的实验评估，并证明了与使用黑盒推理求解器的独立实现相比，具有内置概率推理的查询引擎可以实现明显的性能优势。
Models of uncertain preferences, such as Mallows, have been extensively studied due to their plethora of application domains. In a recent work, a conceptual and theoretical framework has been proposed for supporting uncertain preferences as first-class citizens in a relational database. The resulting database is probabilistic, and, consequently, query evaluation entails inference of marginal probabilities of query answers. In this paper, we embark on the challenge of a practical realization of this framework. We first describe an implementation of a query engine that supports querying probabilistic preferences alongside relational data. Our system accommodates preference distributions in the general form of the Repeated Insertion Model (RIM), which generalizes Mallows and other models. We then devise a novel inference algorithm for conjunctive queries over RIM, and show that it significantly outperforms the state of the art in terms of both asymptotic and empirical execution cost. We also develop performance optimizations that are based on sharing computation among different inference tasks in the workload. Finally, we conduct an extensive experimental evaluation and demonstrate that clear performance benefits can be realized by a query engine with built-in probabilistic inference, as compared to a stand alone implementation with a black-box inference solver.
登录
查看更多内容
影响因子：
7.5
作者：
Lilyana Mihalkova;L. Getoor
通讯作者：
Lilyana Mihalkova;L. Getoor
影响因子：
2.7
作者：
MALLOWS, CL
通讯作者：
MALLOWS, CL
影响因子：
0.9
作者：
Ekhine Irurozki;Borja Calvo;J. A. Lozano
通讯作者：
Ekhine Irurozki;Borja Calvo;J. A. Lozano
通过与 Thurstone 模型组合回归进行监督排序
影响因子：
12
作者：
Toshihiro Kamishima;S. Akaho
通讯作者：
S. Akaho
候选人性别与选民选择：多人优先投票系统的分析
影响因子：
2.1
作者：
Gail Mcelroy;Michael Marsh
通讯作者：
Michael Marsh