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

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

2012-04-05

arxiv.org/abs/1204.1098v1

Computer Science

Data Structures and Algorithms

Scientific paper

Approximating the length of the longest increasing sequence (LIS) of a data stream is a well-studied problem. There are many algorithms that estimate the size of the complement of the LIS, referred to as the \emph{distance to monotonicity}, both in the streaming and property testing setting. Let $n$ denote the size of an input array. Our aim is to develop a one-pass streaming algorithm that accurately approximates the distance to monotonicity, and only uses polylogarithmic storage. For any $\delta > 0$, our algorithm provides a $(1+\delta)$-multiplicative approximation for the distance, and uses only $O((\log^2 n)/\delta)$ space. The previous best known approximation using poly-logarithmic space was a multiplicative 2-factor. Our algorithm is simple and natural, being just 3 lines of pseudocode. It is essentially a polylogarithmic space implementation of a classic dynamic program that computes the LIS. Our technique is more general and is applicable to other problems that are exactly solvable by dynamic programs. We are able to get a streaming algorithm for the longest common subsequence problem (in the asymmetric setting introduced in \cite{AKO10}) whose space is small on instances where no symbol appears very many times. Consider two strings (of length $n$) $x$ and $y$. The string $y$ is known to us, and we only have streaming access to $x$. The size of the complement of the LCS is the edit distance between $x$ and $y$ with only insertions and deletions. If no symbol occurs more than $k$ times in $y$, we get a $O(k(\log^2 n)/\delta)$-space streaming algorithm that provides a $(1+\delta)$-multiplicative approximation for the LCS complement. In general, we also provide a deterministic 1-pass streaming algorithm that outputs a $(1+\delta)$-multiplicative approximation for the LCS complement and uses $O(\sqrt{(n\log n)/\delta})$ space.

Affiliated with

Also associated with

No associations

Rating

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212061