Finding longest increasing and common subsequences in streaming data
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet Sigma has length at least k, we discuss a one-pass algorithm using O(k log vertical bar Sigma vertical bar) space, with update time either O(log k) or O(log log vertical bar Sigma vertical bar); for vertical bar Sigma vertical bar=O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Omega(k) on the space requirement for this problem for general alphabets Sigma, even when the input stream is a permutation of Sigma. For finding the actual LIS, we give a [log(1+1/epsilon)]-pass algorithm using O(k(1+epsilon) log vertical bar Sigma vertical bar)space, for any epsilon>0. For LCS, there is a trivial Theta(1)-approximate O(log n)-space streaming algorithm when vertical bar Sigma vertical bar=O(1). For general alphabets Sigma, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Omega(n/rho(2)) space to approximate the LCS of two n-element streams to within a factor of rho, even if the streams are permutations of each other.
algorithms lower bounds lis lcs data-streaming model