On-Line Stream Merging, Max Span, and Min Coverage | SpringerLink
Skip to main content
Springer Nature Link
Log in

On-Line Stream Merging, Max Span, and Min Coverage

  • Conference paper
  • First Online:
Algorithms and Complexity (CIAC 2003)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2653))

Included in the following conference series:

  • 454 Accesses

Abstract

This paper introduces the notions of span and coverage for analyzing the performance of on-line algorithms for stream merging. We show that these two notions can solely determine the competitive ratio of any such algorithm. Furthermore, we devise a simple greedy algorithm that can attain the ideal span and coverage, thus giving a better performance guarantee than existing algorithms with respect to either the maximum bandwidth or the total bandwidth. The new notions also allow us to obtain a tighter analysis of existing algorithms.

This research was supported in part by Hong Kong RGC Grant HKU-7024/01E

This research was supported in part by Hong Kong RGC Grant HKU-7045/02E

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. C. C. Aggarwal, J. L. Wolf, and P. S. Yu. On optimal piggyback merging policies for video-on-demand systems. In Proc. ACM Sigmetrics, pages 200–209, 1996.

    Google Scholar 

  2. A. Bar-Noy, J. Goshi, R. E. Ladner, and K. Tam. Comparison of stream merging algorithms for media-on-demand. In Proc. Conf. on Multi. Comput. and Net. (MMCN), pages 115–129, 2002.

    Google Scholar 

  3. A. Bar-Noy and R. E. Ladner. Competitive on-line stream merging algorithms for media-on-demand. In Proc. 12th ACM-SIAM SODA, pages 364–373, 2001.

    Google Scholar 

  4. Y. Cai, K. A. Hua, and K. Vu. Optimizing patching performance. In Proc. Conf. on Multi. Comput. and Net. (MMCN), pages 204–215, 1999.

    Google Scholar 

  5. S. W. Carter and D. D. E. Long. Improving bandwidth efficiency of video-on-demand. Computer Networks, 31(1–2):99–111, 1999.

    Google Scholar 

  6. W. T. Chan, T. W. Lam, H. F. Ting, and W. H. Wong. Competitive analysis of on-line stream merging algorithms. In Proc. 27th MFCS, pages 188–200, 2002.

    Google Scholar 

  7. W. T. Chan, T. W. Lam, H. F. Ting, and W. H. Wong. A unified analysis of hot video schedulers. In Proc. 34th ACM STOC, pages 179–188, 2002.

    Google Scholar 

  8. W. T. Chan, T. W. Lam, H. F. Ting, and W. H. Wong. On-line stream merging in a general setting. Theoretical Computer Science, 296(1):27–46, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  9. E. Coffman, P. Jelenkovic, and P. Momcilovic. The dyadic stream merging algorithm. Journal of Algorithms, 43(1), 2002.

    Google Scholar 

  10. D. Eager, M. Vernon, and J. Zahorjan. Bandwidth skimming: A technique for coste effective video-on-demand. In Proc. Conf. on Multi. Comput. and Net. (MMCN), pages 206–215, 2000.

    Google Scholar 

  11. D. Eager, M. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. IEEE Tran. on K. and Data Eng., 13(5):742–757, 2001.

    Article  Google Scholar 

  12. L. Golubchik, J. C. S. Lui, and R. R. Muntz. Adaptive piggybacking: A novel technique for data sharing in video-on-demand storage servers. ACM J. of Multi. Sys., 4(3):140–155, 1996.

    Article  Google Scholar 

  13. K. A. Hua, Y. Cai, and S. Sheu. Patching: A multicast technique for true video-on-demand services. In Proc. 6th ACM Multimedia, pages 191–200, 1998.

    Google Scholar 

  14. S. W. Lau, J. C. S. Lui, and L. Golubchik. Merging video streams in a multimedia storage server: Complexity and heuristics. ACM J. of Multi. Sys., 6(1):29–42, 1998.

    Article  Google Scholar 

  15. S. Sen, L. Gao, J. Rexford, and D. Towsley. Optimal patching schemes for efficient multimedia streaming. In Proc. 9th Int. W. on Net. and OS Support for Digital Audio and Video, pages 44–55, 1999.

    Google Scholar 

  16. P. W. H. Wong. On-line Scheduling of Video Streams. PhD thesis, The University of Hong Kong.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing, Hong Kong Polytechnic University, Hong Kong

    Wun-Tat Chan

  2. Department of Computer Science, University of Hong Kong, Hong Kong

    Tak-Wah Lam, Hing-Fung Ting & Prudence W. H. Wong

Authors
  1. Wun-Tat Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tak-Wah Lam
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hing-Fung Ting
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Prudence W. H. Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Infornatica, Università di Roma “La Sapienza”, Via Salaria 113, 00198, Rome, Italy

    Rossella Petreschi  & Riccardo Silvestri  & 

  2. Dipartimento di Infornatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, Via S. Allende 2, 84081, Baronissi, SA, Italy

    Giuseppe Persiano

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chan, WT., Lam, TW., Ting, HF., Wong, P.W.H. (2003). On-Line Stream Merging, Max Span, and Min Coverage. In: Petreschi, R., Persiano, G., Silvestri, R. (eds) Algorithms and Complexity. CIAC 2003. Lecture Notes in Computer Science, vol 2653. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44849-7_14

Download citation

  • DOI: https://doi.org/10.1007/3-540-44849-7_14

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40176-6

  • Online ISBN: 978-3-540-44849-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation