File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-25591-5_58
- Scopus: eid_2-s2.0-84055190814
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Edit distance to monotonicity in sliding windows
Title | Edit distance to monotonicity in sliding windows |
---|---|
Authors | |
Keywords | Approximate algorithms Data stream Deterministic algorithms Edit distance Linear spaces |
Issue Date | 2011 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 22nd International Symposium on Algorithm and Computation (ISAAC 2011), Yokohama, Japan, 5-8 December 2011. in Lecture Notes in Computer Science, 2011, v. 7074, p. 564-573 How to Cite? |
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 w ≥ 1. We give a deterministic algorithm which can return an estimate within a factor of (4 + ε) using O(1/ε 2 log 2 (ε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 + ε)-approximate algorithm using O(1/ε 2 log ε 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. © 2011 Springer-Verlag. |
Description | Session 8A: Online and Streaming Algorithms LNCS v. 7074 is proceedings of the 22nd International Symposium, ISAAC 2011 |
Persistent Identifier | http://hdl.handle.net/10722/139996 |
ISSN | 2020 SCImago Journal Rankings: 0.249 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Lee, LK | en_HK |
dc.contributor.author | Pan, J | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.contributor.author | Zhang, Q | en_HK |
dc.date.accessioned | 2011-09-23T06:04:30Z | - |
dc.date.available | 2011-09-23T06:04:30Z | - |
dc.date.issued | 2011 | en_HK |
dc.identifier.citation | The 22nd International Symposium on Algorithm and Computation (ISAAC 2011), Yokohama, Japan, 5-8 December 2011. in Lecture Notes in Computer Science, 2011, v. 7074, p. 564-573 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/139996 | - |
dc.description | Session 8A: Online and Streaming Algorithms | - |
dc.description | LNCS v. 7074 is proceedings of the 22nd International Symposium, ISAAC 2011 | - |
dc.description.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 w ≥ 1. We give a deterministic algorithm which can return an estimate within a factor of (4 + ε) using O(1/ε 2 log 2 (ε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 + ε)-approximate algorithm using O(1/ε 2 log ε 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. © 2011 Springer-Verlag. | en_HK |
dc.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_HK |
dc.subject | Approximate algorithms | - |
dc.subject | Data stream | - |
dc.subject | Deterministic algorithms | - |
dc.subject | Edit distance | - |
dc.subject | Linear spaces | - |
dc.title | Edit distance to monotonicity in sliding windows | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chan, HL: hlchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW: hresltk@hkucc.hku.hk | en_HK |
dc.identifier.email | Lee, LK: lklee@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HF: hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Lee, LK=rp00140 | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1007/978-3-642-25591-5_58 | en_HK |
dc.identifier.scopus | eid_2-s2.0-84055190814 | en_HK |
dc.identifier.hkuros | 194067 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-84055190814&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 7074 LNCS | en_HK |
dc.identifier.spage | 564 | en_HK |
dc.identifier.epage | 573 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.description.other | The 22nd International Symposium on Algorithm and Computation (ISAAC 2011), Yokohama, Japan, 5-8 December 2011. In Lecture Notes in Computer Science, 2011, v. 7074, p. 564-573 | - |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Lee, LK=12646190100 | en_HK |
dc.identifier.scopusauthorid | Pan, J=54788140800 | en_HK |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
dc.identifier.scopusauthorid | Zhang, Q=54788768300 | en_HK |
dc.identifier.issnl | 0302-9743 | - |