Streaming Stochastic Submodular Maximization with On-Demand User Requests

Honglian Wang, Sijing Tu, Lutz Oettershagen, Aristides Gionis · 2026

Read Streaming Stochastic Submodular Maximization with On-Demand User Requests by Honglian Wang, Sijing Tu, Lutz Oettershagen, Aristides Gionis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10901.txt.

Introduction

Honglian Wang, Sijing Tu, Lutz Oettershagen, and Aristides Gionis study streaming submodular maximization with on-demand requests. The setting mirrors news recommendation sites. Users can arrive at any time. At each visit, the site must show up to k news items, chosen from a stream it cannot store whole. Picks must be diverse yet relevant, the hallmark of submodular goals.

The on-demand twist breaks the usual one-pass setup: queries come when users come, not when the stream ends. Algorithms must keep a compact summary ready at all times. The work formalizes this problem and its trade-offs. It serves platform designers who must answer instantly from endless content with bounded memory.

Catalog record

CREATORHonglian Wang, Sijing Tu, Lutz Oettershagen, Aristides Gionis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Streaming Stochastic Submodular Maximization with On-Demand User Requests Honglian Wang, Sijing Tu, Lutz Oettershagen, Aristides Gionis Abstract We explore a novel problem in streaming submodular maximization, inspired by the dynamics of news-recommendation platforms. We consider a setting where users can visit a news website at any time, and upon each visit, the website must display up to k k news items. User interactions are inherently stochastic: each news item presented to the user is consumed with a certain acceptance probability by the user, and each news item covers certain topics. Our goal is to design a streaming algorithm that maximizes the expected total topic coverage. To address this problem, we establish a connection to submodular maximization subject to a matroid constraint. We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance or linear-size memory in the stream length is available. However, in more realistic scenarios where only an upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance. To overcome these limitations, we introduce a new online streaming algorithm that achieves a competitive ratio of 1 / ( 8 ​ δ ) 1/(8\delta) , where δ \delta controls the approximation quality. Moreover, it requires only a single pass over the stream, and uses memory independent of the stream length. Empirically, our algorithms consistently outperform the baselines. 1 Introduction Streaming submodular maximization has been extensively studied under various feasibility constraints, including matchoid [ 8 , 9 , 11 ] , matroid [ 10 ] , knapsack [ 22 , 23 ] and k - set [ 21 ] constraints. In the classical setting, the goal is to select a single subset of items from a data stream and output it when the stream ends. However, this classical framework falls short in many real-world scenarios, for example, when seeking to maximize content coverage in online news recommendation. In such a setting, users visit a news website multiple times and expect to receive a relevant set of articles on each visit. Meanwhile, new articles continuously arrive at the content-provider’s server in a stream fashion. The long-term objective is to maximize the total content coverage across user visits. Existing streaming submodular maximization algorithms are ill-suited for this use case, as they are designed to produce a single solution and do not support multiple or on-demand user interactions during the stream. Motivated by this limitation, we introduce a novel problem called Streaming Stochastic Submodular Maximization with On-demand Requests ( S3MOR ). While the setting is broadly applicable to streaming submodular maximization tasks with multiple output requirements, we focus on the news recommendation task for illustration. Therefore, in S3MOR , the data stream consists of incoming news items that the system aggregates into a personalized news website. Each item V_{i} covers a set of topics and is associated with a probability p_{i} , representing the probability that a user will click on the item when it is presented. A user may visit the system arbitrarily often and at any time during the stream. At each visit, the system must select and present a subset of at most k items from those that have arrived in the stream up to that point. If a user clicks on item V_{i} , they are exposed to all topics associated with that item. The objective is to maximize the expected total number of unique topics covered by all user clicks across all visits. This setting is challenging due to its online character: • On-demand : At any point, the system must be ready to output a subset of news items. • Irrevocability : Once a subset is presented to the user, it cannot be modified. To the best of our knowledge, no existing algorithm directly addresses the S3MOR problem. We evaluate the performance of online streaming algorithms that make irrevocable decisions using the notion of competitive ratio . An algorithm is called c -competitive if, for every input stream \sigma , the value \mathcal{A}(\sigma) achieved by algorithm \mathcal{A} satisfies \frac{\mathcal{A}(\sigma)}{\mathbf{OPT}(\sigma)}\geq c, where \mathbf{OPT}(\sigma) denotes the value of an optimal offline solution with full access to the input stream. To evaluate the performance of our algorithms, we clarify the notions of response time complexity , time complexity , and space complexity . Response-time complexity vs. time complexity. For the S3MOR problem, we assume there exists an oracle that can evaluate the objective function f(S) for any feasible candidate set S . We define the response time complexity of an algorithm as the worst-case number of oracle calls needed to produce a recommendation result of size k after the user submits a request. This metric captures the latency users experience. In contrast, time complexity is defined as the worst-case number of oracle calls required by the algorithm over the entire stream. Space complexity. In practice, all users share common storage for original news items. We distinguish between two storage types: shared storage containing original items accessible to all users (not counted toward space complexity), and per-user storage for additional memory each user needs to compute personalized recommendations, including document identifiers and user-item association probabilities. Throughout this paper, "space complexity" refers exclusively to per-user storage. Table 1: Comparison of our algorithms. N\in\mathbb{N} denotes the stream length, k\in\mathbb{N} number of news items to present per user access, T\in\mathbb{N} and T^{\prime}\in\mathbb{N} are the exact number and upper bound of user accesses, and \delta\in\mathbb{N} an approximation parameter. Algorithm Competitive ratio Time Space Response time LMGreedy \nicefrac{{1}}{{2}} \mathcal{O}(NT^{\prime}k) \Theta(N+kT) \mathcal{O}(Nk) Storm \nicefrac{{1}}{{4(T^{\prime}-T+1)}} \mathcal{O}(NT^{\prime}k) \mathcal{O}(T^{\prime}k) \mathcal{O}(T^{\prime}) Storm ++ \nicefrac{{1}}{{(8\delta)}} \mathcal{O}(NT^{{}^{\prime}2}k/\delta) \mathcal{O}(T^{{}^{\prime}2}k/\delta) \mathcal{O}(T^{\prime}) Our contributions. We reduce S3MOR to the problem of streaming submodular maximization under a partition matroid constraint , which allows us to leverage existing online streaming algorithms. Based on this reduction, we propose three algorithms and evaluate them across multiple dimensions: competitive ratio, space complexity, time complexity, and response time complexity. We state our main results as follows: • We prove that provided sufficient memory to store the whole stream, a greedy algorithm, LMGreedy , can achieve the best possible 1/2 competitive ratio for the S3MOR problem. • If the exact number T of user visits is known, the reduction preserves the competitive ratio of the underlying online streaming submodular algorithm. • However, in realistic scenarios, the number of user visits T is unknown and we need to guess the number of visits as T^{\prime}>T . For this case, we introduce an algorithm Storm , which has a competitive ratio of \frac{1}{4(T^{\prime}-T+1)} . • To achieve a better competitive ratio, we propose a second algorithm Storm ++ that makes multiple concurrent guesses of T , maintaining one solution per guess. It then greedily aggregates outcomes across guesses. This algorithm achieves a competitive ratio of \nicefrac{{1}}{{(8\delta)}} , where \delta is a tunable parameter that balances efficiency and solution quality. The space and time complexity increase by a factor of \delta T^{\prime} relative to the underlying streaming algorithm. • Storm and Storm ++ achieve worse competitive ratios than LMGreedy , but they utilize much smaller space and have significantly better response time. We summarize the results for all algorithms mentioned above in Table 1 . We validate

Read the complete text