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
Chan, WTLam, TWTing, HFWong, PWH
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?
DOI: http://dx.doi.org/10.1007/s00224-004-1182-2
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
1432-4350
2021 Impact Factor: 0.616
2020 SCImago Journal Rankings: 0.479
ISI Accession Number ID
WOS:000230362800006
References
References in Scopus

 

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.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
dc.identifier.issnl1432-4350-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats