Streaming algoritmus - Streaming algorithm

A számítástechnika , a streaming algoritmusok algoritmusokat feldolgozására adatfolyamok , amelyben a bemenő kerül bemutatásra, mint a szekvencia elemek és lehet vizsgálni csak néhány menetben (általában csak egy ). A legtöbb modellben ezek az algoritmusok korlátozott memóriához férnek hozzá (általában logaritmikusak az adatfolyam méretében és/vagy maximális értékében). Előfordulhat, hogy az egyes tételek feldolgozási ideje is korlátozott.

Ezek a korlátozások azt jelenthetik, hogy egy algoritmus hozzávetőleges választ ad az adatfolyam összegzése vagy "vázlata" alapján.

Történelem

Bár a streaming algoritmusokat Munro és Paterson már 1978 -ban, valamint Philippe Flajolet és G. Nigel Martin 1982/83 -ban tanulmányozta, a streaming algoritmusok területét először Noga Alon , Yossi 1996 -os dokumentumában formalizálta és népszerűsítette. Matias , és Szegedy Mario . Ehhez a cikkhez a szerzők később 2005 -ben elnyerték a Gödel -díjat "a streaming algoritmusokhoz nyújtott alapvető hozzájárulásukért". Azóta nagy mennyiségű munka folyik az adatfolyam -algoritmusok köré, amelyek számítástechnikai területek széles skáláját ölelik fel, mint például az elmélet, az adatbázisok, a hálózatépítés és a természetes nyelvfeldolgozás.

A féláramú algoritmusokat 2005-ben vezették be a gráfok streamelési algoritmusainak lazításaként, amelyekben a megengedett tér lineáris az n csúcsok számában , de csak logaritmikus az m élek számában . Ez a lazítás még mindig jelentős a sűrű gráfok számára, és megoldhat olyan érdekes problémákat (például a kapcsolódást), amelyek térben oldhatatlanok . ${\ displaystyle o (n)}$

Modellek

Adatfolyam modell

Az adatfolyam -modellben a bemenet egy része vagy egésze egész számok véges szekvenciájaként jelenik meg (valamilyen véges tartományból), amely általában nem érhető el véletlenszerű hozzáféréshez , hanem egyenként érkezik egy "folyamban". Ha az adatfolyamnak hossza n , és a domain van mérete m , algoritmusok általában korlátozott hely használni, amely logaritmikus a m és n . Általában csak kis számú állandó áthaladást tudnak végrehajtani a patakon, néha csak egyet .

Forgatókapu és pénztárgép modellek

A streaming szakirodalom nagy része statisztikai számításokkal foglalkozik a tárolásra túl nagy frekvenciaeloszlásokról. Ennek a problémakörnek van egy vektora (inicializálva a nulla vektorra ), amely frissítéseket mutat be a folyamban. Ezen algoritmusok célja olyan funkciók kiszámítása, amelyek lényegesen kevesebb helyet foglalnak el, mint amennyi a pontos ábrázoláshoz szükséges . Az ilyen folyamok frissítésére két általános modell létezik, az úgynevezett "pénztárgép" és a "turnstile" modell. ${\ displaystyle \ mathbf {a} = (a_ {1}, \ pontok, a_ {n})}$${\ displaystyle \ mathbf {0}}$${\ displaystyle \ mathbf {a}}$${\ displaystyle \ mathbf {a}}$

A pénztárgép -modellben minden frissítés formájú , tehát néhány pozitív egész számmal növekszik . Figyelemre méltó különleges eset, amikor (csak az egység behelyezése megengedett). ${\ displaystyle \ langle i, c \ rangle}$${\ displaystyle a_ {i}}$${\ displaystyle c}$${\ displaystyle c = 1}$

A forgószárnyas modellben minden frissítés formájú , tehát néhány (esetleg negatív) egész számmal növelhető . A "szigorú turnstile" modellben egyetlen esetben sem lehet kevesebb nullánál. ${\ displaystyle \ langle i, c \ rangle}$${\ displaystyle a_ {i}}$${\ displaystyle c}$${\ displaystyle a_ {i}}$

Tolóablakos modell

Számos cikk figyelembe veszi a "csúszó ablak" modellt is. Ebben a modellben az érdekes funkció az adatfolyam rögzített méretű ablakán keresztül történő számítás. A folyam előrehaladtával az ablak végén lévő elemek eltávolításra kerülnek, míg az adatfolyamból származó új elemek a helyükre kerülnek.

