I teoretisk informatikk er en datastrømmineralgoritme eller algoritmestreaming av streamingalgoritme på engelsk en algoritme for å ta en kontinuerlig strøm av varer. Disse algoritmene har generelt lite minne til rådighet (mye mindre enn størrelsen på inngangsvolumet) og liten tid til å tildele til hvert element.
Disse begrensningene kan innebære at en slik algoritme gir en omtrentlig respons basert på bruken av et sammendrag ( " Sammendrag " ) av datastrømmen i minnet.
Modellen deler noen aspekter med de elektroniske algoritmene , men de to modellene er forskjellige. I en streamingalgoritme kan svaret gis forsinket, og vanskeligheten er den lille plassen som er tilgjengelig, det kan til og med være flere passeringer på dataene. Tvert imot for online algoritmer, må avgjørelser tas når informasjonen mottas, og ressursene i rommet og i databehandlingstid er ikke begrenset.
For å finne hyppige elementer i en datastrøm, er det to typer algoritmer: algoritmer basert på tellinger og algoritmer basert på sammendrag ( “ Sketch ” ).
TellerSticky Sampling og Lossy-Counting er to viktige algoritmer i dette området, bare hvis de er målestokk. De er begge orienterte algoritmer falske positive ( " falske positive " ), dvs. de tillater seg å presentere i inntektspostene eller hyppige varesett når de ikke er det, men ingen falske negativer blir glemt.
Tapende tellerLossy-Counting er en av de første algoritmene som utforsker datastrømmer ved hjelp av modellen for flaggvinduer ( " landmark windows model " ). Det er en parametrisk algoritme som godtar to parametere fra brukeren: og hvor er feilfrekvensen og s er støtteterskelen ønsket av analytikeren. Hvis N er antall varesett som nettopp har kommet, bruker algoritmen vinduer med lengde 1 / . Utformingen av algoritmen sørger for at alle elementene (varesett) hvis faktiske frekvens er større enn sN (støtten til i i et sett med kardinalitet N er lik ) er i utgangslisten, ingen varesett der den faktiske frekvensen er mindre enn er i utgangslisten, og de estimerte frekvensene flyttes bare bort fra de faktiske frekvensene med en faktor som er høyest lik .
Klebrig prøvetakingSticky Sampling bruker vinduer med fast lengde, og en samplingsfrekvens r, dvs. at den velger et element med en sannsynlighet lik . Den bruker tre parametere - feilfrekvensen - er støtteterskelen, og sannsynligheten for feil ønsket av analytikeren. Hvis , de første ankomstene velges med en hastighet r lik 1, følgende 2t med en hastighet lik 2, .... Hvis analytikeren ber om utgang av varer (varesett) over terskelen s, l elementene inkludert frekvensen .
DSM-FIData Stream Mining for Frequent Itemset er en algoritme opprettet av Hua-Fu Li, Suh-Yin Lee og Man-Kwan Shan for å utforske hyppige varesett i en datastrøm.
" Very Fast Decision Trees elevner " reduserer tidslæringen for store inkrementelle datasett ved å delprøve datastrømmen. VFDT bruker et Hoeffding-tre.
CVFDT" Concept-adapting Very Fast Decision Trees elevner " er en forbedring av den forrige algoritmen ved at den tar hensyn til den konseptuelle drift ( " Concept drift " ).
Hoeffding treEt Hoeffding-tre er en inkrementell og evigvarende beslutningstreetalgoritme, som er i stand til å lære av en massiv datastrøm, med den antagelsen at distribusjonen av prøvene ikke varierer med tiden - ingen drift-konseptuelle ( " Concept drift " ). Denne algoritmen bygger et tre på en inkrementell måte, ved å samle inn bladene nok informasjon til å kunne velge i et gitt øyeblikk som er den beste egenskapen for å transformere disse bladene til noder. Inndelingen av bladet - som forvandler bladet til en node - i to underblad utføres ved bruk av Hoeffding-ulikhet ( " Hoeffding bound " ), et statistisk mål som gjør det mulig å vite fra hvor mange prøver en estimator er nær den sanne verdien av variabelen estimert med en sannsynlighet , hvis vi gir oss selv på forhånd.
BIRCH ( “ balansert iterativ reduksjon og klynging ved bruk av hierarkier ” ) er en uten tilsyn data mining algoritme som brukes til å produsere hierarkisk segmentering på spesielt store datavolumer. Denne algoritmen bruker segmentkarakteriseringsvektorer ( " Clustering Feature " ) sammensatt av hvor hver er en vektor, for å oppsummere mikrosegmentene ( " mikroklyngen " ) for å bygge et balansert tre sammensatt av disse mikrosegmentene. Informasjonen i en CF-vektor er tilstrekkelig til å beregne estimatorene for gjennomsnitt, varians, sentroider og visse avstander. CF-treet har tre parametere: B forgreningsfaktoren, T terskelen, L det maksimale antall blader under de siste nodene. Arkene er sammenkoblet av pekere før og følger. Algoritmen foregår i tre faser: den første består av å lese dataene og bygge CF-treet innenfor grensen for tilgjengelig minne. Den andre fasen brukes til å eliminere aberrasjonene ( " outlier " ) og en segmenteringsalgoritme brukes i fase tre for å segmentere bladene.
Nedre grenser kan beregnes for streamingalgoritmene , spesielt ved å bruke resultatene av kommunikasjonskompleksiteten .