Vi undersöker problemet med kodad cachelagring för ickeuniforma krav när den strukturerade clique cover algoritm som föreslås av Maddah-Ali och Niesen för decentraliserad cache används för leverans. Vi tillämpar denna algoritm på alla användares krav oavsett deras behov sannolikheter. Detta gör det möjligt att koda bland de filer som har olika krav sannolikheter men gör tilldelningen av minne till olika filer utmanande under innehåll placeringsfasen. Som vårt huvudsakliga bidrag karakteriserar vi analytiskt den optimala placeringsstrategin som minimerar den förväntade leveranshastigheten under en lagringskapacitetsbegränsning. Det visas att den optimala placeringen följer antingen en två eller en tre grupp strategi, där en uppsättning mindre populära filer inte är cachad alls och filerna inom var och en av de andra uppsättningar tilldelas identiska mängder lagring som om de hade samma begäran sannolikheter. Vi visar att för en begränsad uppsättning lagringskapacitet, som vi kallar grundfallen av problemet, är de två gruppstrategierna alltid optimala. För annan lagringskapacitet uppnås optimal placering genom minnesdelning mellan vissa basfall och den resulterande placeringen följer antingen en två- eller tregruppsstrategi beroende på vilka basfall som används. Vi härleder en polynom tid algoritm som bestämmer bas fall av problemet med tanke på antalet cache och popularitet distribution av filer. Med tanke på problemets basfall kommer de optimala parametrarna för minnestilldelning för eventuell lagringskapacitet att härledas analytiskt. Index Terms-Coded caching, konvex optimering, icke-uniforma krav, submodulära funktioner.
Minnesdelning mellan sådana punkter måste utföras om cachestorleken inte är medlem i M. Den uppsättning basfall beror på populariteten hos filerna, antalet användare och antalet filer, och kan beräknas via en effektiv algoritm REF.
Full Characterization of Optimal Uncoded Placement for the Structured Clique Cover Delivery of Nonuniform Demands
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}