On-line stream merging with max span and min coverage

Wun Tat Chan; Tak Wah Lam; Hing Fung Ting; Prudence W.H. Wong

doi:10.1007/s00224-004-1182-2

On-line stream merging with max span and min coverage

Wun Tat Chan
, Tak Wah Lam
, Hing Fung Ting
, Prudence W.H. Wong

School of Continuing Education

Research output: Contribution to journal › Journal article › peer-review

2 Citations (Scopus)

Abstract

This 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.

Original language	English
Pages (from-to)	461-479
Number of pages	19
Journal	Theory of Computing Systems
Volume	38
Issue number	4
Early online date	28 Jan 2005
DOIs	https://doi.org/10.1007/s00224-004-1182-2
Publication status	Published - Jul 2005

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Access to Document

10.1007/s00224-004-1182-2

Cite this

@article{07ffcf6e2cc84e1399ba1681d1dc7c3c,

title = "On-line stream merging with max span and min coverage",

abstract = "This 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.",

author = "Chan, \{Wun Tat\} and Lam, \{Tak Wah\} and Ting, \{Hing Fung\} and Wong, \{Prudence W.H.\}",

note = "This research by the third author was supported in part by Hong Kong RGC Grant HKU-7024/01E Publisher Copyright: {\textcopyright} 2005 Springer Science+Business Media, Inc.",

year = "2005",

month = jul,

doi = "10.1007/s00224-004-1182-2",

language = "English",

volume = "38",

pages = "461--479",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On-line stream merging with max span and min coverage

AU - Chan, Wun Tat

AU - Lam, Tak Wah

AU - Ting, Hing Fung

AU - Wong, Prudence W.H.

PY - 2005/7

Y1 - 2005/7

N2 - This 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.

AB - This 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.

UR - https://www.scopus.com/pages/publications/22344453477

UR - https://link.springer.com/article/10.1007/s00224-004-1182-2#Ab1

U2 - 10.1007/s00224-004-1182-2

DO - 10.1007/s00224-004-1182-2

M3 - Journal article

AN - SCOPUS:22344453477

SN - 1432-4350

VL - 38

SP - 461

EP - 479

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 4

ER -

On-line stream merging with max span and min coverage

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this