Databases and Information Systems Commons^™

Continuous Monitoring Of Top-K Queries Over Sliding Windows, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias

Kyriakos MOURATIDIS

Given a dataset P and a preference function f, a top-k query retrieves the k tuples in P with the highest scores according to f. Even though the problem is well-studied in conventional databases, the existing methods are inapplicable to highly dynamic environments involving numerous long-running queries. This paper studies continuous monitoring of top-k queries over a fixed-size window W of the most recent data. The window size can be expressed either in terms of the number of active tuples or time units. We propose a general methodology for top-k monitoring that restricts processing to the sub-domains of the workspace …