Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642255915_58
 Scopus: eid_2s2.084055190814
 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, 58 December 2011. in Lecture Notes in Computer Science, 2011, v. 7074, p. 564573 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 nondecreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming wellunderstood 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 outoforder 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 constantapproximate algorithm requires linear space. © 2011 SpringerVerlag. 
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  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
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  20110923T06:04:30Z   
dc.date.available  20110923T06:04:30Z   
dc.date.issued  2011  en_HK 
dc.identifier.citation  The 22nd International Symposium on Algorithm and Computation (ISAAC 2011), Yokohama, Japan, 58 December 2011. in Lecture Notes in Computer Science, 2011, v. 7074, p. 564573  en_HK 
dc.identifier.issn  03029743  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 nondecreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming wellunderstood 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 outoforder 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 constantapproximate algorithm requires linear space. © 2011 SpringerVerlag.  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.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
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/9783642255915_58  en_HK 
dc.identifier.scopus  eid_2s2.084055190814  en_HK 
dc.identifier.hkuros  194067  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.084055190814&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, 58 December 2011. In Lecture Notes in Computer Science, 2011, v. 7074, p. 564573   
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 