Vi presenterar effektiva parallella streamingalgoritmer för grundläggande frekvensbaserade aggregat i både skjutfönstret och de oändliga fönsterinställningarna. I skjutfönsterinställningen ger vi en parallell algoritm för att underhålla en rymdbunden blockräknare (SBBC). Med hjälp av SBBC härleder vi algoritmer för grundläggande räkning, frekvensuppskattning och tunga hitters som inte utför mer arbete än sina bästa sekventiella motsvarigheter. I den oändliga fönsterinställningen presenterar vi algoritmer för frekvensuppskattning, tunga hitters och räkna-min skiss. För både de oändliga fönster- och skjutfönsterinställningarna behandlar våra parallella algoritmer en "minibatch" av objekt med linjärt arbete och polylogparallelldjup. Vi visar också en lägre gräns som visar att arbetet med den parallella algoritmen är optimalt i fallet med tunga hitters och frekvensuppskattning. Enligt vår kunskap är dessa de första parallella algoritmerna för dessa problem som är bevisligen fungerar effektivt och har lågt djup.
Parallella algoritmer för grundläggande frekvensbaserade aggregat, inklusive tunga hitters konstruerades av Tangwongsan et al. Hoppa över det.
Parallel streaming frequency-based aggregates
{'venue': "SPAA '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}