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.
För en dataström av bitar används begreppet skjutfönster i REF för att uppskatta antalet 1-bitar i nyligen genererade N-bitar.
Maintaining Stream Statistics over Sliding Windows
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}