RECORD
Streaming Algorithms for Partitioning Integer Sequences
Data Structures and Algorithms · Submitted 7 Apr 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim All discussed algorithms require space $O( \frac{1}{\epsilon} \mathrm{polylog} (m,n,\frac{1}{\epsilon}))$, and we prove that the linear dependency on $\frac{1}{\epsilon}$ is necessary for any possibly randomized one-pass streaming algorithm that computes a $(1+\epsilon)$-approximation.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study the problem of partitioning integer sequences in the one-pass data streaming model. Given is an input stream of integers $X \in \{0, 1, \dots, m \}^n$ of length $n$ with maximum element $m$, and a parameter $p$. The goal is to output the positions of separators splitting the input stream into $p$ contiguous blocks such that the maximal weight of a block is minimized. We show that computing an optimal solution requires linear space, and we design space efficient $(1+\epsilon)$-approximation algorithms for this problem following the parametric search framework. We demonstrate that parametric search can be successfully applied in the streaming model, and we present more space efficient refinements of the basic method. All discussed algorithms require space $O( \frac{1}{\epsilon} \mathrm{polylog} (m,n,\frac{1}{\epsilon}))$, and we prove that the linear dependency on $\frac{1}{\epsilon}$ is necessary for any possibly randomized one-pass streaming algorithm that computes a $(1+\epsilon)$-approximation.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study the problem of partitioning integer sequences in the one-pass data streaming model. | background 0.59 | 0.76 | 0.03 | asserted 0.80 |
| s1 | Given is an input stream of integers $X \in \{0, 1, \dots, m \}^n$ of length $n$ with maximum element $m$, and a parameter $p$. | background 0.79 | 0.15 | 0.02 | asserted 0.94 |
| s2 | The goal is to output the positions of separators splitting the input stream into $p$ contiguous blocks such that the maximal weight of a block is minimized. | background 0.95 | 0.10 | 0.05 | asserted 0.95 |
| s3 | We show that computing an optimal solution requires linear space, and we design space efficient $(1+\epsilon)$-approximation algorithms for this problem following the parametric search framework. | contribution 0.87 | 0.96 | 0.57 | asserted 1.00 |
| s4 | We demonstrate that parametric search can be successfully applied in the streaming model, and we present more space efficient refinements of the basic method. | contribution 0.84 | 0.94 | 0.13 | asserted 1.00 |
| s5 | All discussed algorithms require space $O( \frac{1}{\epsilon} \mathrm{polylog} (m,n,\frac{1}{\epsilon}))$, and we prove that the linear dependency on $\frac{1}{\epsilon}$ is necessary for any possibly randomized one-pass streaming algorithm that computes a $(1+\epsilon)$-approximation. | result 0.93 | 0.94 | 0.53 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study the problem of partitioning integer sequences in the one-pass data streaming model. Given is an input stream of integers $X \in \{0, 1, \dots, m \}^n$ of length $n$ with maximum element $m$, and a parameter $p$. The goal is to output the positions of separators splitting the input stream into $p$ contiguous blocks such that the maximal weight of a block is minimized. We show that computing an optimal solution requires linear space, and we design space efficient $(1+\epsilon)$-approximation algorithms for this problem following the parametric search framework. We demonstrate that parametric search can be successfully applied in the streaming model, and we present more space efficient refinements of the basic method. All discussed algorithms require space $O( \frac{1}{\epsilon} \mathrm{polylog} (m,n,\frac{1}{\epsilon}))$, and we prove that the linear dependency on $\frac{1}{\epsilon}$ is necessary for any possibly randomized one-pass streaming algorithm that computes a $(1+\epsilon)$-approximation.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.