Flajolet – Martinův algoritmus - Flajolet–Martin algorithm

The Flajolet – Martinův algoritmus je algoritmus pro aproximaci počtu odlišných prvků v proudu s jedním průchodem a logaritmickou spotřebou prostoru v maximálním počtu možných odlišných prvků v proudu ( početně odlišný problém ). Algoritmus zavedl Philippe Flajolet a G. Nigel Martin ve svém článku z roku 1984 „Pravděpodobnostní algoritmy počítání pro aplikace databází“.^[1] Později to bylo vylepšeno v „LogLog počítání velkých světových stran“ Marianne Durand a Philippe Flajolet,^[2] a "HyperLogLog: Analýza téměř optimálního algoritmu odhadu mohutnosti "od Philippe Flajolet et al.^[3]

Ve svém článku z roku 2010 „Optimální algoritmus pro problém odlišných prvků“^[4] Daniel M. Kane, Jelani Nelson a David P. Woodruff poskytují vylepšený algoritmus, který využívá téměř optimální prostor a má optimální Ó(1) časy aktualizací a hlášení.

Algoritmus

Předpokládejme, že dostáváme a hashovací funkce ${ displaystyle mathrm {hash} (x)}$ který mapuje vstup ${ displaystyle x}$ na celá čísla v rozsahu ${ displaystyle [0; 2 ^ {L} -1]}$ , a kde jsou výstupy dostatečně rovnoměrně rozloženo. Všimněte si, že sada celých čísel od 0 do ${ displaystyle 2 ^ {L} -1}$ odpovídá množině binárních řetězců délky ${ displaystyle L}$ . Pro jakékoli nezáporné celé číslo ${ displaystyle y}$ , definovat ${ displaystyle mathrm {bit} (y, k)}$ být ${ displaystyle k}$ -tý bit v binární reprezentaci ${ displaystyle y}$ takové, že:

{ displaystyle y = sum _ {k geq 0} mathrm {bit} (y, k) 2 ^ {k}.}

Poté definujeme funkci ${ displaystyle rho (y)}$ která vydává pozici nejméně významného nastaveného bitu v binární reprezentaci ${ displaystyle y}$ :

{ displaystyle rho (y) = min {k geq 0 mid mathrm {bit} (y, k) neq 0 }}

kde ${ displaystyle rho (0) = L}$ . Všimněte si, že s výše uvedenou definicí používáme pro pozice 0 indexování. Například, ${ displaystyle rho (13) = rho (1101_ {2}) = 0}$ , protože nejméně významný bit je 1 (0. pozice), a ${ displaystyle rho (8) = rho (1000_ {2}) = 3}$ , protože nejméně významný bit je na 3. pozici. V tomto bodě si všimněte, že za předpokladu, že výstup naší hashovací funkce je rovnoměrně rozložen, pak pravděpodobnost pozorování hash výstupu končícího ${ displaystyle 2 ^ {k}}$ (jeden, následovaný ${ displaystyle k}$ nula) je ${ displaystyle 2 ^ {- (k + 1)}}$ , protože to odpovídá převrácení ${ displaystyle k}$ hlavy a pak ocas se spravedlivou mincí.

Nyní Flajolet – Martinův algoritmus pro odhad mohutnosti a multiset ${ displaystyle M}$ je následující:

Inicializujte bitový vektor BITMAP, který má délku ${ displaystyle L}$ a obsahují všechny 0s.
Pro každý prvek ${ displaystyle x}$ $X$ v ${ displaystyle M}$ $M$ :
1. Vypočítejte index ${ displaystyle i = rho ( mathrm {hash} (x))}$ .
2. Soubor ${ displaystyle mathrm {BITMAP} [i] = 1}$ .
Nechat ${ displaystyle R}$ označují nejmenší index ${ displaystyle i}$ takhle ${ displaystyle mathrm {BITMAP} [i] = 0}$ .
Odhadněte mohutnost ${ displaystyle M}$ tak jako ${ displaystyle 2 ^ {R} / phi}$ , kde ${ displaystyle phi přibližně 0,77351}$ .

Myšlenka je, že pokud ${ displaystyle n}$ je počet odlišných prvků v multisetu ${ displaystyle M}$ , pak ${ displaystyle mathrm {BITMAP} [0]}$ je přístupný přibližně ${ displaystyle n / 2}$ časy, ${ displaystyle mathrm {BITMAP} [1]}$ je přístupný přibližně ${ displaystyle n / 4}$ krát a tak dále. V důsledku toho, pokud ${ displaystyle i gg log _ {2} n}$ , pak ${ displaystyle mathrm {BITMAP} [i]}$ je téměř jistě 0, a pokud ${ displaystyle i ll log _ {2} n}$ , pak ${ displaystyle mathrm {BITMAP} [i]}$ je téměř jistě 1. Pokud ${ displaystyle i cca log _ {2} n}$ , pak ${ displaystyle mathrm {BITMAP} [i]}$ lze očekávat, že bude 1 nebo 0.

