Close Dominance Graph: An Efficient Framework for Answering Continuous Top- \(k\) Dominating Queries
Bagus Jati Santoso, Ge-Ming Chiu · IEEE Transactions on Knowledge and Data Engineering · 2014
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.