Ilmu Komputer & AI editorial
Open AccessOA2026
Continuous Query for Top-$K$ Maximal Sum Intervals over Streaming Data
A partition-based strategy for efficient top- maximal sum interval identification in sliding windows
Zhongshuai Zhang; Xiaochun Yang; Baihua Zheng; Rui Zhu; Haomin Li; Bin Wang· 2026· DOI 10.48550/arXiv.2607.11035
The core problem
The continuous identification of top- 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 values, or depend on indexes that require frequent and costly restructuring. This paper addresses these limitations by proposing a novel partition-based strategy.
Innovation
Extensive experiments on real and synthetic datasets demonstrate that the proposed approach significantly improves efficiency. The partition-based strategy outperforms existing algorithms, especially for small values, by avoiding exhaustive enumeration and costly index restructuring. The safe pruning mechanism effectively narrows the search space, and incremental maintenance ensures low update overhead as the sliding window moves.
The continuous identification of top- 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 values, or depend on indexes that require frequent and costly restructuring. This paper addresses these limitations by proposing a novel partition-based strategy.
The core insight of the proposed approach 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- results, drastically narrowing the search space, and it enables efficient, incremental maintenance of the maximal sum intervals in each partition. The authors develop algorithms for partition construction, incremental partition updates, and partition-based top- maximal sum interval search.
Why it matters
The partition-based strategy offers a robust solution for continuous top- maximal sum interval queries in streaming environments. Its ability to process partitions independently and in parallel makes it suitable for distributed and real-time applications. The incremental maintenance further enhances its practicality for high-velocity data streams. Future work may explore adaptive partitioning and extensions to other types of interval queries.
Who should read this
CS practitioners and researchers
Opening member content…