Dynamic Multiple Continuous Top-K Queries Over Streaming Data

This paper studies the problem of DMCTQ (Dynamic Multiple Continuous Top-k Queries) over streaming data, a fundamental problem in the domain of streaming data management. Let S be the set of streaming data, and Q be the query workload. It contains a set of queries with different query parameters. Each query qi(n, s, k, F) in Q monitors objects generated in the last qi(n) time units, and returns qi(k) objects with the highest scores to the system whenever qi(s) time units pass. Some existing methods support DMCTQ but they incur high computational costs, especially when queries within Q are allowed to be changed. In this paper, we propose a novel framework named Skyline-based Top-k Query Framework (STKQF for short) over streaming data. It is based on the following observation. For two queries q1 and q2 in the query workload Q, if q1(n) > q2(n) and q1(k) > q2(k), the meaningful objects of q2 must be meaningful objects of q1. Therefore, we can support DMCTQ based on partial queries. Based on this, we propose a grid based index to maintain these queries, form a small number of virtual queries, support DMCTQ via monitoring meaningful objects under these virtual queries. Finally, we conduct extensive performance studies on large real and synthetic datasets, which demonstrate that our new framework could efficiently support DMCTQ over streaming data.