Reporting l most influential objects in uncertain databases based on probabilistic reverse top-k queries
Reporting l most influential objects in uncertain databases based on probabilistic reverse top-k queries
复制标题
基于概率反向top-k查询报告不确定数据库中最有影响力的对象
DOI：
10.1016/j.ins.2017.04.028
复制
发表时间：
2017-09-01
影响因子：
8.1
通讯作者：
Li, Keqin
中科院分区：
文献类型：
--
作者：
Xiao, Guoqing;Li, Kenli;Li, Keqin
逆向top-k查询是从产品制造商的角度提出的，对于制造商评估潜在市场是必不可少的。然而，现有的反向top-k查询方法都是基于底层数据是准确的(或确定的)的假设。由于不确定数据与确定数据之间的内在差异，这些方法不能直接应用于不确定数据集的处理。受此启发，本文首先对不确定数据上的概率反向top-k查询进行建模。此外，我们构造了一个概率TOP-L影响力查询，它报告了影响因子最大的1个最有影响力的对象，其中对象的影响因子定义为其概率反向top-k查询结果集的基数。为了提高查询速度，我们提出了有效的剪枝启发式算法。特别地，我们利用概率阈值TOP-K查询和概率轮廓线查询的一些性质来缩小该问题的搜索空间。此外，还估计了潜在用户的上界，以减少计算候选对象的概率反向top-k查询的成本。最后，结合所提出的剪枝策略，给出了高效的查询算法。使用真实世界和合成数据集的大量实验证明了我们提出的算法的效率和有效性。(C)2017 Elsevier Inc.保留所有权利。
Reverse top-k queries are proposed from the perspective of a product manufacturer, which are essential for manufacturers to assess the potential market. However, the existing approaches for reverse top-k queries are all based on the assumption that the underlying data are exact (or certain). Due to the intrinsic differences between uncertain and certain data, these methods cannot be applied to process uncertain data sets directly. Motivated by this, in this paper, we firstly model the probabilistic reverse top-k queries over uncertain data. Moreover, we formulate a probabilistic top-l influential query, that reports the 1 most influential objects having the largest impact factors, where the impact factor of an object is defined as the cardinality of its probabilistic reverse top-k query result set. We present effective pruning heuristics for speeding up the queries. Particularly, we exploit several properties of probabilistic threshold top-k queries and probabilistic skyline queries to reduce the search space of this problem. In addition, an upper bound of the potential users is estimated to reduce the cost of computing the probabilistic reverse top-k queries for the candidate objects. Finally, efficient query algorithms are presented seamlessly with integration of the proposed pruning strategies. Extensive experiments using both real-world and synthetic data sets demonstrate the efficiency and effectiveness of our proposed algorithms. (C) 2017 Elsevier Inc. All rights reserved.