Continuous Query for Top-$K$ Maximal Sum Intervals over Streaming Data

Abstract

The continuous identification of top-$k$ maximal sum intervals using a sliding window over a data stream is a critical operation for applications in IoT and beyond. A maximal sum interval is a non-overlapping, contiguous subsequence with the maximal sum in a sequence of signed values. Existing algorithms are ill-suited for streaming contexts: they either exhaustively enumerate all intervals even for small $k$ values, or depend on indexes that require frequent and costly restructuring. We propose a novel partition-based strategy. Our core insight is a partitioning scheme that guarantees that any maximal sum interval is fully contained within a single partition, enabling independent and parallel processing. This design provides two key advantages: it enables safe pruning of partitions that cannot contribute to top-$k$ results, drastically narrowing the search space, and it enables efficient, incremental maintenance of the maximal sum intervals in each partition. We develop algorithms for partition construction, incremental partition updates, and partition-based top-$k$ maximal sum interval search. Extensive experiments on real and synthetic datasets demonstrate that our approach significantly improves efficiency.

14 pages, 10 figures. Accepted by VLDB 2026 (PVLDB Vol. 19, No. 9)

Topics & keywords