File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Edit distance to monotonicity in sliding windows

TitleEdit distance to monotonicity in sliding windows
Authors
KeywordsApproximate algorithms
Data stream
Deterministic algorithms
Edit distance
Linear spaces
Issue Date2011
PublisherSpringer 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?
AbstractGiven 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.
DescriptionSession 8A: Online and Streaming Algorithms
LNCS v. 7074 is proceedings of the 22nd International Symposium, ISAAC 2011
Persistent Identifierhttp://hdl.handle.net/10722/139996
ISSN
2020 SCImago Journal Rankings: 0.249
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorPan, Jen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Qen_HK
dc.date.accessioned2011-09-23T06:04:30Z-
dc.date.available2011-09-23T06:04:30Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 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-573en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/139996-
dc.descriptionSession 8A: Online and Streaming Algorithms-
dc.descriptionLNCS v. 7074 is proceedings of the 22nd International Symposium, ISAAC 2011-
dc.description.abstractGiven 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.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.subjectApproximate algorithms-
dc.subjectData stream-
dc.subjectDeterministic algorithms-
dc.subjectEdit distance-
dc.subjectLinear spaces-
dc.titleEdit distance to monotonicity in sliding windowsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-642-25591-5_58en_HK
dc.identifier.scopuseid_2-s2.0-84055190814en_HK
dc.identifier.hkuros194067en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84055190814&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume7074 LNCSen_HK
dc.identifier.spage564en_HK
dc.identifier.epage573en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 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.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridPan, J=54788140800en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Q=54788768300en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats