On the monotonicity of a data stream (Q1677498)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the monotonicity of a data stream |
scientific article; zbMATH DE number 6806059
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the monotonicity of a data stream |
scientific article; zbMATH DE number 6806059 |
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
0 references
0 references
0 references
0 references
