Article

A near optimal algorithm for generating broadcast programs on multiple channels

Authors:

Arbee L. P. ChenAuthors Info & Claims

CIKM '01: Proceedings of the tenth international conference on Information and knowledge management

Pages 303 - 309

https://doi.org/10.1145/502585.502637

Published: 05 October 2001 Publication History

Abstract

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. In our approach, an expected average access time of the broadcast data items is first derived. The broadcast program is then generated, which minimizes the expected average access time. Simulation is performed to compare the performance of our approach with two existing approaches. The result of the experiments shows that our approach outperforms others and is in fact close to the optimal.

References

[1]

S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, "Broadcast Disks: Data management for Asymmetric Communication Environments," Proc. ACM SIGMOD Conf., pages. 199-2 10, San Jose, CA, May 1995.

Digital Library

[2]

S. Acharya, M. Franklin and S. Zdonik, "Disseminationbased Data Delivery Using Broadcast Disks", IEEE Personal Communications, 2(6), Dec. 1995.

[3]

S. Acharya, M. Franklin and S. Zdonik, "Disseminating Updates on Broadcast Disks", Proc. VLDB Conference, pages 354-365,1996.

Digital Library

[4]

S. Acharya, M. Franklin and S. Zdonik, "Prefetching from a Broadcast Disk", Proc. IEEE International Conference on Data Engineering, pages 276-285, 1996.

Digital Library

[5]

R. Alonso and H. Korth. "Database Systems in Nomadic Computing" In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 388-392, 1993.

Digital Library

[6]

T.F. Bowen, G. Gopal, G. Herman, T. Hickey, K.C. Lee, W.H. Mansfield, J. Raitz, and A. Weinrib. "The Datacycle Architecture". Communications of the ACM, pages 850-857, 1995.

[7]

J. Gray, P. Sundaresan, S. Englett, K. Baclawski, and P. J. Weinberger. "Quickly Generating Billion-Record Synthetic Databases". In Proceeding of ACM SIGMOD, pages: 243- 252, 1994.

Digital Library

[8]

A.R. Hurson, Y.C. Chehadeh and J. Hannan, "Object Organization on Parallel Broadcast Channels in a Global Information Sharing Environment," IEEE International Performance, Computing, and Communications Conference (IPCCC), February 2000.

[9]

G. Herman, G. Gopal, K.C. Lee, and A. Weinrib. "The Datacycle Architecture for Very High Throughput Database Systems". In Procedings of the 1987 ACM-SIGMOD International Conference on Management of Data, pages 97- 103, 1987.

Digital Library

[10]

S. hameed and N. Vaidya. "Efficient Algorithms for Scheduling Data Broadcastation". ACM/Baltzer Wireless Networks, 5(3):183-193,1999.

Digital Library

[11]

T. Imielinski, B.R. Badrinath, "Data Management for Mobile Computing" SIGMOD RECORD, 22(l): 34-39, 1993.

Digital Library

[12]

S.C. Lo and A. L. P. Chen. "Optimal Index and Data Allocation in Multiple Broadcast Channels". In Proceeding of the 16th International Conference on Data Engineering, pages 293-302,200O.

Digital Library

[13]

W.C. Peng and M.S. Chen, "Dynamic Generation of Data Broadcast Programs for a Broadcast Disk Array in a Mobile Computing Environment" Proc. of the ACM 9th Intern'1 Conf. on Information and Knowledge Management, November 6-l 1,200O.

Digital Library

[14]

Khan Prabhakra, Kien A. Hua, and JungHwan Oh, "Multi- Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment" In Proceeding of the 16th International Conference on Data Engineering, pages 167- 176,200O.

Digital Library

[15]

E. Pitoura and G. Samaras "Data Management for Mobile Computing", Kluwer Academic Publishers, 1998.

Digital Library

[16]

N. Shivakumar and S. Venkatasubramanian, "Energy- Efftcient Indexing For Information Dissemination In Wireless Systems," ACM, Journal of Wireless and Nomadic Application, 1996.

[17]

K.L Tan and B.C. Ooi. "Batch Scheduling for Demanddriven Servers in Wireless Environment". Information Sciences, 109:281-298, 1998.

Digital Library

[18]