A fenti frekvenciaalapú problémák mellett néhány más típusú problémát is tanulmányoztak. Sok gráfprobléma megoldódik abban a beállításban, ahol a grafikon szomszédsági mátrixát vagy szomszédsági listáját valamilyen ismeretlen sorrendben közvetítik. Vannak olyan problémák is, amelyek nagymértékben függenek az adatfolyam sorrendjétől (azaz aszimmetrikus függvények), például a folyam inverzióinak számolása és a leghosszabban növekvő alsorozat megtalálása.

Értékelés

Az adatfolyamokon működő algoritmus teljesítményét három alapvető tényező határozza meg:

• Az algoritmus által a folyamon végrehajtott passzok száma.
• A rendelkezésre álló memória.
• Az algoritmus futási ideje.

Ezek az algoritmusok sok hasonlóságot mutatnak az online algoritmusokkal, mivel mindkettő megköveteli a döntést, mielőtt minden adat rendelkezésre áll, de nem azonosak. Az adatfolyam -algoritmusoknak csak korlátozott memóriája áll rendelkezésre, de képesek lehetnek elhalasztani a műveletet, amíg egy pontcsoport meg nem érkezik, míg az online algoritmusoknak lépéseket kell tenniük, amint minden pont megérkezik.

Ha az algoritmus közelítő algoritmus, akkor a válasz pontossága egy másik kulcsfontosságú tényező. A pontosságot gyakran közelítésként határozzák meg, ami azt jelenti, hogy az algoritmus kisebb hibát ér el, mint valószínűséggel . ${\ displaystyle (\ epsilon, \ delta)}$${\ displaystyle \ epsilon}$${\ displaystyle 1- \ delta}$

Alkalmazások

A streamelési algoritmusoknak számos alkalmazása van a hálózatépítésben, mint például az elefántáramlás hálózati kapcsolatainak figyelése , a különálló folyamok számának számítása, az áramlási méretek megoszlásának becslése stb. Alkalmazásaik vannak adatbázisokban is, például becsülik a csatlakozás méretét .

Néhány streaming probléma

Frekvencia pillanatok

A frekvenciahalmaz k -edik frekvenciamomentuma a következő . ${\ displaystyle \ mathbf {a}}$${\ displaystyle F_ {k} (\ mathbf {a}) = \ sum _ {i = 1}^{n} a_ {i}^{k}}$

Az első pillanat egyszerűen a frekvenciák összege (azaz a teljes szám). A második pillanat hasznos az adatok statisztikai tulajdonságainak, például a Gini variációs együttható kiszámításához . a leggyakrabban előforduló tételek gyakorisága. ${\ displaystyle F_ {1}}$${\ displaystyle F_ {2}}$${\ displaystyle F _ {\ infty}}$

Alon, Matias és Szegedy alapvető dolgozata a gyakorisági pillanatok becslésének problémájával foglalkozott.

Frekvenciamomentumok kiszámítása

A frekvenciamomentumok megkeresésének közvetlen megközelítése megköveteli a m _i regiszter fenntartását minden különálló a _i ∈ (1,2,3,4, ..., N ) elemhez , amely legalább a rend memóriáját igényli . De vannak helykorlátaink, és olyan algoritmust igényelünk, amely sokkal alacsonyabb memóriában számol. Ezt úgy érhetjük el, hogy közelítéseket használunk a pontos értékek helyett. Egy algoritmust, amely kiszámít egy ( ε, δ ) közelítése F _k , ahol F” _k a ( ε, δ ) - közelítő értéke az F _k . Ahol ε a közelítő paraméter, és δ a megbízhatósági paraméter. ${\ displaystyle \ Omega (N)}$

F ₀ kiszámítása (különálló elemek egy adatfolyamban)

FM-Sketch algoritmus

Flajolet és mtsai. bevezette a valószínűségi számítási módszert, amelyet Robert Morris dolgozata ihletett . Morris tanulmányában azt mondja, hogy ha a pontosság követelménye leesett, egy számláló n lehet helyettesíteni egy számláló log n tárolható a log log n bit. Flajolet és mtsai. továbbfejlesztve ezt a módszert egy h hash függvény használatával, amely feltételezi, hogy egyenletesen osztja el az elemet a hash térben ( L hosszúságú bináris karakterlánc ).

${\ Displaystyle h: [m] \ rightarrow [0,2 ^ {L} -1]}$

Jelölje a bit ( y, k ) az y bináris ábrázolásának k -edik bitjét

${\ displaystyle y = \ összeg _ {k \ geq 0} \ mathrm {bit} (y, k)*2^{k}}$

A Let a legkevésbé szignifikáns 1 bites pozíciót jelöli y _i bináris ábrázolásában, megfelelő konvencióval . ${\ displaystyle \ rho (y)}$${\ displaystyle \ rho (0)}$

${\ displaystyle \ rho (y) = {\ begin {case} \ mathrm {Min} (k: \ mathrm {bit} (y, k) == 1) & {\ text {if}} y> 0 \\ L & {\ text {if}} y = 0 \ end {esetekben}}}$

Legyen A az M hosszúságú adatfolyam sorozata, amelynek számosságát meg kell határozni. Legyen BITMAP [0 ... L - 1] a

hash tér, ahol a ρ ( kivonatolt értékek ) van rögzítve. Az alábbi algoritmus ezután meghatározza hozzávetőleges számossága A .

Procedure FM-Sketch:

    for i in 0 to L − 1 do
        BITMAP[i] := 0 
    end for
    for x in A: do
        Index := ρ(hash(x))
        if BITMAP[index] = 0 then
            BITMAP[index] := 1
        end if
    end for
    B := Position of left most 0 bit of BITMAP[] 
    return 2 ^ B

Ha egy adatfolyamban N különálló elem található.

• Mert akkor a BITMAP [ i ] minden bizonnyal 0${\ displaystyle i \ gg \ log (N)}$
• Mert akkor a BITMAP [ i ] minden bizonnyal 1${\ displaystyle i \ ll \ log (N)}$
• Az ezután BITMAP [ i ] egy peremén a 0 és 1-es${\ displaystyle i \ kb \ log (N)}$

K -minimális értékű algoritmus

Az előző algoritmus leírja Flajolet és Martin első kísérletét az F ₀ közelítésére az adatfolyamban. Algoritmusuk kiválaszt egy véletlenszerű hash függvényt, amely feltételezi, hogy egyenletesen osztja el a hash értékeket a hash térben.

Bar-Yossef és mtsai. bevezetett k-minimum értékű algoritmus az adatfolyamban lévő különböző elemek számának meghatározására. Ők használt egy hasonló hash függvény H , amelyek normalizálni lehet, hogy a [0,1], mint . De rögzítettek egy t korlátot a hash térben lévő értékek számára. A t értékét a sorrend feltételezi (azaz a kisebb közelítési érték ε több t-t igényel ). A KMV algoritmus csak a t -legkisebb hash -értékeket tartja a hash térben. Miután a patak összes m értéke megérkezett, kiszámításra kerül . Vagyis egy közel egységes hash-térben legalább t elemre számítanak, mint a .${\ Displaystyle h: [m] \ rightarrow [0,1]}$${\ displaystyle O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)}$${\ displaystyle \ upsilon = \ mathrm {Max} (h (a_ {i}))}$${\ displaystyle F '_ {0} = {\ dfrac {t} {\ upsilon}}}$${\ displaystyle O \ left ({\ dfrac {t} {F_ {0}}} \ right)}$

Procedure 2 K-Minimum Value

Initialize first t values of KMV 
for a in a1 to an do
    if h(a) < Max(KMV) then
        Remove Max(KMV) from KMV set
        Insert h(a) to KMV 
    end if
end for 
return t/Max(KMV)

A KMV komplexitás elemzése

A KMV algoritmus memóriabites térben valósítható meg . Mindegyik kivonatolási értékhez rendelt memóriabitek szükségesek . A sorrend hash értékei vannak . A hozzáférési idő csökkenthető, ha a t hash értékeket egy bináris fában tároljuk . Így az idő bonyolultsága lecsökken . ${\ displaystyle O \ left (\ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right) \ cdot \ log (m) \ right)}$${\ displaystyle O (\ log (m))}$${\ displaystyle O \ left ({\ dfrac {1} {\ varepsilon _ {2}}} \ right)}$${\ displaystyle O \ left (\ log \ left ({\ dfrac {1} {\ varepsilon}}} \ right) \ cdot \ log (m) \ right)}$

F _k számítása

Alon és mtsai. becsli az F _k -t az adott térben és időben kiszámítható véletlen változók meghatározásával. A véletlen változók várható értéke F _k hozzávetőleges értékét adja .

Tegyük fel, hogy az m sorozat hossza előre ismert. Ezután készítsen X véletlenszerű változót az alábbiak szerint:

• Jelölje egy _p lehet véletlenszerű tagja szekvencia egy index a p ,${\ displaystyle a_ {p} = l \ in (1,2,3, \ ldots, n)}$
• Let , képviseli az előfordulások számát az L belül a tagok a szekvencia A következő egy _p .${\ displaystyle r = | \ {q: q \ geq p, a_ {q} = l \} |}$
• Véletlen változó .${\ Displaystyle X = m (r ^ {k} - (R-1) ^ {k})}$

