Simplifying wireless social caching

Mohammed Karmoose; Martina Cardone; Christina Fragouli

doi:10.1109/ISIT.2016.7541331

Simplifying wireless social caching

Mohammed Karmoose, Martina Cardone, Christina Fragouli

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Social groups give the opportunity for a new form of caching. In this paper, we investigate how a social group of users can jointly optimize bandwidth usage, by each caching parts of the data demand, and then opportunistically share these parts among them upon meeting. We formulate this problem as a Linear Program (LP) with exponential complexity. Based on the optimal solution, we propose a simple heuristic inspired by the bipartite set-cover problem that operates in polynomial time. Furthermore, we prove a worst case gap between the heuristic and the LP solutions. Finally, we assess the performance of our algorithm using real-world mobility traces from the MIT Reality Mining project dataset.

Original language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	410-414
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541331
State	Published - Aug 10 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

Bibliographical note

Funding Information:
This work was partially supported by NSF under Awards 1423271 and 1321120

Publisher link

10.1109/ISIT.2016.7541331

Find It

Find It at U of M Libraries

Cite this

Karmoose, M., Cardone, M., & Fragouli, C. (2016). Simplifying wireless social caching. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 410-414). [7541331] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541331

Simplifying wireless social caching. / Karmoose, Mohammed; Cardone, Martina; Fragouli, Christina.

Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 410-414 7541331 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Karmoose, M, Cardone, M & Fragouli, C 2016, Simplifying wireless social caching. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541331, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 410-414, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541331

@inproceedings{1e9877b9ae544c22a9e6a3ed1a524d50,

title = "Simplifying wireless social caching",

abstract = "Social groups give the opportunity for a new form of caching. In this paper, we investigate how a social group of users can jointly optimize bandwidth usage, by each caching parts of the data demand, and then opportunistically share these parts among them upon meeting. We formulate this problem as a Linear Program (LP) with exponential complexity. Based on the optimal solution, we propose a simple heuristic inspired by the bipartite set-cover problem that operates in polynomial time. Furthermore, we prove a worst case gap between the heuristic and the LP solutions. Finally, we assess the performance of our algorithm using real-world mobility traces from the MIT Reality Mining project dataset.",

author = "Mohammed Karmoose and Martina Cardone and Christina Fragouli",

note = "Funding Information: This work was partially supported by NSF under Awards 1423271 and 1321120; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541331",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "410--414",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

}

TY - GEN

T1 - Simplifying wireless social caching

AU - Karmoose, Mohammed

AU - Cardone, Martina

AU - Fragouli, Christina

N1 - Funding Information: This work was partially supported by NSF under Awards 1423271 and 1321120

PY - 2016/8/10

Y1 - 2016/8/10

N2 - Social groups give the opportunity for a new form of caching. In this paper, we investigate how a social group of users can jointly optimize bandwidth usage, by each caching parts of the data demand, and then opportunistically share these parts among them upon meeting. We formulate this problem as a Linear Program (LP) with exponential complexity. Based on the optimal solution, we propose a simple heuristic inspired by the bipartite set-cover problem that operates in polynomial time. Furthermore, we prove a worst case gap between the heuristic and the LP solutions. Finally, we assess the performance of our algorithm using real-world mobility traces from the MIT Reality Mining project dataset.

AB - Social groups give the opportunity for a new form of caching. In this paper, we investigate how a social group of users can jointly optimize bandwidth usage, by each caching parts of the data demand, and then opportunistically share these parts among them upon meeting. We formulate this problem as a Linear Program (LP) with exponential complexity. Based on the optimal solution, we propose a simple heuristic inspired by the bipartite set-cover problem that operates in polynomial time. Furthermore, we prove a worst case gap between the heuristic and the LP solutions. Finally, we assess the performance of our algorithm using real-world mobility traces from the MIT Reality Mining project dataset.

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

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

U2 - 10.1109/ISIT.2016.7541331

DO - 10.1109/ISIT.2016.7541331

M3 - Conference contribution

AN - SCOPUS:84986000836

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 410

EP - 414

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -

Simplifying wireless social caching

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this