Reverse top-k queries
Reverse top-k queries
复制标题
DOI：
10.1109/icde.2010.5447890
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
A. Vlachou;C. Doulkeridis;Y. Kotidis;K. Nørvåg
中科院分区：
文献类型：
--
作者：
A. Vlachou;C. Doulkeridis;Y. Kotidis;K. Nørvåg
等级感知查询处理对于许多应用程序来说已经变得至关重要，这些应用程序基于各个用户的偏好仅向用户返回前k个对象。Top-k查询主要从用户的角度进行研究，主要关注高效的查询处理。在这项工作中，第一次，我们研究的top-k查询的角度来看，产品制造商。给定一个潜在的产品，该产品在top-k查询结果集中的用户偏好是什么？我们确定了一种新的查询类型，即反向top-k查询，这是必不可少的制造商，以评估潜在的市场和影响，他们的产品的基础上的竞争。我们正式定义了反向top-k查询，并介绍了两个版本的查询，即单色和双色。我们首先提供了一个几何解释的单色反向top-k查询的解决方案空间，有助于理解反向top-k查询概念。然后，我们更详细地研究了双色反向top-k查询的情况下，这是更有趣的实际应用。如果以简单的方式计算这样的查询，则需要针对数据库中的每个用户偏好评估前k个查询，这即使对于中等数据集也是非常昂贵的。在本文中，我们提出了一个有效的基于阈值的算法，消除候选用户的喜好，而不处理各自的top-k查询。此外，我们引入了一种基于物化的反向top-k视图的索引结构，以加快反向top-k查询的计算速度。物化反向top-k视图以可控的方式用预处理成本换取查询速度。我们的实验评估表明，我们的技术，减少了1至3个数量级的top-k计算所需的数量的效率。
Rank-aware query processing has become essential for many applications that return to the user only the top-k objects based on the individual user's preferences. Top-k queries have been mainly studied from the perspective of the user, focusing primarily on efficient query processing. In this work, for the first time, we study top-k queries from the perspective of the product manufacturer. Given a potential product, which are the user preferences for which this product is in the top-k query result set? We identify a novel query type, namely reverse top-k query, that is essential for manufacturers to assess the potential market and impact of their products based on the competition. We formally define reverse top-k queries and introduce two versions of the query, namely monochromatic and bichromatic. We first provide a geometric interpretation of the monochromatic reverse top-k query in the solution space that helps to understand the reverse top-k query conceptually. Then, we study in more details the case of bichromatic reverse top-k query, which is more interesting for practical applications. Such a query, if computed in a straightforward manner, requires evaluating a top-k query for each user preference in the database, which is prohibitively expensive even for moderate datasets. In this paper, we present an efficient threshold-based algorithm that eliminates candidate user preferences, without processing the respective top-k queries. Furthermore, we introduce an indexing structure based on materialized reverse top-k views in order to speed up the computation of reverse top-k queries. Materialized reverse top-k views trade preprocessing cost for query speed up in a controllable manner. Our experimental evaluation demonstrates the efficiency of our techniques, which reduce the required number of top-k computations by 1 to 3 orders of magnitude.