Vi studerar problemet med att beräkna sambandet mellan n relationer i flera rundor av MapReduce. Vi introducerar en distribuerad och generaliserad version av Yannakakis algoritm, kallad GYM. GYM tar som indata någon generaliserad hypertree sönderdelning (GHD) av en fråga om bredd w och djup d, och beräknar frågan i O(d) rundor och O(n(n(in w + Out)) kommunikation och beräkningskostnad. Med hjälp av GYM uppnår vi två huvudresultat: (1) Varje widew fråga kan beräknas i O(n) rundor MapReduce med O(n(IN w + OUT)) kostnad; (2) Varje wide-w fråga kan beräknas i O(log(n)) rundor MapReduce med O(n(n) 3w + OUT) kostnad. Vi uppnår vårt andra resultat genom att visa hur man konstruerar en O(log(n)-djup och bredd-3w GHD av en fråga om bredd w. Vi beskriver en annan generell teknik för att konstruera ännu kortare djup GHD med längre bredder, effektivt visar ett spektrum av kompromisser man kan göra mellan kommunikation och beräkning och antalet rundor av MapReduce. Genom att simulera MapReduce i PRAM-modellen innebär vårt andra huvudresultat också resultatet av Gottlob et al. [12] att computing acyklic och konstantwidth frågor är i NC. För vissa frågor ger vårt tillvägagångssätt faktiskt betydligt färre PRAM-steg än byggandet av det senare papperet. Vi uppnår dock våra resultat med hjälp av Yannakakis algoritm, som har ansetts ha en sekventiell karaktär. Istället, Vi överraskande visar att Yannakakis algoritm kan parallelliseras avsevärt genom att ge det som input kort djup GHDs av frågor.
GYM REF algoritmen visar att tillåta logg (n) rundor av MapReduce i stället för bara en runda kan avsevärt minska kostnaderna.
GYM: A Multiround Join Algorithm In MapReduce
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}