Efficient data access to multi-channel broadcast programs

ABSTRACT

This paper studies fast access to data that are broadcast on multiple channels. Broadcast is a useful data dissemination technique because of its scalability, but is lacking when it comes to response time. Increasing the number of available broadcast channels is a logical way of increasing throughput. Little work, however, has considered the access structures necessary for making effective use of the additional channels. We propose various indexing schemes for a multi-channel broadcast program. We demonstrate the effectiveness of our techniques in decreasing response time and tuning time via extensive experiments over a wide range of parameters.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 3: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 4: K. C. Almeroth, M. H. Ammar, and Z. Fei. Scalable delivery of web pages using cyclic best-effort (udp) multicast. In Proc. IEEE INFOCOM, March 1998.
• 5: M. H. Ammar and J. W. Wong. The design of teletext broadcast cycles. Performance Evaluation, 5(4):235--242, December 1985.
• 6: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 7: M. J. Donahoo, M. H. Ammar, and E. W. Zegura. Multiple-channel multicast scheduling for scalable bulk-data transport. In Proc. IEEE INFOCOM, March 1999.
• 8: J. Fernandez and K. Ramamritham. Adaptive dissemination of data in time critical asymmetric communication environments. In Proceedings of Euromicro Real-Time Systems Symposium, pages 195--203, 1999.
• 9: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 10: GSM Association. Gsm world. Web Document, 2002. www.gsmworld.com.
• 11: Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States
• 12: Chih-Hao Hsu , Guanling Lee , Arbee L. P. Chen, A near optimal algorithm for generating broadcast programs on multiple channels, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502637]
• 13: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• 14: Sanjeev Khanna , Shiyu Zhou, On indexed data broadcast, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.463-472, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276859]
• 15: D. H. Layer. Digital radio takes to the road. IEEE Spectrum, July 2001.
• 16: Wang-Chien Lee , Qinglong Hu , Dik Lun Lee, A study on channel allocation for data dissemination in mobile computing environments, Mobile Networks and Applications, v.4 n.2, p.117-129, May 1999 [doi>10.1023/A:1019190613700]
• 17: Optimal Index and Data Allocation in Multiple Broadcast Channels, Proceedings of the 16th International Conference on Data Engineering, p.293, February 28-March 03, 2000
• 18: Marimba, Inc. Marimba, inc. web site. Web Document, 2002. www.marimba.com.
• 19: Wen-Chih Peng , Ming-Syan Chen, Dynamic generation of data broadcasting programs for a broadcast disk array in a mobile computing environment, Proceedings of the ninth international conference on Information and knowledge management, p.38-45, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354780]
• 20: Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment, Proceedings of the 16th International Conference on Data Engineering, p.167, February 28-March 03, 2000
• 21: S. M. Ross. Introduction to Probability Models. Academic Press, 6th edition, 1997.
• 22: Narayanan Shivakumar , Suresh Venkatasubramanian, Efficient indexing for broadcast based wireless systems, Mobile Networks and Applications, v.1 n.4, p.433-446, Dec. 1996
• 23: Nitin H. Vaidya , Sohail Hameed, Scheduling data broadcast in asymmetric communication environments, Wireless Networks, v.5 n.3, p.171-182, May 1999 [doi>10.1023/A:1019142809816]
• 24: S. Vishwanathan and T. Imielinski. Pyramid broadcasting for video on demand service. In IEEE Multimedia Computing and Networks Conference, February 1995.
• 25: W. G. Yee and S. B. Navathe. Efficient generation of broadcast schedules. In Submitted for Publication, 2002.
• 26: W. G. Yee and S. B. Navathe. Fast data access on multiple broadcast streams. Technical report, Georgia Institute of Technology, May 2003.
• 27: Wai Gen Yee , Shamkant B. Navathe , Edward Omiecinski , Christopher Jermaine, Efficient Data Allocation over Multiple Channels at Broadcast Servers, IEEE Transactions on Computers, v.51 n.10, p.1231-1236, October 2002 [doi>10.1109/TC.2002.1039849]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
access methods, broadcast, data dissemination, indexing, query processing, scheduling