Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/70062
Title: Improved on-line stream merging : from a restricted to a general setting
Authors: Chan, WT
Lam, TW
Ting, HF
Wong, WH
Issue Date: 2001
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2001, v. 2108, p. 432-442 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
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.
Description: 7th Annual International Computing and Combinatorics Conference, COCOON 2001, Guilin, China, August 20-23, 2001
URI: http://hdl.handle.net/10397/70062
ISBN: 978-3-540-42494-9
978-3-540-44679-8
ISSN: 0302-9743
EISSN: 1611-3349
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.