Budgeted data caching based on k-Median in mobile edge computing

Xiaoyu Xia, Feifei Chen, Guangming Cui, Mohamed Abdelrazek, John Grundy, Hai Jin, Qiang He

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)


In mobile edge computing (MEC), edge servers are deployed at base stations to provide highly accessible computational resources and storage capacities to nearby mobile devices. Caching data on edge servers can ensure the service quality and network latency for those mobile devices. However, an app vendor needs to ensure that the data caching cost does not exceed its data caching budget. In this paper, we present the budgeted edge data caching (BEDC) problem as a constrained optimization problem to maximize the overall reduction in data retrieval for all its app users within the budget, and prove that it is NP-hard. Then, we provide an approach named IP-BEDC for solving the BEDC problem optimally based on Integer Programming. We also provide an O(k) -approximation algorithm, namely α-BEDC, to find near-optimal solutions to the BEDC problems efficiently. Our proposed approaches are evaluated on a real-world data set and a synthesized data set. The results demonstrate that our approaches can solve the BEDC problem effectively and efficiently while significantly outperforming five representative approaches.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE International Conference on Web Services, ICWS 2020
EditorsErnesto Damiani, Peking University
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages10
ISBN (Electronic)9781728187860
ISBN (Print)9781728187877
Publication statusPublished - 2020
EventIEEE International Conference on Web Services 2020 - Virtual, Online, Beijing, China
Duration: 18 Oct 202024 Oct 2020
Conference number: 13th
https://conferences.computer.org/icws/2020/ (Website)
https://ieeexplore.ieee.org/xpl/conhome/9283848/proceeding (Proceedings)


ConferenceIEEE International Conference on Web Services 2020
Abbreviated titleICWS 2020
Internet address


  • approximation algorithm
  • data caching
  • low-latency services
  • mobile edge computing
  • optimization

Cite this