Tegyük fel, hogy S ₁ rendű és S ₂ rendű . Az algoritmus S ₂ véletlen változót vesz fel és adja ki a mediánt . Ahol Y _i X _ij átlaga, ahol 1 ≤ j ≤ S ₁ . ${\ Displaystyle O (n ^ {1-1 / k} / \ lambda ^ {2})}$${\ displaystyle O (\ log (1/\ varepsilon))}$${\ Displaystyle Y_ {1}, Y_ {2}, ..., Y_ {S2}}$${\ displaystyle Y}$

Most számítsa ki az E ( X ) véletlen változó elvárását .

${\ displaystyle {\ begin {array} {lll} E (X) & = & \ sum _ {i = 1}^{n} \ sum _ {i = 1}^{m_ {i}} (j^{ k}-(j-1)^{k}) \\ & = & {\ frac {m} {m}} [(1^{k}+(2^{k} -1^{k})+ \ ldots+(m_ {1}^{k}-(m_ {1} -1)^{k})) \\ && \;+\; (1^{k}+(2^{k} -1 ^{k})+\ ldots+(m_ {2}^{k}-(m_ {2} -1)^{k}))+\ ldots \\ && \;+\; (1^{k} +(2^{k} -1^{k}) +\ ldots +(m_ {n}^{k}-(m_ {n} -1)^{k}))] \\ & = & \ összeg _ {i = 1}^{n} m_ {i}^{k} = F_ {k} \ end {tömb}}}$

F _k bonyolultsága

A fentiekben tárgyalt F _k kiszámítási algoritmusból láthatjuk, hogy minden X véletlen változó tárolja a _p és r értékét . Tehát az X kiszámításához csak log ( n ) biteket kell fenntartanunk a _p tárolására és log ( n ) biteket az r tárolására . Az X véletlenszerű változó teljes száma a . ${\ displaystyle S_ {1}*S_ {2}}$

Ezért az algoritmus teljes térbonyolultsága nagyságrendű ${\ displaystyle O \ left ({\ dfrac {k \ log {1 \ over \ varepsilon}} {\ lambda ^{2}}} n ^{1- {1 \ over k}} \ bal (\ log n+\ napló m \ jobb) \ jobb)}$

Egyszerűbb módszer az F ₂ kiszámítására

Az előző algoritmus memóriabitek sorrendjében számol . Alon és mtsai. leegyszerűsítve ezt az algoritmust négy bölcs független független véletlen változó használatával, amelynek értékei leképezve . ${\ displaystyle F_ {2}}$${\ Displaystyle O ({\ sqrt {n}} (\ log m + \ log n))}$${\ displaystyle \ {-1,1 \}}$

Ez tovább csökkenti a komplexitást számítani , hogy${\ displaystyle F_ {2}}$${\ displaystyle O \ left ({\ dfrac {\ log {1 \ over \ varepsilon}} {\ lambda ^{2}}} \ left (\ log n+\ log m \ right) \ right)}$

Gyakori elemek

Az adatfolyam -modellben a gyakori elemekkel kapcsolatos probléma az, hogy olyan elemhalmazt ad ki, amely több mint a folyam bizonyos rögzített töredéke. Különleges eset a többségi probléma , amelynek során meg kell határozni, hogy bármely érték a folyam többségét alkotja -e vagy sem.

Formálisabban rögzítsen valamilyen pozitív c > 1 konstansot , legyen az áram hossza m , és f _i jelölje az i érték gyakoriságát a folyamban. A gyakori elemek probléma a kimeneti halmaz { i | f _i > m/c}.

Néhány figyelemre méltó algoritmus:

• Boyer – Moore többségi szavazati algoritmus
• Count-Min vázlat
• Vesztes számolás
• Többlépcsős Bloom szűrők
• Misra – Gries összefoglaló

Eseményérzékelés

Az adatfolyamokban az események észlelése gyakran a fent felsorolt ​​nehéz ütő algoritmus segítségével történik: a leggyakoribb tételeket és azok gyakoriságát ezen algoritmusok egyikével határozzák meg, majd az előző időponthoz képest a legnagyobb növekedést jelentik trendként. Ez a megközelítés finomítható exponenciálisan súlyozott mozgóátlagok és variancia használatával a normalizáláshoz.

Különálló elemek számolása

