Algorytmy strumienia danych „Dziel i rządź”

Jakie istnieją przydatne algorytmy, które działają na ogromnych strumieniach danych, a także ich wyniki są dość małe i można obliczyć wynik dla mieszanki dwóch strumieni, łącząc w jakiś sposób ich wyniki?

Mogę wymienić kilka:

• Oczywiste rzeczy, takie jak suma, min, maksimum, liczba, najwyższe K itp.
• Przybliżone tak zwane „oparte na szkicach” algorytmy strumieniowe dla histogramów, zliczania różnych elementów lub obliczania kwantyli

Jacy są inni

(Jestem zainteresowany, ponieważ piszę projekt hobby do monitorowania systemów rozproszonych, których użyteczność jest bezpośrednio określona przez przydatność takich algorytmów)

Guha i in. '03 podaje algorytm aproksymacji dla k-medianowego grupowania w modelu strumieniowania. Ich algorytm dzieli dane na części rozłączne, znajduje centra O (k) dla każdego elementu rozłącznego, a następnie łączy wyniki, aby uzyskać k centrów. Wydaje się, że jest to rodzaj algorytmu, którego szukasz.

Papieru przez Bagchi, Chaudhary, Eppstein i Goodrich rozwiązuje wiele strumieniowych problemy geometryczne, stosując podstawową podprogram obliczania -nets i ε -approximations z odpowiednio wybranych miejscach zasięgu. Ten podprogram korzysta z dodatkowej konstrukcji tych obiektów przez opracowanie hierarchiczny system ich (obliczyć w którym wirtualne i p strumień poziom agregacji bloki w wirtualnym ( I - 1 ) $\varepsilon$$\varepsilon$$i^{\text{th}}$$(i-1)^{\text{th}}$-level strumień, a poziom 0 to oryginalny strumień). Jest to zasadniczo oddolne przedstawienie strategii dziel i zwyciężaj. z aktualizacjami wzdłuż „krawędzi” drzewa rekurencyjnego. Pod względem struktury jest bardzo podobny do artykułu Guha i in. Wspomnianego przez Lwa.

Znalazłem artykuł ( „Dystrybucja obliczeń strumienia danych zależnych od częstotliwości” ), który mówi, że każda funkcja rozkładu częstotliwości strumienia jest możliwa do scalenia (chociaż nie daje wyraźnej i wydajnej konstrukcji dla operacji scalania). Dowód wydaje się być bardzo interesujący i dotyczy teorii pierścieni. Musisz przeczytać poprzedni artykuł tego samego autora ( „Dolne granice estymacji częstotliwości strumieni danych” ), którego główny wynik został wykorzystany jako podstawa tego.

To przypomina mi Trzecie Twierdzenie o Homomorfizmie ...

Badania nad ciągłymi językami zapytań strumieniowych mogą dostarczyć pewnych informacji. Jednym z takich języków jest CQL , który, jak sądzę, jest adoptowany przez Oracle. Języki umożliwiają obliczanie funkcji na przesuwnych oknach strumienia (w tym okien o rozmiarze 1). Tego praca licencjacka zapewnia niedawny przegląd języka, w tym niektóre przykłady. Ten artykuł zawiera przegląd niektórych języków przetwarzania strumieniowego, które powinny być przydatne do znajdowania linków do innych powiązanych badań.

Wiem, że to nie odpowiada bezpośrednio na twoje pytanie, ale powinno dać ci kontakt z badaniami przeprowadzonymi przez osoby odchodzące z tego samego punktu początkowego.

To pytanie wydaje mi się trochę okrągłe. Jeśli problem ma właściwość, którą chcesz, istnieje algorytm oparty na szkicowaniu i scalaniu. Jak wspomniano powyżej, istnieją prace nad klastrowaniem, przybliżeniami i zestawami rdzeni, które to zapewniają. Ponadto większość algorytmów przesyłania strumieniowego umożliwia łączenie strumieni po prostu (koncepcyjnie) łącząc jeden strumień z drugim.

Nie jestem też pewien, czy algorytmy przesyłania strumieniowego Top-k są scalalne - ale mogę się mylić.

Przepraszam, że o tym nekromantuję, ale pomyślałem, że możesz przyjrzeć się pracy nad rozproszonym ciągłym monitorowaniem strumieni, gdzie otrzymujesz kilka strumieni, a celem jest monitorowanie niektórych zbiorczych statystyk w centralnym miejscu monitorowania przy minimalizacji komunikacji. Model wydaje mi się ściśle związany z twoją motywacją. Spójrz na odniesienia w książce Muthu . Jeden papier to .

Artykuł Ganguly jest również bardzo interesujący.