I de flesta algoritmiska tillämpningar som jämför två distributioner är informationsteoretiska avstånd mer naturliga än standard p normer. I detta papper designar vi streaming och sublinear tid egendom testa algoritmer för entropi och olika information teoretiska avstånd. Batu et al poserade problemet med egendomsprövning med avseende på Jensen-Shannon avstånd. Vi presenterar optimala algoritmer för att uppskatta avgränsade, symmetriska f-divergences (inklusive Jensen-Shannon divergens och Hellinger avstånd) mellan distributioner i olika egendom testramar. Längs vägen stänger vi ett (log n)/H gap mellan de övre och nedre gränserna för uppskattning av entropi H, vilket ger en optimal algoritm över alla värden av entropi. I en dataströmsinställning (sublinjärt utrymme) ger vi den första algoritmen för att uppskatta entropi för en distribution. Vår algoritm körs i polylogaritmiskt utrymme och ger en asymptotisk konstant faktor approximation schema. En integrerad del av algoritmen är en intressant användning av en F0 (antalet olika element i en uppsättning) uppskattningsalgoritm; vi ger också andra resultat längs mellanslag/tid/ungefärlig avräkningskurva. Våra resultat har intressanta strukturella implikationer som förbinder sublinjär tid och utrymme begränsade algoritmer. Medlingsmodellen är den slumpmässiga streamingmodellen, som förutsätter att indatan är en slumpmässig permutation av ett multiset och först övervägdes av Munro och Paterson 1980. Vi visar att alla egenskapstestande algoritmer i den kombinerade orakelmodellen för beräkning av permutationsinvarianta funktioner kan simuleras i den slumpmässiga ordermodellen i ett enda pass. Detta tar upp en fråga som togs upp av Feigenbaum et al om förhållandet mellan testning av egendom och strömalgoritmer. Dessutom ger vi en polylog-rymden PTAS för att uppskatta entropi av en ett pass slumpmässig ordning ström. Denna gräns kan inte uppnås i den kombinerade oraklet (generaliserad egenskapstestning).
McGregor m.fl. REF beskriver algoritmer som uppskattar entropi och andra informationsteoretiska åtgärder i ett strömmande sammanhang.
Streaming and sublinear approximation of entropy and information distances
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}