Close dominance graph: An efficient framework for answering continuous top-k dominating queries

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.