Algoritmus streamování

Algoritmus  streamování je algoritmus pro zpracování sekvence dat v jednom nebo malém počtu průchodů.

Streamové algoritmy řeší problémy, kdy data přicházejí postupně a ve velkém objemu. Příkladem je analýza síťového provozu na straně routeru . Takové problémy ukládají přirozená omezení na dostupnou paměť (mnohem menší než je velikost vstupních dat) a dobu zpracování pro každý prvek sekvence u streamovacích algoritmů. Zpracování dat je často možné pouze v jednom průchodu.

Přísná omezení času a paměti často znemožňují exaktní řešení zkoumaného problému. Algoritmy toku jsou obvykle pravděpodobnostní a poskytují aproximaci přesné odpovědi.

Historie

Ačkoli se o takových algoritmech uvažovalo v pracích první poloviny 80. let [1] [2] , koncept streamovacího algoritmu byl poprvé formalizován v práci Alona , Matiase ( eng.  Yossi Matias ) a Szegediho ( eng.  Mario Szegedy ) v roce 1996 [3] . V roce 2005 byli autoři oceněni Gödelovou cenou za zásadní přínos k algoritmům streamování . 

V roce 2005 byl představen koncept semi-streamingového algoritmu [  4 ] jako algoritmy, které zpracovávají příchozí proud v konstantním nebo logaritmickém režimu.[ upřesnit ] počet průchodů.

Model

V datovém modelu toku se má za to, že část nebo celá sada vstupních dat, která je třeba zpracovat, není k dispozici pro náhodný přístup : vstupní data přicházejí postupně a nepřetržitě v jednom nebo více tocích. Datové toky mohou být reprezentovány uspořádanou sekvencí bodů („aktualizace“), ke kterým lze přistupovat v daném pořadí a pouze jednou nebo v omezeném počtu.

Mnoho publikací s vlákny považuje za úkol počítačové statistiky distribuce dat, která je příliš velká pro efektivní ukládání.[ specifikovat ] . Pro tuto třídu problémů se předpokládá, že vektor (nulově inicializovaný ) má v proudu určitý počet "aktualizací". Cílem takových algoritmů je vypočítat funkce s použitím výrazně menšího prostoru, než by vyžadovalo kompletní reprezentaci vektoru . Existují dva obecné modely pro aktualizaci těchto dat: " pokladna " a " turniket " ( angl . turniket ).   

V "hotovostním" modelu je každá "aktualizace" reprezentována ve tvaru a vektor je upraven tak, že se zvýší o nějaké kladné celé číslo . Zvláštní případ je případ (je povoleno vložit pouze jednu jednotku).

V modelu "turniket" je každá "aktualizace" reprezentována ve tvaru a vektor je upraven tak, že se zvětší o nějaké kladné nebo záporné celé číslo . V přísném modelu nemůže být v žádném okamžiku negativní.

V řadě zdrojů se navíc uvažuje s modelem „slide-window“. V tomto modelu je zájmová funkce počítána přes okno omezené dimenzionality z dat toku, prvky z konce okna se neberou v úvahu, dokud je nenahradí nová data z toku.

Tyto algoritmy berou v úvahu nejen problémy související s frekvenčními charakteristikami dat, ale také řadu dalších. Mnoho problémů na grafech se řeší za podmínky, že matice sousednosti grafu je předem načtena v nějakém neznámém pořadí. Někdy je naopak nutné vyřešit problém s odhadem pořadí dat, například spočítat počet převrácených hodnot v proudu a najít největší rostoucí sekvenci.

Porovnání algoritmů

Hlavní vlastnosti streamovacích algoritmů:

Tyto algoritmy mají mnoho společného s online algoritmy , protože algoritmus se musí rozhodnout dříve, než jsou k dispozici všechna data, ale existují rozdíly. In-line algoritmy mají zejména schopnost zpozdit rozhodování, dokud nepřijde skupina bodů v posloupnosti dat, zatímco online algoritmy se musí rozhodovat při příchodu každého nového bodu v posloupnosti.