A folyamban lévő különböző elemek számának (néha F ₀ pillanatnak) számolása egy másik jól tanulmányozott probléma. Az első algoritmust Flajolet és Martin javasolta. 2010 -ben Daniel Kane , Jelani Nelson és David Woodruff aszimptotikusan optimális algoritmust talált erre a problémára. Ez használ O ( ε ² + log d ) térben, O (1) legrosszabb frissítés és jelentési szer, valamint az univerzális hash függvények, és egy R -wise független hash család, ahol r = Ω (log (1 / ε ) / log log (1/ ε )) .

Entrópia

A (empirikus) entrópiája frekvenciák készletéhez definiáljuk , ahol . ${\ displaystyle \ mathbf {a}}$${\ displaystyle F_ {k} (\ mathbf {a}) = \ sum _ {i = 1}^{n} {\ frac {a_ {i}} {m}} \ log {\ frac {a_ {i} } {m}}}$${\ Displaystyle m = \ sum _ {i = 1} ^ {n} a_ {i}}$

Online tanulás

Tanuljon meg egy modellt (pl. Osztályozó ) egyetlen passz segítségével egy edzéssorozaton.

• Funkció összevonása
• Sztochasztikus színátmenet

Alsó határok

Sok vizsgált adatfolyam -probléma esetében alacsonyabb határokat számítottak ki. Az alsó határok kiszámításának leggyakoribb technikája messze a kommunikáció bonyolultsága volt .

Lásd még

• Adatfolyam bányászat
• Adatfolyam csoportosítás
• Online algoritmus
• Adatfolyam feldolgozás
• Szekvenciális algoritmus

Megjegyzések

Hivatkozások

• Alon, Noga ; Matias, Yossi ; Szegedy, Mario (1999), "A frekvenciamomentumok közelítésének térbeli összetettsége", Journal of Computer and System Sciences , 58 (1): 137–147, doi : 10.1006/jcss.1997.1545 , ISSN  0022-0000. Először Alon, Noga néven jelent meg; Matias, Yossi; Szegedy, Mario (1996), "A frekvenciamomentumok közelítésének térbeli összetettsége", Proceedings of the 28.th  ACM Symposium on Theory of Computing (STOC 1996) , 20–29. O. , CiteSeerX 10.1.1.131.4984 , doi : 10.1145/ 237814.237823 , ISBN 978-0-89791-785-8, S2CID  1627911.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev ; Widom, Jennifer (2002), "Modellek és problémák az adatfolyam rendszerekben", Proceedings of the 21.st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF) , 1–16. O.  , CiteSeerX 10.1. 1.138.190 , doi : 10.1145/543613.543615 , ISBN 978-1581135077, S2CID  2071130.
• Gilbert, AC ; Kotidis, Y .; Muthukrishnan, S .; Strauss, MJ (2001), "Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries" (PDF) , Proceedings of the International Conference on Very Large Data Bases : 79–88.
• Kane, Daniel M .; Nelson, Jelani; Woodruff, David P. (2010). "Optimális algoritmus a különböző elemek problémájához". Az adatbázis-rendszerek elveiről szóló ACM SIGMOD-SIGACT-SIGART szimpózium huszonkilencedik alkalommal folytatott munkája . PODS '10. New York, NY, USA: ACM. 41–52. CiteSeerX  10.1.1.164.142 . doi : 10.1145/1807085.1807094 . ISBN 978-1-4503-0033-9. S2CID  10006932 ..
• Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003), "Egy egyszerű algoritmus a gyakori elemek megtalálására a folyamokban és zsákokban", ACM Transactions on Database Systems , 28 (1): 51–55, CiteSeerX  10.1.1.116.8530 , doi : 10.1145/762471.762473 , S2CID  952840.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, június; Zhang, Hui (2006), "Adatfolyam -algoritmusok a hálózati forgalom entrópiájának becsléséhez", A Számítógépes rendszerek méréséről és modellezéséről szóló közös nemzetközi konferencia (ACM SIGMETRICS 2006) (PDF) , o. 145, doi : 10.1145/1140277.1140295 , hdl : 1802/2537 , ISBN 978-1595933195, S2CID  240982.
• Xu, június (Jim) (2007), A hálózati adatfolyamok bemutatója (PDF).
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Learning Nested Concepts With Limited Storage", Proceeding IJCAI'91 Proceedings of the 12th international international conference on Artificial Intelligence - Volume 2, 777-782. Oldal, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA © 1991
• Morris, Robert (1978), "Nagyszámú esemény számolása kis regiszterekben", Communications of the ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID  36226357.