Close Dominance Graph: An Efficient Framework for Answering Continuous Top- $k$ Dominating Queries
Close Dominance Graph: An Efficient Framework for Answering Continuous Top- $k$ Dominating Queries
复制标题
DOI：
10.1109/tkde.2013.172
复制
发表时间：
2014-08
影响因子：
8.9
通讯作者：
B. J. Santoso;Ge-Ming Chiu
中科院分区：
文献类型：
--
作者：
B. J. Santoso;Ge-Ming Chiu
数据库系统中常用的基于偏好的查询有两种：（1）top-k查询和（2）skyline查询。通过结合top-\（k\）查询中使用的排序规则和skyline查询中使用的支配关系的概念，出现了top-\（k\）支配查询，为数据处理提供了新的视角。这个查询返回数据集中支配分数最高的\（k\）条记录。然而，当数据集在流模型下操作时，top-\（k\）支配查询的处理是复杂的。随着新数据不断生成，同时旧数据从数据库中删除，连续top-\（k\）支配查询（cTKDQ）要求可以随时将更新的结果返回给用户。这项工作探讨了cTKDQ的问题，并提出了一个独特的索引结构，称为关闭优势图（CDG），以支持处理的cTKDQ。CDG提供了关于记录之间的优势关系的全面信息，这对于在有限的搜索空间内回答cTKDQ至关重要。然后，将cTKDQ的更新过程转换为影响CDG的一小部分的简单更新。实验结果表明，该方案是能够提供更好的性能相比，现有的解决方案。
There are two preference-based queries commonly used in database systems: (1) top-k query and (2) skyline query. By combining the ranking rule used in top-\(k\) query and the notion of dominance relationships utilized in the skyline query, a top-\(k\) dominating query emerges, providing a new perspective on data processing. This query returns the \(k\) records with the highest domination scores from the dataset. However, the processing of the top-\(k\) dominating query is complex when the dataset operates under a streaming model. With new data being continuously generated while stale data being removed from the database, a continuous top-\(k\) dominating query (cTKDQ) requires that updated results can be returned to users at any time. This work explores the cTKDQ problem and proposes a unique indexing structure, called a Close Dominance Graph (CDG), to support the processing of a cTKDQ. The CDG provides comprehensive information regarding the dominance relationship between records, which is vital in answering a cTKDQ with a limited search space. The update process for a cTKDQ is then converted to a simple update affecting a small portion of the CDG. Experimental results show that this scheme is able to offer much better performance when compared with existing solutions.