Edit Distance to Monotonicity in Sliding Windows

DOI10.1007/978-3-642-25591-5_58MaRDI QIDQ3104657zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ho-Leung Chan, Lap-Kei Lee, Jiangwei Pan, Qin Zhang, Tak-Wah Lam, Hing-Fung Ting

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.5386

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Data structures (68P05) Approximation algorithms (68W25)

Abstract: 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 $wge1$. We give a deterministic algorithm which can return an estimate within a factor of $(4+eps)$ using $O(frac1ep{s}^{2}lo{g}^2(epsw))$ 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(frac1epsilo{n}^{2}logepsilo{n}^{2}wlogw)$ 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.

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• The smoothed complexity of edit distance
• The Smoothed Complexity of Edit Distance
• Edit distance and its computation
• A sublinear algorithm for weakly approximating edit distance
• RLE edit distance in near optimal time
• Approximating the geometric edit distance

Cited in

(3)

• Derandomization for sliding window algorithms with strict correctness
• A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
• Randomized sliding window algorithms for regular languages

This page was built for publication: Edit Distance to Monotonicity in Sliding Windows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104657)