Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment

Yongrui Qin, Hua Wei Wang, Ji Zhang, Xiaohui Tao, Wei Emma Zhang, Kerry Taylor, Quan Z. Sheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper tackles the key scheduling problem of reducing the overall wait time of mobile clients in wireless data broadcast systems. It is observed that in periodic broadcast, new mobile clients may join in and existing mobile clients may leave anytime; in on-demand broadcast, high uplink communication cost may occur as all clients have to submit their queries every time. These are likely to degrade existing broadcasting approaches. In this work, we study the scheduling problem of XML data broadcast in a hybrid mode, where the system supports both periodic broadcast and on-demand broadcast services at the same. By taking the structural similarity between XML documents into account, only a small portion of mobile clients would be involved in the scheduling process and all mobile clients can be served more effectively. In this way, communication cost at the client side can be reduced greatly. A formal theoretical analysis of the proposed technique is presented. Based on the analysis, a novel clustering-based scheduling algorithm is developed. Moreover, we utilize an aging method to predict the distribution of incoming queries based on small samples of queries from mobile clients. Finally, we evaluate the approach through a set of experiments and the results show that it can significantly improve access efficiency for mobile clients.

LanguageEnglish
Title of host publicationProceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015
PublisherIEEE Computer Society
Pages725-732
Number of pages8
Volume2016-January
ISBN (Electronic)9780769557854
DOIs
Publication statusPublished - 15 Jan 2016
Externally publishedYes
Event21st IEEE International Conference on Parallel and Distributed Systems - Melbourne, Australia
Duration: 14 Dec 201517 Dec 2015
Conference number: 21

Conference

Conference21st IEEE International Conference on Parallel and Distributed Systems
Abbreviated titleICPADS 2015
CountryAustralia
CityMelbourne
Period14/12/1517/12/15

Fingerprint

XML
Scheduling
Communication
Scheduling algorithms
Broadcasting
Costs
Aging of materials
Experiments

Cite this

Qin, Y., Wang, H. W., Zhang, J., Tao, X., Zhang, W. E., Taylor, K., & Sheng, Q. Z. (2016). Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment. In Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015 (Vol. 2016-January, pp. 725-732). [7384359] IEEE Computer Society. https://doi.org/10.1109/ICPADS.2015.96
Qin, Yongrui ; Wang, Hua Wei ; Zhang, Ji ; Tao, Xiaohui ; Zhang, Wei Emma ; Taylor, Kerry ; Sheng, Quan Z. / Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment. Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015. Vol. 2016-January IEEE Computer Society, 2016. pp. 725-732
@inproceedings{cd31b99d4ee74a529cdf704da83813ea,
title = "Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment",
abstract = "This paper tackles the key scheduling problem of reducing the overall wait time of mobile clients in wireless data broadcast systems. It is observed that in periodic broadcast, new mobile clients may join in and existing mobile clients may leave anytime; in on-demand broadcast, high uplink communication cost may occur as all clients have to submit their queries every time. These are likely to degrade existing broadcasting approaches. In this work, we study the scheduling problem of XML data broadcast in a hybrid mode, where the system supports both periodic broadcast and on-demand broadcast services at the same. By taking the structural similarity between XML documents into account, only a small portion of mobile clients would be involved in the scheduling process and all mobile clients can be served more effectively. In this way, communication cost at the client side can be reduced greatly. A formal theoretical analysis of the proposed technique is presented. Based on the analysis, a novel clustering-based scheduling algorithm is developed. Moreover, we utilize an aging method to predict the distribution of incoming queries based on small samples of queries from mobile clients. Finally, we evaluate the approach through a set of experiments and the results show that it can significantly improve access efficiency for mobile clients.",
author = "Yongrui Qin and Wang, {Hua Wei} and Ji Zhang and Xiaohui Tao and Zhang, {Wei Emma} and Kerry Taylor and Sheng, {Quan Z.}",
note = "No record of this in Eprints. HN 25/10/2017",
year = "2016",
month = "1",
day = "15",
doi = "10.1109/ICPADS.2015.96",
language = "English",
volume = "2016-January",
pages = "725--732",
booktitle = "Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015",
publisher = "IEEE Computer Society",
address = "United States",

}

