On the monotonicity of a data stream (Q1677498)
From MaRDI portal
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
0 references
0 references
0 references
0 references