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

Bagus Jati Santoso, Ge Ming Chiu

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number6654121
Pages (from-to)1853-1865
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number8
DOIs
Publication statusPublished - Aug 2014
Externally publishedYes

Keywords

  • Anchor set
  • close dominance graph
  • continuous query
  • dominance relationship
  • streaming model
  • top-k dominating query

Fingerprint

Dive into the research topics of 'Close dominance graph: An efficient framework for answering continuous top-k dominating queries'. Together they form a unique fingerprint.

Cite this