Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

摘要: Approximating the length of longest increasing sequence (LIS) an array is a well-studied problem. We study this problem in data stream model, where algorithm allowed to make single left-to-right pass through and key resource be minimized amount additional memory used. present which, for any δ > 0, given streaming access n provides (1 + δ)-multiplicative approximation distance monotonicity (n minus LIS), uses only O((log2n)/δ) space. The previous best known using polylogarithmic space was multiplicative 2-factor. improved factor reflects qualitative difference between our algorithms: algorithms could not reliably detect subsequences as large n/2, while ours can βn β 0. More precisely, used estimate LIS within additive δn 0 achieve error n(1/2 -- o(1)).Our very simple, being just 3 lines pseudocode, has small update time. It essentially approximate implementation classic dynamic program that computes LIS.We also show how technique applied other problems solvable by programs. For example, we give approximating LCS(x, y), common subsequence strings x y, each n. Our works asymmetric setting (inspired [AKO10]), which have random y x, runs provided no symbol appears often y. it gives additive-δn y) (and hence E(x, = edit when insertions deletions, but substitutions, are allowed), with complexity O(k(log2n)/δ), k maximum number times one y.We provide deterministic 1-pass outputs (which δn-approximation), setting, O(√n/δ log(n)) All these obtained carefully trading accuracy standard program.