Pokud je algoritmus přibližný, pak je dalším ukazatelem přesnost odpovědi. Přesnost algoritmu je často reprezentována jako hodnota , což znamená, že algoritmus dosáhne menší chyby s pravděpodobností .

Aplikace

Streamové algoritmy mají velký význam v úlohách monitorování a správy počítačových sítí, např. jejich pomocí lze rychle zabránit přetečení (sledování obřích toků odhadování počtu a předpokládané doby přetečení) [ ] Algoritmy streamování lze také použít v databázích, například k odhadu velikosti po operaci spojení tabulky .

Příklady problémů řešených streamovacími algoritmy

Problémy s distribucí frekvencí

Moment té frekvence ve vektoru je definován jako .

První moment  je prostý součet frekvencí (tedy celkový počet). Druhý bod je užitečný pro výpočet statistických parametrů dat, jako je Giniho koeficient . definována jako frekvence nejčastěji se vyskytujícího prvku.

Studovány jsou také otázky odhadu frekvenčních momentů.

Hledat těžké prvky

Úkolem je najít nejčastěji se vyskytující prvek v datovém toku. Zde platí následující algoritmy:

Sledování trendů

Trendování v datovém toku se obvykle provádí v následujícím pořadí: nejčastější prvky a jejich frekvence jsou určeny na základě jednoho z výše uvedených algoritmů.[ objasnit ] <--algoritmy pro hledání těžkých prvků? a pokud se tato sekce posune níže?-->, a pak se největší nárůst vzhledem k předchozímu časovému bodu zaznamená jako trend. K tomu se používá exponenciální klouzavý průměr a různé normalizace [6] . Používá prostor O(ε² + log d) a aktualizaci O(1) v nejhorším případě pro univerzální hašovací funkci z rodiny nezávislých hašovacích funkcí r-smart s r = Ω(log(1/ε)/ log log(1 / ε))[ specifikovat ] .

Entropie

Empirický odhad entropie přes soubor frekvencí je definován jako , kde [7] .

Strojové učení

Hlavním úkolem online strojového učení  je trénovat model (například klasifikátor) jedním průchodem trénovací sadou; k jeho používá prediktivní hašování a gradient

Počítání počtu jedinečných prvků

Dalším je počítání počtu jedinečných prvků v datovém toku (moment ) .[ objasnit ] dobře prostudovaný problém. První algoritmus navrhli Flajolet a Martin [2] . V roce 2010 byl nalezen asymptoticky optimální algoritmus [8] .

Poznámky

  1. ↑ Munro & Paterson (1980 )
  2. ↑ 1 2 Flajolet & Martin (1985 )
  3. ↑ Alon, Matias & Szegedy (1996 )
  4. ↑ Feigenbaum Joan , Kannan Sampath , McGregor Andrew , Suri Siddharth , Zhang Jian. O grafových problémech v semi-streamingovém modelu  // Teoretická informatika. - 2005. - prosinec ( roč. 348 , č. 2-3 ). - S. 207-216 . — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2005.09.013 .
  5. ↑ J. Xu Výukový program pro streamování dat v síti
  6. ↑ Schubert Erich , Weiler Michael , Kriegel Hans-Peter. SigniTrend  // Sborník příspěvků z 20. mezinárodní konference ACM SIGKDD o objevování znalostí a dolování dat - KDD '14. - 2014. - ISBN 9781450329569 . - doi : 10.1145/2623330.2623740 .
  7. ↑ Odhady entropie uvedli McGregor et al., Do Ba et al., Lall et al., Chakrabarti et al.[ upřesnit ]
  8. ↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), "Optimal algorithm for the different elements problem", Proceedings of 29th ACM SIGMOD-SIGACT-SIGART symposium on Principles of databázových systémů, PODS '10, New York, NY, USA: ACM, str. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 .

Literatura

Odkazy

učebnice Kurzy