Stream-algoritmi

Suoratoistoalgoritmi on algoritmi datasarjan käsittelemiseksi yhdellä tai pienellä määrällä kulkua .

Stream-algoritmit ratkaisevat ongelmia, joissa dataa saapuu peräkkäin ja suuria määriä. Esimerkki on verkkoliikenteen analyysi reitittimen puolella . Tällaiset ongelmat asettavat luonnollisia rajoituksia käytettävissä olevalle muistille (paljon vähemmän kuin syöttödatan koko) ja prosessointiaikaan kullekin sekvenssin elementille suoratoistoalgoritmeissa. Usein tietojen käsittely on mahdollista vain yhdellä kertaa.

Tiukat aika- ja muistirajoitukset tekevät usein mahdottomaksi ratkaista tutkittavaa ongelmaa tarkasti. Virtausalgoritmit ovat yleensä todennäköisyyspohjaisia ja antavat likiarvon tarkalle vastaukselle.

Historia

Vaikka tällaisia algoritmeja tarkasteltiin 1980-luvun ensimmäisen puoliskon teoksissa [1] [2] , suoratoistoalgoritmin käsite virallistettiin ensin Alonin , Matiasin ( eng. Yossi Matias ) ja Szegedin ( eng. Mario ) teoksissa. Szegedy ) vuonna 1996 [3] . Vuonna 2005 kirjoittajat palkittiin Gödel-palkinnolla heidän perustavanlaatuisesta panoksestaan suoratoistoalgoritmeihin .

Vuonna 2005 otettiin käyttöön puolisuoratoistoalgoritmin käsite [ 4 ] algoritmeina, jotka käsittelevät saapuvan virran vakiona tai logaritmisena.[ selventää ] passien lukumäärä.

Malli

Virtatietomallissa katsotaan, että osa tai kaikki prosessoitavan syöttödatan joukko ei ole käytettävissä satunnaiskäyttöä varten : syöttödata saapuu peräkkäin ja jatkuvasti yhdessä tai useammassa virrassa. Tietovirrat voidaan esittää järjestetyllä pistejonolla ("päivitykset"), joihin pääsee järjestyksessä ja vain kerran tai rajoitetun määrän kertoja.

Monet ketjutusjulkaisut pitävät tietokonetilastojen tehtävänä tietojen jakelussa, joka on liian suuri tehokkaaseen varastointiin.[ määritä ] . Tämän luokan ongelmia varten oletetaan, että vektorissa (nolla-alustettu ) on säikeessä jonkin verran "päivityksiä". Tällaisten algoritmien tavoitteena on laskea funktioita, jotka käyttävät huomattavasti vähemmän tilaa kuin vaatisi vektorin täydellisen esityksen . Tällaisten tietojen päivittämiseen on olemassa kaksi yleistä mallia: " kassakone " ja "kääntöportti" ( eng . turnstile ). $\mathbf {a} =(a_{1},\pisteet ,a_{n})$ $\mathbf {0}$ ${\mathbf {a}}$ ${\mathbf {a}}$

"Cash"-mallissa jokainen "päivitys" esitetään muodossa ja vektoria muokataan siten, että se kasvaa jollain positiivisella kokonaisluvulla . Erikoistapaus on tapaus (vain yksi yksikkö saa lisätä). $\langle i,c\rangle$ $a_{i}$ $c$ $c=1$

"Kääntöportti"-mallissa jokainen "päivitys" esitetään muodossa ja vektoria muokataan siten, että se kasvaa jollain positiivisella tai negatiivisella kokonaisluvulla . Tiukassa mallissa millään hetkellä ei voi olla negatiivinen. $\langle i,c\rangle$ $a_{i}$ $c$ $a_{i}$

Useissa lähteissä "slide-window" -mallia tarkastellaan lisäksi. Tässä mallissa kiinnostava funktio lasketaan rajoitetun ulottuvuuden ikkunan yli virtatiedoista, elementtejä ikkunan lopusta ei oteta huomioon ennen kuin uusi data virrasta tulee tilalle.

Nämä algoritmit eivät huomioi vain datan taajuusominaisuuksiin liittyviä kysymyksiä, vaan myös monia muita. Monet graafien ongelmat ratkaistaan sillä ehdolla, että graafin vierekkäisyysmatriisi ladataan etukäteen jossain tuntemattomassa järjestyksessä. Joskus päinvastoin on tarpeen ratkaista tietojen järjestyksen arvioinnin ongelma, esimerkiksi laskea käänteisten arvojen lukumäärä virrassa ja löytää suurin kasvava sekvenssi.

Algoritmien vertailu

Suoratoistoalgoritmien pääominaisuudet:

algoritmin sallittujen kulkujen lukumäärä datan yli;
käytettävissä oleva muisti;
käsittelyaika[ määritä ] .

Näillä algoritmeilla on paljon yhteistä online-algoritmien kanssa, koska algoritmin on tehtävä päätös ennen kuin kaikki tiedot ovat saatavilla, mutta eroja on. Erityisesti in-line-algoritmeilla on kyky viivyttää päätösten tekemistä, kunnes datasekvenssin pisteiden ryhmä saapuu, kun taas online-algoritmien on tehtävä päätökset sekvenssin jokaisen uuden pisteen saapuessa.

Jos algoritmi on likimääräinen, niin vastauksen tarkkuus on toinen indikaattori. Algoritmin tarkkuus esitetään usein arvona , mikä tarkoittaa, että algoritmi saavuttaa vähemmän virhettä todennäköisyydellä . $(\epsilon ,\delta )$ $\epsilon$ $1-\delta$

Sovellus

Virtausalgoritmeilla on suuri merkitys esimerkiksi tietokoneverkkojen valvonta- ja hallintatehtävissä , sillä niiden avulla voidaan nopeasti estää ylivuodot (jälkivirtojen seuranta , lukumäärän ja odotettavissa olevan keston arvioiminen) [ ] Myös suoratoistoalgoritmeja voidaan käyttää tietokannoissa, esimerkiksi arvioimaan kokoa taulukon liitosoperaation jälkeen .

Esimerkkejä suoratoistoalgoritmien ratkaisemista ongelmista

Ongelmia taajuusjakaumassa

$k$ Taajuushetki vektorissa on määritelty . ${\mathbf {a}}$ ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k))$

Ensimmäinen hetki on taajuuksien yksinkertainen summa (eli kokonaisluku). Toinen kohta on hyödyllinen laskettaessa datan tilastollisia parametreja, kuten Gini-kerrointa . määritellään useimmin esiintyvän elementin taajuudeksi. $F_{1}$ $F_{2}$ ${\displaystyle F_{\infty ))$

Myös taajuusmomenttien arvioinnin kysymyksiä tutkitaan.

Etsi raskaita elementtejä

Tehtävänä on löytää useimmin esiintyvä elementti tietovirrasta. Tässä pätevät seuraavat algoritmit:

Boyer-Mooren enemmistöäänestysalgoritmi
Karp-Papadimitriou-Schenker-algoritmi ,
Count-Min luonnos ,
tahmea näytteenottoalgoritmi , _ _
algoritmi _
"sample and hold" ( eng. sample and hold ),
kerroksellinen kukintasuodatin ,
counting "sketch" ( eng. Count-sketch ),
näytteenotto perustuu "outline" eng. luonnosohjattu näytteenotto ,

Trendiseuranta

Trendit tietovirrassa tehdään yleensä seuraavassa järjestyksessä: yleisimmät elementit ja niiden taajuudet määritetään jonkin yllä olevista algoritmeista[ selventää ] <--algoritmit raskaiden elementtien löytämiseen? ja jos tämä osio siirretään alemmas?-->, ja sitten suurin nousu edelliseen ajankohtaan verrattuna on trendi. Tätä varten käytetään eksponentiaalista liukuvaa keskiarvoa ja erilaisia normalisointeja [6] . Se käyttää O(ε² + log d)-avaruutta ja O(1) pahimman tapauksen päivitystä yleiselle hash-funktiolle r-smart-riippumattomien tiivistefunktioiden perheestä, jossa r = Ω(log(1/ε)/log log(1) / ε))[ määritä ] .

Entropia

Empiirinen entropiaestimaatti taajuuksien joukolle määritellään , jossa [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))$

Koneoppiminen

Verkkokoneoppimisen päätehtävänä on kouluttaa malli (esimerkiksi luokitin) yhdellä kertaa koulutussarjan läpi; ennustavaa tiivistystä ja gradienttia sen

Yksilöllisten elementtien lukumäärän laskeminen

