Stream algoritmus

A streaming algoritmus egy adatsor feldolgozására szolgáló algoritmus egy vagy kis számú lépésben.

Az adatfolyam-algoritmusok olyan problémákat oldanak meg, amelyekben az adatok szekvenciálisan és nagy mennyiségben érkeznek. Példa erre a hálózati forgalom elemzése az útválasztó oldalán . Az ilyen problémák természetes korlátozásokat írnak elő a rendelkezésre álló memóriára (sokkal kisebb, mint a bemeneti adatok mérete) és a feldolgozási időre a streaming algoritmusok sorozatának minden elemére vonatkozóan. Az adatfeldolgozás gyakran csak egy menetben lehetséges.

Az idő és a memória szigorú korlátozása gyakran lehetetlenné teszi a vizsgált probléma pontos megoldását. Az áramlási algoritmusok általában valószínűségiek, és közelítést adnak a pontos válaszhoz.

Történelem

Bár az 1980-as évek első felében foglalkoztak ilyen algoritmusokkal [1] [2] , a streaming algoritmus fogalmát először Alon , Matias ( eng. Yossi Matias ) és Szegedi ( eng. Mario ) munkáiban formalizálták. Szegedy ) 1996 -ban [3] . 2005-ben a szerzőket Gödel-díjjal jutalmazták a streaming algoritmusokhoz való alapvető hozzájárulásukért .

2005-ben bevezették a félig streaming algoritmus fogalmát [ 4 ] , mint olyan algoritmusokat, amelyek a bejövő adatfolyamot konstans vagy logaritmikus formában dolgozzák fel.[ pontosítás ] passzok száma.

Modell

Az adatfolyam-adatmodellben figyelembe veszik, hogy a feldolgozandó bemeneti adatok egy része vagy egésze nem áll rendelkezésre véletlenszerű hozzáféréshez : a bemeneti adatok szekvenciálisan és folyamatosan érkeznek egy vagy több adatfolyamban. Az adatfolyamok rendezett pontsorozattal ("frissítésekkel") ábrázolhatók, amelyek sorrendben és csak egyszer vagy korlátozott számban érhetők el.

Sok szálfűző publikáció a hatékony tároláshoz túl nagy adateloszlásra vonatkozó számítógépes statisztika feladatát tekinti.[ adja meg ] . Ennél a problémaosztálynál feltételezzük, hogy a vektornak (nulla inicializált ) van bizonyos számú "frissítés" az adatfolyamban. Az ilyen algoritmusok célja olyan függvények kiszámítása, amelyek lényegesen kevesebb helyet igényelnek, mint amennyi a vektor teljes reprezentációjához szükséges . Két általános modell létezik az ilyen adatok frissítésére: „ pénztárgép ” és „forgókapu” ( eng . turnstile ). $\mathbf {a} =(a_{1},\pontok ,a_{n})$ $\mathbf {0}$ ${\mathbf {a}}$ ${\mathbf {a}}$

A "cash" modellben minden "frissítés" a formában van ábrázolva, és a vektor úgy módosul, hogy valamely pozitív egész számmal növekszik . Egy speciális eset az eset (csak egy egység beillesztése megengedett). $\langle i,c\rangle$ $a_{i}$ $c$ $c=1$

A "forgókerekes" modellben minden "frissítés" formában van ábrázolva, és a vektor úgy módosul, hogy valamely pozitív vagy negatív egész számmal növekszik . Egy szigorú modellben az adott időpontban nem lehet negatív. $\langle i,c\rangle$ $a_{i}$ $c$ $a_{i}$

Számos forrásban a „slide-window” modellt is figyelembe veszik. Ebben a modellben az érdeklődési függvényt egy korlátozott dimenziójú ablakon számítják ki az adatfolyam adataiból, az ablak végén lévő elemeket nem veszik figyelembe, amíg az adatfolyamból származó új adatok át nem veszik a helyüket.

Ezek az algoritmusok nemcsak az adatok gyakorisági jellemzőivel kapcsolatos kérdéseket veszik figyelembe, hanem számos más kérdést is. A gráfokkal kapcsolatos számos probléma megoldható olyan feltételek mellett, hogy a gráf szomszédsági mátrixát valamilyen ismeretlen sorrendben előre betöltjük. Néha éppen ellenkezőleg, meg kell oldani az adatok sorrendjének becslésének problémáját, például meg kell számolni az inverz értékek számát az adatfolyamban, és meg kell találni a legnagyobb növekvő sorozatot.

Algoritmusok összehasonlítása

A streaming algoritmusok főbb jellemzői:

az algoritmus adat feletti megengedett áthaladásának száma;
elérhető memória;
a feldolgozás ideje[ adja meg ] .

Ezeknek az algoritmusoknak sok közös vonásuk van az online algoritmusokkal , mivel az algoritmusnak döntést kell hoznia, mielőtt az összes adat elérhető lenne, de vannak különbségek. Az in-line algoritmusok különösen képesek késleltetni a döntések meghozatalát addig, amíg egy adatsorozat pontcsoportja meg nem érkezik, míg az online algoritmusoknak döntéseket kell hozniuk a sorozat minden új pontjának megérkezésekor.

Ha az algoritmus hozzávetőleges, akkor a válasz pontossága egy másik mutató. Egy algoritmus pontosságát gyakran értékként adják meg , ami azt jelenti, hogy az algoritmus kevesebb hibát fog elérni , -os valószínűséggel . $(\epsilon ,\delta )$ $\epsilon$ $1-\delta$

Alkalmazás

Az adatfolyam-algoritmusok nagy jelentőséggel bírnak a számítógépes hálózatok felügyeletének és menedzselésének feladataiban , így például eszközükkel gyorsan megelőzhető a túlcsordulás (óriásfolyamok követése , túlcsordulások számának és várható időtartamának becslése) [ ] Emellett adatfolyam-algoritmusok használhatók adatbázisokban, például a méret becslésére egy tábla-illesztési művelet után .

Példák adatfolyam-algoritmusok által megoldott problémákra

Problémák a frekvenciaelosztással

$k$ A vektor th frekvencianyomatéka a következőképpen van definiálva . ${\mathbf {a}}$ ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k))$

Az első momentum a frekvenciák egyszerű összege (azaz a teljes szám). A második pont az adatok statisztikai paramétereinek, például a Gini-együttható kiszámításához hasznos . a leggyakrabban előforduló elem gyakoriságaként határozzuk meg. $F_{1}$ $F_{2}$ ${\displaystyle F_{\infty ))$

A frekvencianyomatékok becslésének kérdéseit is tanulmányozzuk.

Nehéz elemek keresése

A feladat az adatfolyam leggyakrabban előforduló elemének megtalálása. Itt a következő algoritmusok érvényesek:

Boyer-Moore többségi szavazási algoritmus
Karp-Papadimitriou-Schenker algoritmus ,
Count-Min vázlat ,
ragadós mintavételi algoritmus , _
számláló algoritmus
"sample and hold" ( eng. sample and hold ),
réteges virágszűrő ,
counting "sketch" ( eng. Count-sketch ),
mintavétel "vázlat" eng. vázlatos mintavételezés ,

Trendkövetés

Az adatfolyamban a trendelés általában a következő sorrendben történik: a leggyakrabban előforduló elemeket és azok gyakoriságát a fenti algoritmusok valamelyike alapján határozzuk meg[ pontosítás ] <--algoritmusok nehéz elemek megtalálására? és ha ezt a szakaszt lejjebb helyezzük?-->, akkor trendként az előző időponthoz viszonyított legnagyobb növekedést jegyezzük meg. Ehhez exponenciális mozgóátlagot és különféle normalizálásokat használnak [6] . O(ε² + log d) szóközt és O(1) legrosszabb eset frissítést használ egy univerzális hash függvényhez az r-smart független hash függvények családjából, ahol r = Ω(log(1/ε)/ log log(1) / ε))[ adja meg ] .

Entrópia

Egy empirikus entrópiabecslést egy frekvenciahalmazra a következőképpen definiálunk: , ahol [7] . ${\mathbf {a}}$ $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))$

Gépi tanulás

Az online gépi tanulás fő feladata egy modell (például egy osztályozó) betanítása egy menetben a képzési készleten keresztül; prediktív kivonatolást és gradienst használnak

Az egyedi elemek számának számolása

Az adatfolyamban lévő egyedi elemek számának megszámlálása (pillanat ) egy másik dolog $F_{0}$ [ pontosítás ] egy jól tanulmányozott probléma. Az első algoritmust Flajolet és Martin javasolta [2] . 2010-ben találtak egy aszimptotikusan optimális algoritmust [8] .

Jegyzetek

↑ Munro és Paterson (1980 )
↑ 1 2 Flajolet és Martin (1985 )
↑ Alon, Matias és Szegedy (1996 )
↑ Feigenbaum Joan , Kannan Sampath , McGregor Andrew , Suri Siddharth , Zhang Jian. Gráfproblémákról félig streaming modellben // Elméleti számítástechnika. - 2005. - December ( 348. évf . , 2-3. sz. ). - S. 207-216 . — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2005.09.013 .
↑ J. Xu Oktatóanyag a hálózati adatfolyamról
↑ Schubert Erich , Weiler Michael , Kriegel Hans-Peter. SigniTrend // A 20. ACM SIGKDD tudásfelfedezés és adatbányászat című nemzetközi konferencia anyaga - KDD '14. - 2014. - ISBN 9781450329569 . - doi : 10.1145/2623330.2623740 .
↑ Az entrópiabecsléseket McGregor és munkatársai, Do Ba és mtsai, Lall és mtsai, Chakrabarti et al.[ pontosítás ]
↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), "Optimális algoritmus a különálló elemek problémájához", Proceedings of the huszonkilencedik ACM SIGMOD-SIGACT-SIGART szimpózium az adatbázisrendszerek alapelveiről, PODS '10, New York, NY, USA: ACM, pp. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 .

Irodalom

Alon, Noga ; Matias, Yossi & Szegedy, Mario (1999), A frekvenciamomentumok közelítésének térkomplexitása , Journal of Computer and System Sciences 58. kötet (1): 137–147, ISSN 0022-0000 , DOI 10.1006/jcss.1997.1545 . Először Alon, Noga néven jelent meg; Matias, Yossi & Szegedy, Mario (1996), A frekvenciamomentumok közelítésének térkomplexitása , Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996) , p. 20–29., ISBN 0-89791-785-5 , DOI 10.1145/237814.237823 .
Babcock, Brian; Babu, Shivnath; Datar, Mayur és Motwani , Rajeev (2002), Models and issues in data stream systems , Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) , p. 1–16, doi : 10.1145/543613.543615 , < http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf > .
Gilbert, AC ; Kotidis, Y.; Muthukrishnan, S. & Strauss, MJ (2001), Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries , Proceedings of the International Conference on Very Large Data Bases : 79–88 , < http://www.vldb. org/conf/2001/P079.pdf > .
Kane, Daniel M.; Nelson, Jelani & Woodruff, David P. (2010), Optimal algoritmus for the different elements problem , PODS '10, New York, NY, USA: ACM, p. 41-52, ISBN 978-1-4503-0033-9 , DOI 10.1145/1807085.1807094 .
Karp, R. M .; Papadimitriou, CH & Shenker, S. (2003), Egy egyszerű algoritmus gyakori elemek megtalálására folyamokban és zsákokban , ACM Transactions on Database Systems 28. kötet (1): 51–55 , DOI 10.1145/762471.762473 .
Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori & Xu, Jun (2006), Adatfolyam-algoritmusok a hálózati forgalom entrópiájának becsléséhez , Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) , doi : 10.1145/ 29140207140417140711402071 . /ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf > (holt link) .
Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming , < http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf > .

Linkek

Princeton előadási jegyzetek
Streaming Algorithms for Geometric Problems , Piotr Indyk , MIT
Dagstuhl műhely a szublineáris algoritmusokról
IIT Kanpur Workshop az adatfolyamról
A streaming nyitott problémáinak listája (összeállította: Andrew McGregor ) az IITK Workshop on Algorithms for Data Streams, 2006-ban folytatott megbeszéléséből.
StreamIt – MIT CSAIL programozási nyelv és fordítási infrastruktúra (nem elérhető hivatkozás)
IBM Spade – adatfolyam-feldolgozási alkalmazás deklaratív motorja
IBM InfoSphere Streams

tankönyvek

Adatfolyam-algoritmusok és alkalmazások , S. Muthu Muthukrishnan
Stanford STREAM projekt felmérés
Bloom-szűrők hálózati alkalmazásai , Broder és Mitzenmacher
Xu SIGMETRICS 2007 oktatóanyaga
Andrew McGregor és S. Muthu Muthukrishnan előadási jegyzetei a 2009 - es barbadosi Data Streams tanfolyamról

Tanfolyamok