Publication Type

Journal Article

Publication Date

6-2017

Abstract

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on the sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into sub-windows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. To our best knowledge, it is the first algorithm that achieves logarithmic complexity w.r.t. k for incrementally maintaining the candidate set even in the worstcase scenarios.

Discipline

Databases and Information Systems | Data Storage Systems

Research Areas

Data Management and Analytics

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

29

Issue

6

First Page

1310

Last Page

1328

ISSN

1041-4347

Identifier

10.1109/TKDE.2017.2662236

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://doi.org./10.1109/TKDE.2017.2662236

Share

COinS