Branch-and-bound algorithm for reverse top-k queries
Branch-and-bound algorithm for reverse top-k queries
复制标题
DOI：
10.1145/2463676.2465278
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
A. Vlachou;C. Doulkeridis;K. Nørvåg;Y. Kotidis
中科院分区：
文献类型：
--
作者：
A. Vlachou;C. Doulkeridis;K. Nørvåg;Y. Kotidis
Top-k 查询根据个人用户偏好仅向用户返回 k 个最佳对象，并且构成了排名感知查询处理的重要工具。假设存储了用户偏好的数据集，引入了反向前k个查询来检索将给定数据库对象视为其前k个结果之一的用户。由于市场分析和产品植入等大量现实应用，反向前 k 项查询已经引起了人们对研究的极大兴趣。目前，计算反向top-k集最有效的算法是RTA。 RTA 在处理反向 top-k 查询时有两个主要缺点：(i) 它需要访问所有存储的用户首选项，以及 (ii) 它无法避免对属于结果集的每个用户首选项执行 top-k 查询。为了解决这些限制，在本文中，我们确定了处理反向 top-k 查询的有用属性，而无需访问每个用户的个人偏好或执行 top-k 查询。我们提出了一种直观的分支定界算法来有效地处理反向 top-k 查询，并讨论了新颖的优化以提高其性能。我们的实验评估证明了所提出算法的效率大大优于 RTA。
Top-k queries return to the user only the k best objects based on the individual user preferences and comprise an essential tool for rank-aware query processing. Assuming a stored data set of user preferences, reverse top-k queries have been introduced for retrieving the users that deem a given database object as one of their top-k results. Reverse top-k queries have already attracted significant interest in research, due to numerous real-life applications such as market analysis and product placement. Currently, the most efficient algorithm for computing the reverse top-k set is RTA. RTA has two main drawbacks when processing a reverse top-k query: (i) it needs to access all stored user preferences, and (ii) it cannot avoid executing a top-k query for each user preference that belongs to the result set. To address these limitations, in this paper, we identify useful properties for processing reverse top-k queries without accessing each user's individual preferences nor executing the top-k query. We propose an intuitive branch-and-bound algorithm for processing reverse top-k queries efficiently and discuss novel optimizations to boost its performance. Our experimental evaluation demonstrates the efficiency of the proposed algorithm that outperforms RTA by a large margin.