N. Vaidya and S. Hameed. "Scheduling data broadcast in asymmetric communication environments" ACM/Baltzer Wireless Networks, 5(3):171-182,1999.

Digital Library

[19]

J.W. Wong. "Broadcast delivery", Proceeding of the IEEE, 76(12): 1566-1577, 1988.

Cited By

Chen CLee CWang S(2009)On optimal scheduling for time-constrained services in multi-channel data dissemination systemsInformation Systems10.1016/j.is.2008.05.00434:1(164-177)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.is.2008.05.004
Hung HChen M(2007)MULSIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2007.107219:10(1433-1447)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TKDE.2007.1072
Lo SChen A(2007)Efficient index and data allocation for wireless broadcast servicesData & Knowledge Engineering10.1016/j.datak.2006.02.00260:1(235-255)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1016/j.datak.2006.02.002
Show More Cited By

Index Terms

A near optimal algorithm for generating broadcast programs on multiple channels

Recommendations

An Efficient Algorithm for Near Optimal Data Allocation on Multiple Broadcast Channels

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of ...
Index and Data Allocation on Multiple Broadcast Channels Considering Data Access Frequencies
MDM '02: Proceedings of the Third International Conference on Mobile Data Management

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of ...
Near-optimal data allocation over multiple broadcast channels

Data broadcast is known as a scalable way to transmit database items to large client populations through a wireless channel. However, with a large set of items, the expected delay of receiving desired data increases due to the sequential nature of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '01: Proceedings of the tenth international conference on Information and knowledge management

October 2001

616 pages

ISBN:1581134363

DOI:10.1145/502585

Editors:
Henrique Paques
Georgia Institute of Technology
,
Ling Liu
Georgia Institute of Technology
,
David Grossman
Illinois Institute of Technology
,
General Chair:
Calton Pu
Georgia Institute of Technology

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM01

Sponsor:

CIKM01: International Conference on Information and Knowledge Management

October 5 - 10, 2001

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
450
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen CLee CWang S(2009)On optimal scheduling for time-constrained services in multi-channel data dissemination systemsInformation Systems10.1016/j.is.2008.05.00434:1(164-177)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.is.2008.05.004
Hung HChen M(2007)MULSIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2007.107219:10(1433-1447)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TKDE.2007.1072
Lo SChen A(2007)Efficient index and data allocation for wireless broadcast servicesData & Knowledge Engineering10.1016/j.datak.2006.02.00260:1(235-255)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1016/j.datak.2006.02.002
Hung HHuang JHuang JChen MHaddad H(2006)Scheduling dependent items in data broadcasting environmentsProceedings of the 2006 ACM symposium on Applied computing10.1145/1141277.1141555(1177-1181)Online publication date: 23-Apr-2006
https://dl.acm.org/doi/10.1145/1141277.1141555
Huang JPeng WChen M(2006)SOMIEEE Transactions on Mobile Computing10.1109/TMC.2006.1225:8(974-990)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1109/TMC.2006.122
Wang SChen H(2006)Near-optimal data allocation over multiple broadcast channelsComputer Communications10.1016/j.comcom.2005.10.01129:9(1341-1349)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1016/j.comcom.2005.10.011
Hsu CLee GChen A(2005)An Efficient Algorithm for Near Optimal Data Allocation on Multiple Broadcast ChannelsDistributed and Parallel Databases10.1007/s10619-005-4949-918:3(207-222)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1007/s10619-005-4949-9
Wang SChen H(2005)Restricted Dynamic Programming for Broadcast SchedulingNetwork Control and Engineering for QoS, Security and Mobility, III10.1007/0-387-23198-6_11(139-150)Online publication date: 2005
https://doi.org/10.1007/0-387-23198-6_11
Katsaros DManolopoulos Y(2004)Broadcast program generation for webcastingData & Knowledge Engineering10.1016/j.datak.2003.07.00149:1(1-21)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1016/j.datak.2003.07.001
Yee WNavathe SKraft DFrieder OHammer JQureshi SSeligman L(2003)Efficient data access to multi-channel broadcast programsProceedings of the twelfth international conference on Information and knowledge management10.1145/956863.956893(153-160)Online publication date: 3-Nov-2003
https://dl.acm.org/doi/10.1145/956863.956893
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten