Vi löser flera grundläggande frågor inom området distribuerad funktionell övervakning, initierad av Cormode, Muthukrishnan och Yi (SODA, 2008), och får ny uppmärksamhet. I den här modellen finns k-platser som vart och ett följer sina inmatningsströmmar och kommunicerar med en central samordnare. Samordnarens uppgift är att kontinuerligt upprätthålla en ungefärlig utgång till en funktion som beräknas över föreningen av k-strömmarna. Målet är att minimera antalet bitar som kommuniceras. Låt p-th frekvens moment definieras som Fp = i f p i, där fi är frekvensen av element i. Vi visar den randomiserade kommunikation komplexiteten av att uppskatta antalet olika element (dvs. F0) upp till en 1 + ε faktor är  och att förbättra på de tidigare  på k + 1/ε 2 ) bundna och matcha kända övre gränser. För Fp, p > 1, förbättrar vi den tidigare informationen (k + 1/ε 2 ) som är bunden till och med (k p−1 /ε 2 ). Vi får liknande förbättringar för tunga hitters, empirisk entropi och andra problem. Våra nedre gränser är den första av något slag i distribuerad funktionell övervakning att bero på produkten av k och 1/ε 2. Dessutom är de nedre gränserna för den statiska versionen av den distribuerade funktionsövervakningsmodellen, där samordnaren bara behöver beräkna funktionen vid den tidpunkt då alla k-inmatningsströmmar slutar. Förvånansvärt nog motsvarar de nästan vad som är möjligt i den (dynamiska versionen av) distribuerade funktionsövervakningsmodellen där samordnaren behöver hålla reda på funktionen kontinuerligt när som helst. Vi visar också att vi kan uppskatta Fp, för alla p > 1, med hjälp av Õ(k p−1 poly(ε −1 )) kommunikation. Detta förbättras drastiskt jämfört med föregående Õ(k 2p+1 N 1−2/p poly(ε −1 )) bundet till Cormode, Mutukrishnan och Yi för allmän p, och deras Õ(k 2 /ε+ k 1.5 /ε 3 ) bundet till p = 2. För p = 2, löser vårt band sin huvudsakliga öppna fråga. Våra nedre gränser bygger på nya direkta summasatser för ungefärlig majoritet, och ger förbättringar till klassiska problem i standarddataströmsmodellen. För det första förbättrar vi den kända nedre gränsen för uppskattningen av Fp, p > 2, i t passerar från  på 1−2/p /(ε 2/p t)) till på (n 1−2/p /(ε 4/p t)), vilket ger den första gränsen * MADALGO är Center for Massive Data Algorithmics -a Center of the Danish National Research Foundation. som matchar vad vi förväntar oss när p = 2 för ett konstant antal pass. För det andra ger vi den första nedre gränsen för uppskattningen av F0 i t passerar med 1 / (ε 2 t)) bitar av utrymme som inte använder hårdheten i gap-hamming problem.
Frekvensmoment för alla p > 2 beaktas av Woodruff och Zhang i REF.
Tight bounds for distributed functional monitoring
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}