Qin, Y, Wang, HW, Zhang, J, Tao, X, Zhang, WE, Taylor, K & Sheng, QZ 2016, Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment. in Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015. vol. 2016-January, 7384359, IEEE Computer Society, pp. 725-732, 21st IEEE International Conference on Parallel and Distributed Systems, Melbourne, Australia, 14/12/15. https://doi.org/10.1109/ICPADS.2015.96

Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment. / Qin, Yongrui; Wang, Hua Wei; Zhang, Ji; Tao, Xiaohui; Zhang, Wei Emma; Taylor, Kerry; Sheng, Quan Z.

Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015. Vol. 2016-January IEEE Computer Society, 2016. p. 725-732 7384359.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment

AU - Qin, Yongrui

AU - Wang, Hua Wei

AU - Zhang, Ji

AU - Tao, Xiaohui

AU - Zhang, Wei Emma

AU - Taylor, Kerry

AU - Sheng, Quan Z.

N1 - No record of this in Eprints. HN 25/10/2017

PY - 2016/1/15

Y1 - 2016/1/15

N2 - This paper tackles the key scheduling problem of reducing the overall wait time of mobile clients in wireless data broadcast systems. It is observed that in periodic broadcast, new mobile clients may join in and existing mobile clients may leave anytime; in on-demand broadcast, high uplink communication cost may occur as all clients have to submit their queries every time. These are likely to degrade existing broadcasting approaches. In this work, we study the scheduling problem of XML data broadcast in a hybrid mode, where the system supports both periodic broadcast and on-demand broadcast services at the same. By taking the structural similarity between XML documents into account, only a small portion of mobile clients would be involved in the scheduling process and all mobile clients can be served more effectively. In this way, communication cost at the client side can be reduced greatly. A formal theoretical analysis of the proposed technique is presented. Based on the analysis, a novel clustering-based scheduling algorithm is developed. Moreover, we utilize an aging method to predict the distribution of incoming queries based on small samples of queries from mobile clients. Finally, we evaluate the approach through a set of experiments and the results show that it can significantly improve access efficiency for mobile clients.

AB - This paper tackles the key scheduling problem of reducing the overall wait time of mobile clients in wireless data broadcast systems. It is observed that in periodic broadcast, new mobile clients may join in and existing mobile clients may leave anytime; in on-demand broadcast, high uplink communication cost may occur as all clients have to submit their queries every time. These are likely to degrade existing broadcasting approaches. In this work, we study the scheduling problem of XML data broadcast in a hybrid mode, where the system supports both periodic broadcast and on-demand broadcast services at the same. By taking the structural similarity between XML documents into account, only a small portion of mobile clients would be involved in the scheduling process and all mobile clients can be served more effectively. In this way, communication cost at the client side can be reduced greatly. A formal theoretical analysis of the proposed technique is presented. Based on the analysis, a novel clustering-based scheduling algorithm is developed. Moreover, we utilize an aging method to predict the distribution of incoming queries based on small samples of queries from mobile clients. Finally, we evaluate the approach through a set of experiments and the results show that it can significantly improve access efficiency for mobile clients.

UR - http://www.scopus.com/inward/record.url?scp=84964613655&partnerID=8YFLogxK

U2 - 10.1109/ICPADS.2015.96

DO - 10.1109/ICPADS.2015.96

M3 - Conference contribution

VL - 2016-January

SP - 725

EP - 732

BT - Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015

PB - IEEE Computer Society

ER -

Qin Y, Wang HW, Zhang J, Tao X, Zhang WE, Taylor K et al. Efficient algorithms for scheduling XML data in a mobile wireless broadcast environment. In Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015. Vol. 2016-January. IEEE Computer Society. 2016. p. 725-732. 7384359 https://doi.org/10.1109/ICPADS.2015.96