Improved On-Line Stream Merging: From a Restricted to a General Setting

Wun Tat Chan; Tak Wah Lam; Hing Fung Ting; Wai Ha Wong

doi:10.1007/3-540-44679-6_49

Improved On-Line Stream Merging: From a Restricted to a General Setting

Wun Tat Chan
, Tak Wah Lam
, Hing Fung Ting
, Wai Ha Wong

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

4 Citations (Scopus)

Abstract

Stream merging is a promising technique for reducing server bandwidth in video-on-demand systems. There are many heuristics for the problem proposed whose effectiveness has been confirmed empirically. However, it is desirable to prove their effectiveness mathematically. In the pioneering work [2], Bar-Noy and Ladner studied stream merging using competitive analysis. They designed an O(log n)-competitive online scheduler, where n is the totaln umber of stream requests. However, their result is applicable only to systems with large client bandwidth and buffer size. In this paper we design the first on-line scheduler for stream merging in the general setting, in which we lift the large resource requirements, and our scheduler achieves constant competitive ratio.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings
Editors	Jie Wang
Publisher	Springer Berlin Heidelberg
Pages	432-442
Number of pages	11
Edition	1st
ISBN (Electronic)	9783540446798
ISBN (Print)	9783540424949
DOIs	https://doi.org/10.1007/3-540-44679-6_49
Publication status	Published - 3 Aug 2001
Event	7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China Duration: 20 Aug 2001 → 23 Aug 2001 https://link.springer.com/book/10.1007/3-540-44679-6 (Conference Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Volume	2108
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	International Computing and Combinatorics Conference

Conference

Conference	7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Country/Territory	China
City	Guilin
Period	20/08/01 → 23/08/01
Internet address	https://link.springer.com/book/10.1007/3-540-44679-6 (Conference Proceedings)

Access to Document

10.1007/3-540-44679-6_49

Cite this

Chan, W. T., Lam, T. W., Ting, H. F., & Wong, W. H. (2001). Improved On-Line Stream Merging: From a Restricted to a General Setting. In J. Wang (Ed.), Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings (1st ed., pp. 432-442). (Lecture Notes in Computer Science; Vol. 2108), (International Computing and Combinatorics Conference). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-44679-6_49

Chan, Wun Tat ; Lam, Tak Wah ; Ting, Hing Fung et al. / Improved On-Line Stream Merging : From a Restricted to a General Setting. Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings. editor / Jie Wang. 1st. ed. Springer Berlin Heidelberg, 2001. pp. 432-442 (Lecture Notes in Computer Science). (International Computing and Combinatorics Conference).

@inproceedings{a49b6b98e7174783b4e59364090ae3f1,

title = "Improved On-Line Stream Merging: From a Restricted to a General Setting",

abstract = "Stream merging is a promising technique for reducing server bandwidth in video-on-demand systems. There are many heuristics for the problem proposed whose effectiveness has been confirmed empirically. However, it is desirable to prove their effectiveness mathematically. In the pioneering work [2], Bar-Noy and Ladner studied stream merging using competitive analysis. They designed an O(log n)-competitive online scheduler, where n is the totaln umber of stream requests. However, their result is applicable only to systems with large client bandwidth and buffer size. In this paper we design the first on-line scheduler for stream merging in the general setting, in which we lift the large resource requirements, and our scheduler achieves constant competitive ratio.",

author = "Chan, \{Wun Tat\} and Lam, \{Tak Wah\} and Ting, \{Hing Fung\} and Wong, \{Wai Ha\}",

note = "Publisher Copyright: {\textcopyright} 2001 Springer-Verlag Berlin Heidelberg. Funding Information: Research supported by the Hong Kong Research Grants Council HKU7103/99E.; 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2001",

month = aug,

day = "3",

doi = "10.1007/3-540-44679-6\_49",

language = "English",

isbn = "9783540424949",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "432--442",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics",

edition = "1st",

url = "https://link.springer.com/book/10.1007/3-540-44679-6",

}

Chan, WT, Lam, TW, Ting, HF & Wong, WH 2001, Improved On-Line Stream Merging: From a Restricted to a General Setting. in J Wang (ed.), Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings. 1st edn, Lecture Notes in Computer Science, vol. 2108, International Computing and Combinatorics Conference, Springer Berlin Heidelberg, pp. 432-442, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 20/08/01. https://doi.org/10.1007/3-540-44679-6_49

Improved On-Line Stream Merging: From a Restricted to a General Setting. / Chan, Wun Tat; Lam, Tak Wah; Ting, Hing Fung et al.
Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings. ed. / Jie Wang. 1st. ed. Springer Berlin Heidelberg, 2001. p. 432-442 (Lecture Notes in Computer Science; Vol. 2108), (International Computing and Combinatorics Conference).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Improved On-Line Stream Merging

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

AU - Chan, Wun Tat

AU - Lam, Tak Wah

AU - Ting, Hing Fung

AU - Wong, Wai Ha

PY - 2001/8/3

Y1 - 2001/8/3

N2 - Stream merging is a promising technique for reducing server bandwidth in video-on-demand systems. There are many heuristics for the problem proposed whose effectiveness has been confirmed empirically. However, it is desirable to prove their effectiveness mathematically. In the pioneering work [2], Bar-Noy and Ladner studied stream merging using competitive analysis. They designed an O(log n)-competitive online scheduler, where n is the totaln umber of stream requests. However, their result is applicable only to systems with large client bandwidth and buffer size. In this paper we design the first on-line scheduler for stream merging in the general setting, in which we lift the large resource requirements, and our scheduler achieves constant competitive ratio.

AB - Stream merging is a promising technique for reducing server bandwidth in video-on-demand systems. There are many heuristics for the problem proposed whose effectiveness has been confirmed empirically. However, it is desirable to prove their effectiveness mathematically. In the pioneering work [2], Bar-Noy and Ladner studied stream merging using competitive analysis. They designed an O(log n)-competitive online scheduler, where n is the totaln umber of stream requests. However, their result is applicable only to systems with large client bandwidth and buffer size. In this paper we design the first on-line scheduler for stream merging in the general setting, in which we lift the large resource requirements, and our scheduler achieves constant competitive ratio.

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

U2 - 10.1007/3-540-44679-6_49

DO - 10.1007/3-540-44679-6_49

M3 - Conference proceeding

AN - SCOPUS:84944054459

SN - 9783540424949

T3 - Lecture Notes in Computer Science

SP - 432

EP - 442

BT - Computing and Combinatorics

A2 - Wang, Jie

PB - Springer Berlin Heidelberg

Y2 - 20 August 2001 through 23 August 2001

ER -

Chan WT, Lam TW, Ting HF, Wong WH. Improved On-Line Stream Merging: From a Restricted to a General Setting. In Wang J, editor, Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings. 1st ed. Springer Berlin Heidelberg. 2001. p. 432-442. (Lecture Notes in Computer Science). (International Computing and Combinatorics Conference). doi: 10.1007/3-540-44679-6_49

Improved On-Line Stream Merging: From a Restricted to a General Setting

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this