A generic framework for top-kpairs and top-kobjects queries over sliding windows

Zhitao Shen, Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, Haixun Wang

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)


Top-k pairs and top-k objects queries have received significant attention by the research community. In this paper, we present the first approach to answer a broad class of top-k pairs and top-k objects queries over sliding windows. Our framework handles multiple top-k queries and each query is allowed to use a different scoring function, a different value of k, and a different size of the sliding window. Furthermore, the framework allows the users to define arbitrarily complex scoring functions and supports out-of-order data streams. For all the queries that use the same scoring function, we need to maintain only one K-skyband. We present efficient techniques for the K-skyband maintenance and query answering. We conduct a detailed complexity analysis and show that the expected cost of our approach is reasonably close to the lower bound cost. For top-k pairs queries, we demonstrate the efficiency of our approach by comparing it with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost. For top-k objects queries, our experimental results demonstrate the superiority of our algorithm over the state-of-the-art algorithm.
Original languageEnglish
Pages (from-to)1349-1366
Number of pages18
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Publication statusPublished - Jun 2014
Externally publishedYes


  • Top-k pairs
  • top-k objects
  • sliding windows
  • data streams
  • top-k queries

Cite this