Strömningsalgoritm

En  strömningsalgoritm är en algoritm för att bearbeta en sekvens av data i ett eller ett litet antal passager.

Strömalgoritmer löser problem där data anländer sekventiellt och i stora volymer. Ett exempel är analysen av nätverkstrafik på sidan av routern . Sådana problem lägger naturliga begränsningar på det tillgängliga minnet (mycket mindre än storleken på indata) och bearbetningstiden för varje element i sekvensen på strömmande algoritmer. Ofta är databehandling endast möjlig i ett pass.

Strikta begränsningar av tid och minne gör det ofta omöjligt att lösa problemet som studeras exakt. Flödesalgoritmer är vanligtvis probabilistiska och ger en approximation till det exakta svaret.

Historik

Även om sådana algoritmer övervägdes i verken under första hälften av 1980 -talet [1] [2] , formaliserades konceptet med en strömningsalgoritm först i Alon , Matias ( eng.  Yossi Matias ) och Szegedi ( eng.  Mario Szegedy ) 1996 [3] . År 2005 tilldelades författarna Gödelpriset för sitt grundläggande bidrag till streamingalgoritmer . 

2005 introducerades konceptet med en semi-streaming-algoritm [  4 ] som algoritmer som bearbetar den inkommande strömmen i en konstant eller logaritmisk[ förtydliga ] antal pass.

Modell

I strömdatamodellen anses det att en del av eller hela uppsättningen av indata som behöver bearbetas inte är tillgänglig för slumpmässig åtkomst : indata anländer sekventiellt och kontinuerligt i en eller flera strömmar. Dataströmmar kan representeras av en ordnad sekvens av punkter ("uppdateringar"), som kan nås i ordning och endast en gång eller ett begränsat antal gånger.

Många trådningspublikationer anser uppgiften att ha datorstatistik på en distribution av data som är för stor för effektiv lagring.[ specificera ] . För denna klass av problem antas det att vektorn (nollinitierad ) har ett visst antal "uppdateringar" i strömmen. Målet med sådana algoritmer är att beräkna funktioner för att använda betydligt mindre utrymme än vad som skulle kräva en fullständig representation av vektorn . Det finns två generella modeller för uppdatering av sådan data: " kassaregister " och "turnstile" ( sv . turnstile ).   

I "cash"-modellen representeras varje "uppdatering" i formuläret och vektorn modifieras på ett sådant sätt att den ökar med något positivt heltal . Ett specialfall är fallet (endast en enhet får sättas in).

I "turnstile"-modellen representeras varje "uppdatering" i formen och vektorn modifieras på ett sådant sätt att den ökar med något positivt eller negativt heltal . I en strikt modell kan vid varje given tidpunkt inte vara negativ.

I ett antal källor övervägs dessutom "slide-window"-modellen. I denna modell beräknas funktionen av intresse över ett fönster med begränsad dimensionalitet från strömdata, element från slutet av fönstret beaktas inte förrän ny data från strömmen tar deras plats.

Dessa algoritmer beaktar inte bara frågor relaterade till datas frekvensegenskaper, utan också ett antal andra. Många problem på grafer löses under förutsättning att grafens närliggande matris strömladdas i någon okänd ordning i förväg. Ibland, tvärtom, är det nödvändigt att lösa problemet med att uppskatta ordningen på data, till exempel för att räkna antalet inversa värden i strömmen och hitta den största ökande sekvensen.

Jämförelse av algoritmer

De viktigaste egenskaperna hos strömmande algoritmer:

Dessa algoritmer har mycket gemensamt med onlinealgoritmer , eftersom algoritmen måste fatta ett beslut innan all data är tillgänglig, men det finns skillnader. I synnerhet har in-line-algoritmer förmågan att fördröja att fatta beslut tills en grupp av punkter i en datasekvens anländer, medan onlinealgoritmer måste fatta beslut när varje ny punkt i en sekvens anländer.

Om algoritmen är ungefärlig, är noggrannheten i svaret en annan indikator. Noggrannheten hos en algoritm representeras ofta som ett värde , vilket betyder att algoritmen kommer att uppnå mindre fel med en sannolikhet på .

Applikation

Strömalgoritmer är av stor betydelse i uppgifterna att övervaka och hantera datornätverk, till exempel genom att de med hjälp av dem är det möjligt att snabbt förhindra bräddavlopp (spåra jätteströmmar uppskatta antalet och förväntade varaktigheten av brädden) [ ] Dessutom kan strömningsalgoritmer användas i databaser, till exempel för att uppskatta storleken efter en tabellanslutningsoperation .

Exempel på problem lösta med strömningsalgoritmer

Problem med frekvensfördelning

Det:e frekvensmomentet i vektorn definieras som .

Det första momentet  är den enkla summan av frekvenserna (det vill säga det totala antalet). Den andra punkten är användbar för att beräkna statistiska parametrar för data, såsom Gini-koefficienten . definieras som frekvensen av det mest frekvent förekommande elementet.

Frågorna om att uppskatta frekvensmoment studeras också.

Sök efter tunga element

Uppgiften är att hitta det mest frekvent förekommande elementet i dataströmmen. Följande algoritmer gäller här:

Trendspårning

Trender i en dataström görs vanligtvis i följande ordning: de vanligaste elementen och deras frekvenser bestäms baserat på en av ovanstående algoritmer[ förtydliga ] <--algoritmer för att hitta tunga element? och om detta avsnitt flyttas lägre?-->, och då noteras den största ökningen i förhållande till föregående tidpunkt som en trend. För detta används ett exponentiellt glidande medelvärde och olika normaliseringar [6] . Den använder mellanslag O(ε² + log d) och O(1) värsta tänkbara uppdatering för en universell hashfunktion från familjen av r-smarta oberoende hashfunktioner med r = Ω(log(1/ε)/log log(1) / ε))[ specificera ] .

Entropi

En empirisk entropiuppskattning över en uppsättning frekvenser definieras som , där [7] .

Maskininlärning

Huvuduppgiften för online maskininlärning  är att träna en modell (till exempel en klassificerare) i ett pass genom träningsuppsättningen; prediktiv hashning och gradient för att det

Räknar antalet unika element

Att räkna antalet unika element i dataströmmen (moment ) är en annan[ förtydliga ] ett väl studerat problem. Den första algoritmen föreslogs av Flajolet och Martin [2] . 2010 hittades en asymptotiskt optimal algoritm [8] .

Anteckningar

  1. ↑ Munro & Paterson (1980 )
  2. ↑ 1 2 Flajolet & Martin (1985 )
  3. ↑ Alon, Matias & Szegedy (1996 )
  4. ↑ Feigenbaum Joan , Kannan Sampath , McGregor Andrew , Suri Siddharth , Zhang Jian. Om grafproblem i en semi-streaming modell  // Teoretisk datavetenskap. - 2005. - December ( vol. 348 , nr 2-3 ). - S. 207-216 . — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2005.09.013 .
  5. ↑ J. Xu En handledning om nätverksdataströmning
  6. ↑ Schubert Erich , Weiler Michael , Kriegel Hans-Peter. SigniTrend  // Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. - 2014. - ISBN 9781450329569 . - doi : 10.1145/2623330.2623740 .
  7. ↑ Entropiuppskattningar gavs av McGregor et al., Do Ba et al., Lall et al., Chakrabarti et al.[ förtydliga ]
  8. ↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), "An optimal algorithm for the distinct elements problem", Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of databas systems, PODS '10, New York, NY, USA: ACM, sid. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 .

Litteratur

Länkar

läroböcker Kurser