De senaste åren har bevittnat ett ökande intresse för att utforma algoritmer för att fråga och analysera strömmande data (dvs. data som endast ses en gång i en fast ordning) med endast begränsat minne. Att tillhandahålla (kanske ungefärliga) svar på frågor över sådana kontinuerliga dataströmmar är ett avgörande krav för många applikationsmiljöer; exempel inkluderar stora telekom- och IP-nätinstallationer där prestandadata från olika delar av nätverket måste samlas in och analyseras kontinuerligt. I detta dokument anser vi att problemet med att ungefär besvara allmänna aggregerade SQL-frågor över kontinuerliga dataströmmar med begränsat minne. Vår metod bygger på randomisering tekniker som beräknar små "sketch" sammanfattningar av strömmar som sedan kan användas för att ge ungefärliga svar på aggregerade frågor med bevisbara garantier på approximation fel. Vi visar också hur befintlig statistisk information om basdata (t.ex. histogram) kan användas inom det föreslagna ramverket för att förbättra kvaliteten på den approximation som tillhandahålls av våra algoritmer. Nyckelidén är att intelligent dela upp domänen för de underliggande attributen och därmed bryta ner skissproblemet på ett sätt som på ett tillfredsställande sätt skärper våra garantier. Resultaten av vår experimentella studie med såväl verkliga som syntetiska dataströmmar visar att skisser ger betydligt mer exakta svar jämfört med histogram för aggregerade frågor. Detta gäller särskilt när våra domänpartitioneringsmetoder används för att ytterligare öka noggrannheten i de slutliga uppskattningarna. Traditionell programvara för databashantering (DBMS) bygger på konceptet med beständiga datamängder, som lagras på ett tillförlitligt sätt i stabil lagring och som frågas/uppdateras flera gånger under sin livstid. För flera nya tillämpningsområden anländer dock data och behöver behandlas på kontinuerlig (24 x 7) basis, utan fördelen av flera passerar över en statisk, ihållande databild. Sådana kontinuerliga dataströmmar uppstår till exempel naturligt i nätinstallationer av stora telekom- och Internetleverantörer där detaljerad användningsinformation (Call-Detail-Records (CDRs), SNMP/RMON paketflödesdata, etc.) från olika delar av det underliggande nätverket måste kontinuerligt samlas in och analyseras för intressanta trender. Andra applikationer som genererar *Arbete som görs när du besöker Bell Labs. Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior har detta meddelande och ~11 citering på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Snabba, kontinuerliga och stora volymer strömmande data inkluderar transaktioner i detaljhandelskedjor, ATM- och kreditkortsverksamhet i banker, finansiella tickers, webbserver loggposter, etc. I de flesta sådana applikationer, dataströmmen faktiskt ackumuleras och arkiveras i DBMS av en (kanske, off-site) datalager, ofta gör tillgång till arkiverade data oöverkomligt dyrt. Dessutom är förmågan att fatta beslut och dra slutsatser om intressanta mönster online (dvs. när dataströmmen anländer) avgörande för flera uppdragskritiska uppgifter som kan ha ett betydande dollarvärde för ett stort företag (t.ex. upptäckt av telekommunikationsbedrägerier). Som ett resultat har de senaste åren bevittnat ett ökande intresse för att utforma databehandlingsalgoritmer som fungerar över kontinuerliga dataströmmar, dvs. algoritmer som ger återpassar till användarens frågor samtidigt som man tittar på de relevanta dataobjekten endast en gång och i en fast ordning (som bestäms av ström-arrival mönster). Två nyckelparametrar för frågebehandling över kontinuerliga dataströmmar är (1) mängden minne som görs tillgängligt för online-algoritmen, och (2) den per-punkt behandlingstid som krävs av frågeprocessorn. Det förstnämnda utgör ett viktigt hinder för utformningen av stream process algoritmer, eftersom i en typisk strömmande miljö, endast begränsade minnesresurser är tillgängliga för frågebehandling algoritmer. I dessa situationer behöver vi algoritmer som kan sammanfatta de dataströmmar som är involverade i en koncis, men ganska exakt, synopsis som kan lagras i den tilldelade (liten) mängd minne och kan användas för att ge ungefärliga svar på användarfrågor tillsammans med några rimliga garantier för kvaliteten på approximationen. Sådana ungefärliga svar på on-line-frågor är särskilt väl anpassade till den undersökande karaktären hos de flesta data-stream behandling tillämpningar såsom t.ex. trendanalys och bedrägeri / onormal upptäckt i telekomnätverksdata, där målet är att identifiera generiska, intressanta eller "out-of-the-ordinary" mönster snarare än att ge resultat som är exakt till den sista decimalen. Tidigare arbete. Det starka incitamentet bakom dataströmsberäkning har gett upphov till flera färska (teoretiska och praktiska) studier av on-line- eller enpass-algoritmer med begränsade minneskrav för olika problem; exempel inkluderar kvantil- och orderstatistik beräkning [16, 21], uppskatta frekvensmoment och gå samman storlek [3, 2], datakluster och beslutsfattande träd konstruktion [10, 18], uppskatta korrelerade aggregat [13], och beräkna endimensionella (dvs. en-attribut) histogram och Haar våget dekompositioner [17, 15]. Andra relaterade studier har föreslagit tekniker för gradvis upprätthålla liksidiga histogram [14] och Haar wavelets [22], upprätthålla prover och enkel statistik över skjutbara fönster [8], samt allmänna, hög nivå arkitekturer för ström databassystem [4]. Ingen av de tidigare forskningsinsatserna har tagit itu med det allmänna problemet med behandling av allmänna, möjligen multi-join, aggregerade frågor över kontinuerliga dataströmmar. Å andra sidan, effektiv ap-61
Även om skissen partitionering teknik har föreslagits i den allmänna dataström domän för anslutning storlek uppskattning REF, är det i samband med icke-strukturella data.
Processing complex aggregate queries over data streams
{'venue': "SIGMOD '02", 'journal': None, 'mag_field_of_study': ['Computer Science']}