File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On-line stream merging with max span and min coverage

TitleOn-line stream merging with max span and min coverage
Authors
KeywordsComputers
Theory of computing mathematics
Issue Date2005
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00224/
Citation
Theory Of Computing Systems, 2005, v. 38 n. 4, p. 461-479 How to Cite?
AbstractThis paper introduces the notions of span and coverage for analyzing the performance of on-line algorithms for stream merging. It is shown that these two notions can solely determine the competitive ratio of any such algorithm. Furthermore, we devise a simple greedy algorithm that attains the ideal span and coverage, thus giving a better performance guarantee than existing algorithms. The new notions also allow us to obtain a tighter analysis of existing algorithms. © 2005 Springer Science+Business Media, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/53600
ISSN
2015 Impact Factor: 0.719
2015 SCImago Journal Rankings: 0.677
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2009-04-03T07:24:19Z-
dc.date.available2009-04-03T07:24:19Z-
dc.date.issued2005en_HK
dc.identifier.citationTheory Of Computing Systems, 2005, v. 38 n. 4, p. 461-479en_HK
dc.identifier.issn1432-4350en_HK
dc.identifier.urihttp://hdl.handle.net/10722/53600-
dc.description.abstractThis paper introduces the notions of span and coverage for analyzing the performance of on-line algorithms for stream merging. It is shown that these two notions can solely determine the competitive ratio of any such algorithm. Furthermore, we devise a simple greedy algorithm that attains the ideal span and coverage, thus giving a better performance guarantee than existing algorithms. The new notions also allow us to obtain a tighter analysis of existing algorithms. © 2005 Springer Science+Business Media, Inc.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00224/en_HK
dc.relation.ispartofTheory of Computing Systemsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe original publication is available at www.springerlink.comen_HK
dc.subjectComputersen_HK
dc.subjectTheory of computing mathematicsen_HK
dc.titleOn-line stream merging with max span and min coverageen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1432-4350&volume=38&issue=4&spage=461&epage=479&date=2005&atitle=On-line+stream+merging+with+max+span+and+min+coverage+en_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1007/s00224-004-1182-2en_HK
dc.identifier.scopuseid_2-s2.0-22344453477en_HK
dc.identifier.hkuros103121-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-22344453477&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume38en_HK
dc.identifier.issue4en_HK
dc.identifier.spage461en_HK
dc.identifier.epage479en_HK
dc.identifier.isiWOS:000230362800006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats