Edit Distance to Monotonicity in Sliding Windows

Details Edit Distance to Monotonicity in Sliding Windows Edit Distance to Monotonicity in Sliding Windows

2011-11-23

arxiv.org/abs/1111.5386v1

Computer Science

Data Structures and Algorithms

10 pages

Scientific paper

Given a stream of items each associated with a numerical value, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the $w$ most recent items in the stream for any $w \ge 1$. We give a deterministic algorithm which can return an estimate within a factor of $(4+\eps)$ using $O(\frac{1}{\eps^2} \log^2(\eps w))$ space. We also extend the study in two directions. First, we consider a stream where each item is associated with a value from a partial ordered set. We give a randomized $(4+\epsilon)$-approximate algorithm using $O(\frac{1}{\epsilon^2} \log \epsilon^2 w \log w)$ space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space.

Affiliated with

Also associated with

No associations

Rating

Edit Distance to Monotonicity in Sliding Windows 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 Edit Distance to Monotonicity in Sliding Windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edit Distance to Monotonicity in Sliding Windows will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376537