Abstrakt. Vi överväger problemet med att upprätthålla aggregat och statistik över dataströmmar, med avseende på de senaste N-dataelement som hittills setts. Vi hänvisar till denna modell som skjutfönstermodellen. Vi anser att följande grundläggande problem: Med tanke på en ström av bitar, hålla en räkning på antalet 1's i de senaste N element sett från strömmen. Vi visar att med hjälp av O( 1 log 2 N ) bitar av minne, kan vi uppskatta antalet 1 är att inom en faktor på 1 +. Vi ger också en matchande nedre gräns för 1 log 2 N ) minne bitar för alla deterministiska eller randomiserade algoritmer. Vi utökar vårt schema för att upprätthålla summan av de senaste N positiva heltal och ger matchande övre och nedre gränser för detta mer allmänna problem också. Vi visar också hur man på ett effektivt sätt beräknar Lp-normerna (p, [1, 2]) för vektorer i skjutfönstermodellen med hjälp av våra tekniker. Med hjälp av vår algoritm kan man anpassa många andra tekniker för att arbeta för skjutfönstermodellen med en multiplikativ overhead av O( 1 log N ) i minne och en 1 + faktorförlust i noggrannhet. Dessa inkluderar att upprätthålla ungefärliga histogram, hashtabeller, och statistik eller aggregat såsom summa och medelvärden.
Exponentiella histogram REF tillåter spårning av mätvärden över ett skjutfönster för att inom ett multiplikativt fel.
Maintaining Stream Statistics over Sliding Windows
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}