Algorytm przesyłania strumieniowego

W informatyce algorytmy przesyłania strumieniowego to algorytmy przetwarzania strumieni danych , w których dane wejściowe są przedstawiane jako sekwencja elementów i można je zbadać w zaledwie kilku przebiegach, zwykle tylko jednym . Algorytmy te są zaprojektowane do działania z ograniczoną pamięcią, zwykle logarytmiczną w rozmiarze strumienia i/lub w maksymalnej wartości w strumieniu, a także mogą mieć ograniczony czas przetwarzania na element.

W wyniku tych ograniczeń algorytmy przesyłania strumieniowego często dają przybliżone odpowiedzi na podstawie podsumowania lub „szkicu” strumienia danych.

Historia

Chociaż algorytmy przesyłania strumieniowego były już badane przez Munro i Patersona już w 1978 r., A także Philippe'a Flajoleta i G. Nigela Martina w latach 1982/83, dziedzina algorytmów przesyłania strumieniowego została po raz pierwszy sformalizowana i spopularyzowana w artykule z 1996 r. Noga Alon , Yossi Matiasa i Mario Szegedy'ego . Za ten artykuł autorzy otrzymali później nagrodę Gödla w 2005 r. „za ich fundamentalny wkład w algorytmy przesyłania strumieniowego”. Od tego czasu powstało wiele prac poświęconych algorytmom strumieniowego przesyłania danych, które obejmują zróżnicowane spektrum dziedzin informatyki, takich jak teoria, bazy danych, sieci i przetwarzanie języka naturalnego.

Algorytmy półstrumieniowe zostały wprowadzone w 2005 roku jako rozluźnienie algorytmów strumieniowych dla grafów, w których dozwolona przestrzeń jest liniowa pod względem liczby wierzchołków n , ale tylko logarytmiczna pod względem liczby krawędzi m . To rozluźnienie jest $interesujące$ problemy (takie jak łączność), które są nierozwiązywalne przestrzeni

modele

Model strumienia danych

W modelu strumienia danych część lub całość danych wejściowych jest reprezentowana jako skończona sekwencja liczb całkowitych (z jakiejś skończonej dziedziny), która generalnie nie jest dostępna dla dostępu swobodnego , ale zamiast tego dociera pojedynczo w „strumieniu”. Jeśli strumień ma długość n , a domena ma rozmiar m , algorytmy są na ogół ograniczone do używania przestrzeni, która jest logarytmiczna w m i n . Na ogół mogą wykonać tylko niewielką stałą liczbę przejść nad strumieniem, czasami tylko jeden .

Modele kołowrotów i kas fiskalnych

Znaczna część literatury poświęconej transmisji strumieniowej dotyczy obliczeń statystycznych rozkładów częstotliwości, które są zbyt duże, aby je przechowywać. Dla tej klasy problemów istnieje wektor (zainicjowany na zero $\ Displaystyle \ mathbf {a} = (a_ {1}, \ kropki, a_ {n})}$ vector ${\ displaystyle \ mathbf {0}}$ ), który ma aktualizacje prezentowane w strumieniu. Celem tych algorytmów jest obliczenie funkcji za $\ Displaystyle \ mathbf {a}}$$,$ niż potrzeba do dokładnego . Istnieją dwa popularne modele aktualizacji takich strumieni, zwane modelami „kasowymi” i „kołowrotkowymi”.

W modelu kasy fiskalnej każda aktualizacja ma postać $tak$ że dodatnią liczbę całkowitą do $}}$$styl wyświetlania c}$$i$ . Godnym $.$ przypadkiem szczególnym jest sytuacja, gdy tylko wstawienia jednostek)

$}$ ma postać , tak że jest zwiększana o (prawdopodobnie ujemną) liczbę całkowitą c ${\ displaystyle c}$$\ Displaystyle \ langle i, c \ rangle$ . W modelu „ścisłego kołowrotu” żadne $nie$ może być mniejsze od zera.

Model z przesuwanym oknem

Kilka artykułów dotyczy również modelu „przesuwanego okna”. W tym modelu interesującą funkcją są obliczenia w oknie o stałym rozmiarze w strumieniu. W miarę postępu transmisji elementy z końca okna są usuwane z rozważań, a ich miejsce zajmują nowe elementy ze strumienia.

Oprócz powyższych problemów opartych na częstotliwości, zbadano również inne rodzaje problemów. Wiele problemów z wykresami rozwiązuje się w ustawieniu, w którym macierz sąsiedztwa lub lista sąsiedztwa grafu jest przesyłana strumieniowo w nieznanej kolejności. Istnieją również problemy, które są bardzo zależne od kolejności strumienia (tj. funkcje asymetryczne), takie jak zliczanie liczby inwersji w strumieniu i znajdowanie najdłuższego rosnącego podciągu.

Ocena

Wydajność algorytmu działającego na strumieniach danych jest mierzona trzema podstawowymi czynnikami:

• Liczba przebiegów, które algorytm musi wykonać w strumieniu.
• Dostępna pamięć.
• Czas działania algorytmu.

Algorytmy te mają wiele podobieństw do algorytmów online , ponieważ oba wymagają podjęcia decyzji, zanim wszystkie dane będą dostępne, ale nie są identyczne. Algorytmy strumienia danych mają tylko ograniczoną dostępną pamięć, ale mogą być w stanie odroczyć działanie do czasu nadejścia grupy punktów, podczas gdy algorytmy online muszą podjąć działanie, gdy tylko nadejdzie każdy punkt.

Jeśli algorytm jest algorytmem aproksymacyjnym, to dokładność odpowiedzi jest kolejnym kluczowym czynnikiem. Dokładność jest często określana jako $1 -\delta}$$, co$ ​​algorytm osiąga błąd mniejszy niż 1 $Displaystyle$ .

Aplikacje

Algorytmy przesyłania strumieniowego mają kilka zastosowań w sieci , takich jak monitorowanie łączy sieciowych pod kątem przepływów słoni , zliczanie różnych przepływów, szacowanie rozkładu wielkości przepływów i tak dalej. Mają również zastosowania w bazach danych, takie jak szacowanie wielkości sprzężenia [ .

Niektóre problemy z przesyłaniem strumieniowym

Momenty częstotliwości

K - ten moment częstotliwości zbioru częstotliwości $za$ zdefiniowany jako $Displaystyle F_ {k} (\ mathbf {a} )=\suma _{i=1}^{n}a_{i}^{k}}$ .

