Continuous Top-k Dominating Queries
Continuous Top-k Dominating Queries
复制标题
DOI：
10.1109/tkde.2011.43
复制
发表时间：
2012-05
影响因子：
8.9
通讯作者：
Maria Kontaki;A. Papadopoulos;Y. Manolopoulos
中科院分区：
文献类型：
--
作者：
Maria Kontaki;A. Papadopoulos;Y. Manolopoulos
Top-k支配查询使用直观的评分函数，该评分函数关于多维点的支配能力对多维点进行排名，即，一个点支配的点数。具有最佳的k个点（例如，最高的）分数被返回给用户。top-k和skyline查询都是在流媒体环境中研究的，其中数据集的变化非常频繁。在这样的环境中，需要连续查询处理技术来有效地监视查询结果，因为周期性的查询重新执行是计算密集的，并且因此是禁止的。这项工作包含了第一次研究连续top-k支配查询数据流。与连续top-k和skyline查询相比，连续top-k支配查询带来了额外的挑战。研究了三种精确算法（BFA，伊娃，ADA），其中ADA，这是增强了额外的优化技术，显示出最好的整体性能。在某些情况下，我们愿意用准确性换取速度。针对这一方向，提出了两种近似算法（AHBA和AMSA）。AHBA基于Hoeffding界提供关于结果准确性的概率保证，而AMSA执行更积极的计算，从而导致更有效的处理。基于真实生活和合成数据集的评估结果显示了我们技术的效率和可扩展性。
Top-k dominating queries use an intuitive scoring function which ranks multidimensional points with respect to their dominance power, i.e., the number of points that a point dominates. The k points with the best (e.g., highest) scores are returned to the user. Both top-k and skyline queries have been studied in a streaming environment, where changes to the data set are very frequent. In such an environment, continuous query processing techniques are required toward efficient monitoring of query results, since periodic query re-execution is computationally intensive, and therefore, prohibitive. This work contains the first study of continuous top-k dominating queries over data streams. In comparison to continuous top-k and skyline queries, continuous top-k dominating queries pose additional challenges. Three exact algorithms (BFA, EVA, ADA) are studied, and among them ADA, which is enhanced with additional optimization techniques, shows the best overall performance. In some cases, we are willing to trade accuracy for speed. Toward this direction, two approximate algorithms are proposed (AHBA and AMSA). AHBA offers probabilistic guarantees regarding the accuracy of the result based on the Hoeffding bound, whereas AMSA performs a more aggressive computation resulting in more efficient processing. Evaluation results, based on real-life and synthetic data sets, show the efficiency and scalability of our techniques.