<p>In the online framework, you get your inputs piece by piece. Do you have to act on them immediately? In other words, can you put some inputs aside, queue them, and process them at a later step?</p>
<p>For example, consider the online list labeling problem, where you have to keep an array of a given size in order. You get an element and have to place it somewhere in the array. Can you choose not to place that element immediately, queue it, and process it later? Does doing so break the &quot;online&quot; aspect of online list labeling?</p>

CC BY-SA 4.0
2024-12-09T18:00:22.980Z
Depends on the problem. More often than not, you have to act immediately, otherwise it's not really different than the offline version.
usul
CC BY-SA 4.0
2024-12-09T18:27:58.643Z
I believe the general idea of online/streaming frameworks is that the amount of data to be processed exceeds (usually by a lot) whatever amount of storage you have. Thus, I would say that buffering the input as described may be considered permissible, so long as the buffer size is smaller (probably significantly so) than the total input stream. As usul mentions, if you could buffer the entire input stream, then you're basically in the situation of an offline/non-streaming problem.
mhum
CC BY-SA 4.0
2024-12-09T19:09:48.573Z
Streaming is different model from the online model.
Chandra Chekuri
CC BY-SA 4.0
2024-12-09T19:13:08.103Z
So, there isn't a clear boundary on how big the buffer/queue should be? Is queuing log(n) elements, for example, at a time legal? To see why this cheap trick might be useful, consider the following variant of the online list labeling problem. For each element to be inserted, you get a predicted rank. Let the error be defined as the predicted rank minus the actual rank after inserting $n$ elements. To mitigate some of the error, a desperate action you can take is to queue $\log{n}$ elements, compare the prediction to both your array state and your queue, and fix the prediction accordingly.
trytryandtry
CC BY-SA 4.0
2024-12-09T19:31:32.387Z
@ChandraChekuri Ah that's right! I have a poor tendency to conflate streaming and online computation models. But you are correct, these are not equivalent.
mhum
CC BY-SA 4.0
2024-12-09T19:40:22.887Z
@trytryandtry Personally, I would say that anything that's dependent on the size of the input stream would be against the spirit of this type of problem. I.e.: only $O(1)$ size memory should be allowed.
mhum
<online-algorithms>
A Conceptual Question About Online Algorithms
trytryandtry
# A Conceptual Question About Online Algorithms

(Asked by: username_0 on 2024-12-09)

In the online framework, you get your inputs piece by piece. Do you have to act on them immediately? In other words, can you put some inputs aside, queue them, and process them at a later step?

For example, consider the online list labeling problem, where you have to keep an array of a given size in order. You get an element and have to place it somewhere in the array. Can you choose not to place that element immediately, queue it, and process it later? Does doing so break the "online" aspect of online list labeling?

**Tags:** online-algorithms

> **Comments:**
> **username_1**: Depends on the problem. More often than not, you have to act immediately, otherwise it's not really different than the offline version.  
> **username_2**: I believe the general idea of online/streaming frameworks is that the amount of data to be processed exceeds (usually by a lot) whatever amount of storage you have. Thus, I would say that buffering the input as described may be considered permissible, so long as the buffer size is smaller (probably significantly so) than the total input stream. As username_1 mentions, if you could buffer the entire input stream, then you're basically in the situation of an offline/non-streaming problem.  
> **username_3**: Streaming is different model from the online model.  
> **username_0**: So, there isn't a clear boundary on how big the buffer/queue should be? Is queuing log(n) elements, for example, at a time legal? To see why this cheap trick might be useful, consider the following variant of the online list labeling problem. For each element to be inserted, you get a predicted rank. Let the error be defined as the predicted rank minus the actual rank after inserting $n$ elements. To mitigate some of the error, a desperate action you can take is to queue $\log{n}$ elements, compare the prediction to both your array state and your queue, and fix the prediction accordingly.  
> **username_2**: @ChandraChekuri Ah that's right! I have a poor tendency to conflate streaming and online computation models. But you are correct, these are not equivalent.  
> **username_2**: @username_0 Personally, I would say that anything that's dependent on the size of the input stream would be against the spirit of this type of problem. I.e.: only $O(1)$ size memory should be allowed.  

---

## 0 answers