Pierwszy moment jest $po$ prostu sumą częstotliwości (tj. całkowitą liczbą Drugi moment jest przydatny do $obliczania$ właściwości statystycznych danych, takich jak współczynnik . ${\ displaystyle F _ {\ infty}}$ jest definiowany jako częstotliwość najczęstszych elementów.

Przełomowy artykuł Alona, ​​Matiasa i Szegedy'ego dotyczył problemu oszacowania momentów częstotliwości.

Obliczanie momentów częstotliwości

Bezpośrednie podejście do znajdowania momentów częstotliwości wymaga zachowania rejestru m _i dla wszystkich różnych elementów a _i ∈ (1,2,3,4,..., N ) co wymaga przynajmniej pamięci rzędu ${\ styl wyświetlania \Omega (N)}$ . Mamy jednak ograniczenia przestrzenne i wymagamy algorytmu, który wykonuje obliczenia w dużo mniejszej pamięci. Można to osiągnąć, stosując przybliżenia zamiast dokładnych wartości. Algorytm obliczający przybliżenie ( ε,δ ) F _k , gdzie F' _k jest przybliżoną ( ε,δ ) wartością Fk _. Gdzie ε jest parametrem aproksymacji, a δ jest parametrem ufności.

₀ Obliczanie F (odrębne elementy w DataStream)

Główny artykuł: problem z liczeniem odrębnym

Algorytm FM-Sketch

Flajolet i in. wprowadził probabilistyczną metodę liczenia, zainspirowaną pracą Roberta Morrisa . Morris w swoim artykule mówi, że jeśli zrezygnuje się z wymogu dokładności, licznik n można zastąpić logarytmem licznika n , który można przechowywać w bitach log log n . Flajolet i in. in udoskonalił tę metodę, używając funkcji haszującej h , która zakłada równomierne rozmieszczenie elementu w przestrzeni mieszania (ciąg binarny o długości L ).

${\ Displaystyle h: [m] \ strzałka w prawo [0,2 ^ {L} -1]}$

Niech bit( y,k ) reprezentuje k-ty bit w binarnej reprezentacji y

${\ Displaystyle y = \ suma _ {k \ geq 0} \ operatorname {bit} (y, k) * 2 ^ {k}}$

Niech ${\ Displaystyle \ rho (y)}$ reprezentuje pozycję najmniej znaczącego 1-bitowego w binarnej reprezentacji y _ja z odpowiednią konwencją dla ${\ Displaystyle \ rho (0)}$ .

${\ Displaystyle \ rho (y) = {\ rozpocząć {przypadki} \ operatorname {Min } (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{przypadki}}}$

Niech A będzie ciągiem strumienia danych o długości M , którego liczność należy wyznaczyć. Niech BITMAPA [0... L − 1] będzie

przestrzeń mieszania, w której zapisywane są ρ ( wartości mieszania ). Poniższy algorytm określa następnie przybliżoną liczność A .

Procedura FM-Sketch: for i in 0 to L − 1 do BITMAP[i] := 0 end for x in A: do Index := ρ(hash(x)) jeżeli BITMAP[index] = 0 to BITMAP[index ] := 1 koniec jeśli koniec dla B := Pozycja najbardziej lewego 0 bitu BITMAP[] return 2 ^ B

w strumieniu danych jest N różnych elementów.

• Dla ${\ Displaystyle i \ gg \ log (N)}$ wtedy BITMAPA [ ja ] to z pewnością 0
• Dla ${\ Displaystyle i \ ll \ log (N)}$ wtedy BITMAPA [ ja ] to z pewnością 1
• Dla ${\ Displaystyle i \ około \ log (N)}$ wtedy BITMAPA [ ja ] to prążki zer i jedynek

K - algorytm wartości minimalnej

₀ Poprzedni algorytm opisuje pierwszą próbę przybliżenia F w strumieniu danych przez Flajoleta i Martina. Ich algorytm wybiera losową funkcję skrótu , która zakłada równomierny rozkład wartości skrótu w przestrzeni skrótów.

Bar-Yossef i in. we wprowadzonym algorytmie wartości k-minimum do wyznaczania liczby odrębnych elementów w strumieniu danych. Użyli podobnej funkcji skrótu h , którą można znormalizować do [0,1] jako ${\ Displaystyle h: [m] \ rightarrow [0,1]}$ . Ale ustalili limit t na liczbę wartości w przestrzeni skrótów. Przyjęto wartość t rzędu ${\ Displaystyle O \ lewo ({\ dfrac {1} {\ varepsilon _ {2}}} \ prawej)}$ (tj. mniejsza wartość przybliżenia ε wymaga więcej t ). Algorytm KMV przechowuje tylko t - najmniejsze wartości skrótu w przestrzeni skrótów. Po nadejściu wszystkich m wartości strumienia do obliczenia $\ Displaystyle \ upsilon = \ operatorname {Max} (h (a_ {i}))}$${\ Displaystyle F'_ {0} = {\ dfrac {t} {\ upsilon}}}$ . Oznacza to, że w zbliżonej do jednolitej przestrzeni skrótu spodziewają się, że co najmniej t elementów będzie mniejszych niż ${\ Displaystyle O \ lewo ({\ dfrac {t} {F_ {0}}} \ prawej )}$ .

Procedura 2 K-Minimalna wartość Zainicjuj pierwsze wartości t KMV dla a w a1 do an do if h(a) < Max(KMV) następnie Usuń Max(KMV) z zestawu KMV Wstaw h(a) do KMV end if end for return t/maks. (KMV)

Analiza złożoności KMV

Algorytm KMV można zaimplementować w ${\ Displaystyle O \ lewo (\ lewo ({\ dfrac {1} {\ varepsilon _ {2}}} \ prawej) \ cdot \log(m)\right)}$ miejsce na bity pamięci. Każda wartość skrótu wymaga miejsca rzędu bitów pamięci ${\ Displaystyle O (\ log (m))} .$ Istnieją wartości skrótu rzędu ${\ Displaystyle O \ lewo ({\ dfrac {1} {\ varepsilon _ {2}}} \ prawej)}$ . Czas dostępu można skrócić, przechowując t w drzewie binarnym. W ten sposób złożoność czasowa zostanie zredukowana do ${\ Displaystyle O \ lewo (\ log \ lewo ({\ dfrac {1} {\ varepsilon}} \ prawej) \ cdot \log(m)\right)}$ .

Obliczanie Fk _{_}

Alon i in. szacuje F _k , definiując zmienne losowe, które można obliczyć w danej przestrzeni i czasie. Oczekiwana wartość zmiennych losowych daje przybliżoną wartość F _k .

Załóżmy, że długość ciągu m jest znana z góry. Następnie skonstruuj zmienną losową X w następujący sposób:

• Wybierz p _\ być losowym członkiem sekwencji A z indeksem w p , $kropki ,n)}$${\ Displaystyle a_ {p} = l \ w (1,2,3,$
• Niech ${\ Displaystyle r = |\ {q: q \ geq p, a_ {q} = l \}|}$ reprezentuje liczbę wystąpień l w elementach sekwencji A następujących po _p .
• Zmienna losowa ${\ Displaystyle X = m (r ^ {k} - (r-1) ^ {k})}$ .

Załóżmy, że S ₁ jest rzędu ${\ Displaystyle O (n ^ {1-1/k} / \ lambda ^ {2})}$ i S ₂ jest rzędu ${\ Displaystyle O (\ log (1 / \ varepsilon))}$ . Algorytm przyjmuje S ₂ zmienną losową ${\ Displaystyle Y_ {1}, Y_ {2}, ..., Y_ {S2}}$ i wyprowadza medianę ${\ Displaystyle Y}$ . Gdzie Y _i jest średnią z X _ij gdzie 1 ≤ j ≤ S ₁ .

Teraz oblicz wartość oczekiwaną zmiennej losowej E ( X ) .

${\ Displaystyle {\ rozpocząć {tablica} {lll} E (X) & = & \ suma _ {i = 1} ^ {n} \ suma _ {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}))]\\&=&\suma _{i=1}^{n}m_{i}^{k}=F_{k}\end{tablica}}}$