Korekční faktor ${ displaystyle phi přibližně 0,77351}$ je nalezen výpočty, které najdete v původním článku.

Zlepšení přesnosti

Problém s algoritmem Flajolet – Martin ve výše uvedené formě spočívá v tom, že výsledky se výrazně liší. Běžným řešením bylo spuštění algoritmu vícekrát s ${ displaystyle k}$ různé hashovací funkce a kombinovat výsledky z různých běhů. Jedním z nápadů je vzít v úvahu ${ displaystyle k}$ výsledky společně z každé hashovací funkce, získání jediného odhadu mohutnosti. Problém je v tom, že průměrování je velmi náchylné k odlehlým hodnotám (které jsou zde pravděpodobně). Jiný nápad je použít medián, což je méně náchylné k vlivům odlehlých hodnot. Problém je v tom, že výsledky mohou mít pouze formu ${ displaystyle 2 ^ {R} / phi}$ , kde ${ displaystyle R}$ je celé číslo. Běžným řešením je kombinace střední a střední hodnoty: Vytvořit ${ displaystyle k cdot l}$ hash funkce a rozdělit je na ${ displaystyle k}$ odlišné skupiny (každá o velikosti ${ displaystyle l}$ ). V každé skupině použijte medián pro agregaci dohromady ${ displaystyle l}$ výsledky a nakonec vezměte průměr z ${ displaystyle k}$ skupinové odhady jako konečný odhad.

V roce 2007 HyperLogLog Algoritmus rozdělí multiset na podskupiny a odhadne jejich kardinality, poté použije harmonický průměr spojit je do odhadu původní mohutnosti.^[3]

Viz také

Reference

^ Flajolet, Philippe; Martin, G. Nigel (1985). „Algoritmy pravděpodobnostního počítání pro databázové aplikace“ (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8. Citováno 2016-12-11.
^ Durand, Marianne; Flajolet, Philippe (2003). "Počítání logů velkých kardinálností" (PDF). Algoritmy - ESA 2003. Přednášky z informatiky. 2832. str. 605. doi:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Citováno 2016-12-11.
^ ^A ^b Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). „Hyperloglog: Analýza téměř optimálního algoritmu odhadu mohutnosti“ (PDF). Sborník z diskrétní matematiky a teoretické informatiky. Nancy, Francie. AH: 127–146. CiteSeerX 10.1.1.76.4286. Citováno 2016-12-11.
^ Kane, Daniel M .; Nelson, Jelani; Woodruff, David P. (2010). "Optimální algoritmus pro problém odlišných prvků" (PDF). Sborník dvacátého devátého sympózia ACM SIGMOD-SIGACT-SIGART o zásadách databázových systémů dat - PODS '10. str. 41. doi:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. Citováno 2016-12-11.

Další zdroje

Rajaraman, Anand; Ullman, Jeffrey David (2011-10-27). Těžba masivních datových sad. Cambridge University Press. str. 119. ISBN 9781139505345. Citováno 2014-11-09.

[1] Flajolet, Philippe; Martin, G. Nigel (1985). „Algoritmy pravděpodobnostního počítání pro databázové aplikace“ (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8. Citováno 2016-12-11.

[2] Durand, Marianne; Flajolet, Philippe (2003). "Počítání logů velkých kardinálností" (PDF). Algoritmy - ESA 2003. Přednášky z informatiky. 2832. str. 605. doi:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Citováno 2016-12-11.

[flajolet07-3] A ^b Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). „Hyperloglog: Analýza téměř optimálního algoritmu odhadu mohutnosti“ (PDF). Sborník z diskrétní matematiky a teoretické informatiky. Nancy, Francie. AH: 127–146. CiteSeerX 10.1.1.76.4286. Citováno 2016-12-11.

[4] Kane, Daniel M .; Nelson, Jelani; Woodruff, David P. (2010). "Optimální algoritmus pro problém odlišných prvků" (PDF). Sborník dvacátého devátého sympózia ACM SIGMOD-SIGACT-SIGART o zásadách databázových systémů dat - PODS '10. str. 41. doi:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. Citováno 2016-12-11.

[1]

[2]

[3]

[4]