Yksilöllisten elementtien lukumäärän laskeminen tietovirrassa (hetki ) on toinen asia $F_{0}$ [ selventää ] hyvin tutkittu ongelma. Ensimmäisen algoritmin ehdottivat Flajolet ja Martin [2] . Vuonna 2010 löydettiin asymptoottisesti optimaalinen algoritmi [8] .

Muistiinpanot

↑ Munro & Paterson (1980 )
↑ 1 2 Flajolet & Martin (1985 )
↑ Alon, Matias & Szegedy (1996 )
↑ Feigenbaum Joan , Kannan Sampath , McGregor Andrew , Suri Siddharth , Zhang Jian. Graafiongelmista puolisuoratoistomallissa // Teoreettinen tietojenkäsittelytiede. - 2005. - Joulukuu ( nide 348 , nro 2-3 ). - S. 207-216 . — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2005.09.013 .
↑ J. Xu Verkkotietojen suoratoiston opetusohjelma
↑ Schubert Erich , Weiler Michael , Kriegel Hans-Peter. SigniTrend // 20. ACM SIGKDD:n kansainvälisen Knowledge Discovery and Data Mining -konferenssin aineisto - KDD '14. - 2014. - ISBN 9781450329569 . - doi : 10.1145/2623330.2623740 .
↑ Entropiaarviot antoivat McGregor et ai., Do Ba et ai., Lall et ai., Chakrabarti et ai.[ selventää ]
↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), "Optimaalinen algoritmi erillisten elementtien ongelmalle", Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems, PODS '10, New York, NY, USA: ACM, s. 41-52, doi: 10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 .

Kirjallisuus

Alon, Noga ; Matias, Yossi & Szegedy, Mario (1999), Taajuusmomenttien approksimoinnin avaruuden monimutkaisuus , Journal of Computer and System Sciences , osa 58 (1): 137–147, ISSN 0022-0000 , DOI 10.1006/jcss.1997.1545 . Julkaistu ensimmäisen kerran nimellä Alon, Noga; Matias, Yossi & Szegedy, Mario (1996), Taajuusmomenttien approksimoinnin avaruuden monimutkaisuus , Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996) , s. 20–29, ISBN 0-89791-785-5 , DOI 10.1145/237814.237823 .
Babcock, Brian; Babu, Shivnath; Datar, Mayur & Motwani, Rajeev (2002), Mallit ja ongelmat tietovirtajärjestelmissä , Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) , s. 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), Optimaalinen algoritmi eri elementtien ongelmalle , PODS '10, New York, NY, USA: ACM, s. 41-52, ISBN 978-1-4503-0033-9 , DOI 10.1145/1807085.1807094 .
Karp, R.M .; Papadimitriou, CH & Shenker, S. (2003), Yksinkertainen algoritmi usein esiintyvien elementtien löytämiseksi virroista ja pusseista , ACM Transactions on Database Systems , osa 28 (1): 51–55 , DOI 10.1145/762471.762473 .
Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori & Xu, Jun (2006), Datan suoratoistoalgoritmit verkkoliikenteen entropian arviointiin , Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) , doi : 10.1145/291,4025/291,4025/291,4025/151,4025 / 15 /ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf > (kuollut linkki) .
Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming , < http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf > .

Linkit

Princetonin luentomuistiinpanot
Geometristen ongelmien suoratoistoalgoritmit , Piotr Indyk , MIT
Dagstuhl-työpaja sublineaarisista algoritmeista
IIT Kanpur Workshop tiedon suoratoistosta
Luettelo suoratoiston avoimista ongelmista (koonnut Andrew McGregor ) keskustelusta IITK Workshop on Algorithms for Data Streams, 2006.
StreamIt - ohjelmointikieli ja käännösinfrastruktuuri, MIT CSAIL (linkki ei käytettävissä)
IBM Spade - Stream Processing Application Declarative Engine
IBM InfoSphere Streams

oppikirjoja

S. Muthu Muthukrishnanin tietovirran algoritmit ja sovellukset
Stanford STREAM -projektikysely
Bloom-suodattimien verkkosovellukset , Broder ja Mitzenmacher
Xun SIGMETRICS 2007 opetusohjelma
Andrew McGregorin ja S. Muthu Muthukrishnanin luentomuistiinpanot Data Streams -kurssilta Barbadoksella vuonna 2009

Kurssit