Złożoność Fk _{_}

p _Z algorytmu obliczania F _k omówionego powyżej widzimy, że każda zmienna losowa X przechowuje wartość i r . Tak więc, aby obliczyć X p _, musimy zachować tylko log( n ) bitów do przechowywania i log( n ) bitów do przechowywania r . Całkowita liczba zmiennych losowych X będzie wynosić ${\ Displaystyle S_ {1} * S_ {2}}$ .

Stąd całkowita złożoność przestrzenna algorytmu jest rzędu ${\ Displaystyle O \ lewo ({\ dfrac {k \ log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}$

Prostsze podejście do obliczania F ₂

Poprzedni algorytm oblicza $} } (\ log m$$\ log n) )}$ + bitów pamięci. Alon i in. w uproszczeniu ten algorytm przy użyciu czterokierunkowej niezależnej zmiennej losowej z wartościami odwzorowanymi na . ${\ Displaystyle \ {-1,1 \}}$ .

To dodatkowo zmniejsza złożoność obliczania $do$ O $1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}$$\ Displaystyle O \ lewo ({\ dfrac {\$

Częste elementy

W modelu strumienia danych problem częstych elementów polega na wyprowadzaniu zestawu elementów, które stanowią więcej niż pewien stały ułamek strumienia. Szczególnym przypadkiem jest problem większości , który polega na określeniu, czy jakakolwiek wartość stanowi większość strumienia.

Bardziej formalnie, ustalmy pewną dodatnią stałą c > 1, niech długość strumienia będzie m i niech _fi oznacza częstotliwość wartości i w strumieniu. Problemem częstych elementów jest wyprowadzenie zbioru { i | fa _ja > m/c }.

Niektóre godne uwagi algorytmy to:

• Algorytm głosowania większościowego Boyera-Moore'a
• Szkic Count-Min
• Stratne liczenie
• Wielostopniowe filtry Blooma
• Algorytm ciężkich uderzeń Misry-Griesa
• Podsumowanie Misry – Griesa

Wykrywanie zdarzeń

Wykrywanie zdarzeń w strumieniach danych jest często wykonywane przy użyciu algorytmu o dużym natężeniu ruchu, jak opisano powyżej: najczęstsze elementy i ich częstotliwość są określane za pomocą jednego z tych algorytmów, następnie największy wzrost w stosunku do poprzedniego punktu czasowego jest zgłaszany jako trend. Podejście to można udoskonalić, stosując wykładniczo ważone średnie kroczące i wariancję do normalizacji.

Liczenie różnych elementów

Zliczanie liczby odrębnych elementów w strumieniu (czasami nazywanym momentem F ₀ ) to kolejny dobrze zbadany problem. Pierwszy algorytm zaproponowali Flajolet i Martin. W 2010 roku Daniel Kane , Jelani Nelson i David Woodruff znaleźli asymptotycznie optymalny algorytm dla tego problemu. Wykorzystuje O ( ε ² + log d ) , z czasem aktualizacji i raportowania w najgorszym przypadku O (1) , a także uniwersalne funkcje haszujące i r -mądra niezależna rodzina skrótów, gdzie r = Ω(log(1/ ε ) / log log(1/ ε )) .

Entropia

$)$ częstotliwości jest zdefiniowana jako $F_ {k} ( \mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}} ,$ gdzie $\ Displaystyle m = \ suma _ {i = 1} ^ {n} a_ {i}}$ .

