En MapReduce algoritm kan beskrivas med en kartläggning schema, som tilldelar indata till en uppsättning reduktionsgivare, så att för varje nödvändig utdata finns det en reduktioner som tar emot alla indata som deltar i beräkningen av denna utdata. Reducerare har en kapacitet som begränsar de ingångar de kan tilldelas. De enskilda inflödena kan dock variera i fråga om storlek. Vi överväger för första gången att kartlägga scheman där indatastorlekar är en del av övervägandena och restriktionerna. En av de viktiga parametrarna för att optimera i alla MapReduce jobb är kommunikationskostnader mellan kartan och minska faser. Kommunikationskostnaden kan optimeras genom att minimera antalet kopior av indata som skickas till reduktionsföretagen. Kommunikationskostnaden är nära relaterad till antalet reduceringar av begränsad kapacitet som används för att på lämpligt sätt ta emot indata, så att kravet på hur indata måste uppfylla i en reduceringsgivare uppfylls. I detta arbete tar vi hänsyn till en familj av problem där det krävs att varje insats möter varandra input i minst en reduktion. Vi anser också en något olika familj av problem där varje inmatning i en lista, X, krävs för att uppfylla varje inmatning i en annan lista, Y, i minst en reduktioner. Vi bevisar att hitta en optimal kartläggning schema för dessa familjer av problem är NP-hård, och presentera en bin-packning-baserad approximation algoritm för att hitta en nära optimal kartläggning schema.
Afrati m.fl. REF presenterar en modell för minskningskapaciteten för att hitta en lägre gräns för kommunikationskostnaderna som en funktion av den totala storleken på indata som skickas till en reduktionsgivare.
Assignment Problems of Different-Sized Inputs in MapReduce
{'venue': 'TKDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}