On the monotonicity of a data stream (Q1677498): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s00493-014-3035-1 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2090968858 / rank | |||
Normal rank | |||
Revision as of 20:53, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the monotonicity of a data stream |
scientific article |
Statements
On the monotonicity of a data stream (English)
0 references
10 November 2017
0 references
In this paper the authors consider problems related to the sortedness of a data stream. In the first part of this work the problem of estimating the distance to monotonicity is investigated. Then the problem of approximating the length of the longest increasing subsequence of the input stream is discussed. Through the analysis of a multi-party communication game, bounds are given using the deterministic streaming algorithms that approximate the length of the longest increasing subsequence.
0 references
monotonicity
0 references
streaming algorithms
0 references
inversions
0 references
probabilistic method
0 references
