Paper Info
Title
On the monotonicity of a data stream.
Abstract
In this paper we consider problems related to the sortedness of a data stream. In the first part of this work, we investigate the problem of estimating the distance to monotonicity; given a finite stream of length n from alphabet {1,...,m}, we give a deterministic (2+N")-approximation algorithm for estimating its distance to monotonicity in space . This improves over the previous randomized (4+N")-approximation algorithm due to Gopalan, Jayram, Krauthgamer and Kumar in SODA 2007. We then consider the problem of approximating the length of the longest increasing subsequence of the input stream. Through the analysis of a multi-party communication game, we prove that deterministic streaming algorithms that approximate the length of the longest increasing subsequence within 1+N" factor require bits of space for any N" in the range (1/n, 1/6]. This bound matches the upper bound given in the work of Gopalan et al. within a log factor. We note that, independent of our work and via a different proof strategy, Gal and Gopalan has shown an lower bound for all N"a parts per thousand yen1/n including Omega(1) ranges.
Year
DOI
Venue
2015
10.1007/s00493-014-3035-1
Combinatorica
Field
DocType
Volume
Monotonic function,Discrete mathematics,Combinatorics,Longest increasing subsequence,Streaming algorithm,Data stream,Upper and lower bounds,Omega,Mathematics,Alphabet
Journal
35
Issue
ISSN
Citations 
6
0209-9683
1
PageRank 
References 
Authors
0.35
9
2
Name
Order
Citations
PageRank
Funda Ergün131022.81
Hossein Jowhari21728.53