Nauka online

Główny artykuł: Uczenie maszynowe online

Naucz się modelu (np. klasyfikatora ) przez pojedyncze przejście przez zbiór uczący.

• Haszowanie funkcji
• Stochastyczny spadek gradientu

Dolne granice

Dolne granice zostały obliczone dla wielu problemów związanych ze strumieniowaniem danych, które zostały zbadane. Zdecydowanie najpowszechniejszą techniką obliczania tych dolnych granic jest wykorzystywanie złożoności komunikacji .

Zobacz też

• Eksploracja strumienia danych
• Klastrowanie strumieni danych
• Algorytm online
• Przetwarzanie strumieniowe
• Algorytm sekwencyjny

Notatki

•   Alon, Noga ; Matias, Yossi ; Szegedy, Mario (1999), „Złożoność przestrzenna przybliżania momentów częstotliwości”, Journal of Computer and System Sciences , 58 (1): 137–147, doi : 10.1006/jcss.1997.1545 , ISSN 0022-0000 . Po raz pierwszy opublikowany jako Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), „Złożoność przestrzenna przybliżania momentów częstotliwości”, Proceedings of 28th ACM Symposium on Theory of Computing (STOC 1996) , s. 20–29,     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), „Modele i problemy w systemach strumienia danych”, Proceedings of 21. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF) , s. 1–16, 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 Summary 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). „Optymalny algorytm dla problemu różnych elementów”. Materiały z dwudziestego dziewiątego sympozjum ACM SIGMOD-SIGACT-SIGART na temat zasad systemów baz danych . PODS '10. Nowy Jork, NY, USA: ACM. s. 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), „Prosty algorytm znajdowania częstych elementów w strumieniach i workach”, 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, czerwiec; Zhang, Hui (2006), „Algorytmy strumieniowego przesyłania danych do szacowania entropii ruchu sieciowego”, Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) (PDF) , s. 145, doi : 10.1145/1140277.1140295 , hdl : 1802/2537 , ISBN 978-1595933195 , S2CID 240982 .
• Xu, Jun (Jim) (2007), Samouczek dotyczący strumieniowego przesyłania danych w sieci (PDF) .
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., „Learning Nested Concepts with Limited Storage”, Proceeding IJCAI'91 Proceedings of the 12. międzynarodowa wspólna konferencja na temat sztucznej inteligencji - tom 2, strony 777-782, Morgan Kaufmann Publishers Inc. San Francisco, Kalifornia, USA © 1991
•   Morris, Robert (1978), „Zliczanie dużej liczby zdarzeń w małych rejestrach”, Komunikaty ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID 36226357 .