Binary interpolation search for solution mapping on broadcast and on-demand channels in a mobile computing environment

Jiun-Long Huang*, Wen-Chih Peng, Ming Syan Chen

*Corresponding author for this work

Research output: Contribution to conferencePaper

10 Scopus citations

Abstract

We explore in this paper the problem of dynamic data and channel allocations with the number of communication channels and the number of data items given. It is noted that the combined use of broadcast and on-demand channels can utilize the bandwidth effectively for data dissemination in a mobile computing environment. We first derive the analytical models of the expected delays when the data are requested through the broadcast and on-demand channels. Then, we transform this problem into to a guided search problem. In light of the theoretical properties derived, we devise an algorithm based on binary interpolation search, referred to as algorithm BIS, to obtain solutions of high quality efficiently. In essence, algorithm BIS is guided to explore the solution space with higher likelihood to be the optimal first, thereby leading to an efficient and effective search. It is shown by our simulation results that the solution obtained by algorithm BIS is of very high quality and is in fact very close to the optimal one. Sensitivity analysis on several parameters, including the number of data items and the number of communication channels, is conducted.

Original languageEnglish
Pages434-441
Number of pages8
StatePublished - 1 Dec 2001
EventProceedings of the 2001 ACM CIKM: 10th International Conference on Information and Knowledge Management - Atlanta, GA, United States
Duration: 5 Nov 200110 Nov 2001

Conference

ConferenceProceedings of the 2001 ACM CIKM: 10th International Conference on Information and Knowledge Management
CountryUnited States
CityAtlanta, GA
Period5/11/0110/11/01

Keywords

  • Data broadcasting
  • Data dissemination
  • Dynamic data and channel allocation
  • Mobile computing

Fingerprint Dive into the research topics of 'Binary interpolation search for solution mapping on broadcast and on-demand channels in a mobile computing environment'. Together they form a unique fingerprint.

  • Cite this

    Huang, J-L., Peng, W-C., & Chen, M. S. (2001). Binary interpolation search for solution mapping on broadcast and on-demand channels in a mobile computing environment. 434-441. Paper presented at Proceedings of the 2001 ACM CIKM: 10th International Conference on Information and Knowledge Management, Atlanta, GA, United States.