ADŠ prednáška 25: Výber náhodnej vzorky zo streamu, Bloom filter.

Zhrnutie prednášky

Posledná prednáška predmetu sa venuje výberu náhodnej vzorky z prúdu dát (streamu), ktorý nie je možné celý uložiť do pamäte. Na metafore sushi pásu je odvodený algoritmus pre vzorku veľkosti 1: i-ty prvok sa ponechá s pravdepodobnosťou 1/i, inak sa zahodí, čím má každý prvok na konci rovnakú šancu. Algoritmus beží v lineárnom čase, s konštantnou pamäťou a nevyžaduje poznať veľkosť vstupu vopred. Následne sa metóda zovšeobecňuje na vzorku veľkosti K: prvých K prvkov sa uloží do poľa a každý ďalší (n+1-vý) prvok sa do vzorky dostane s pravdepodobnosťou odvodenou z podielu kombinačných čísel, ktorá vychádza K/(n+1). Úvod prednášky motivuje vzorkovanie príkladmi ako prieskumy preferencií, odhad počtu rýb v rybníku a problém nemeckých tankov.

• - Náhodná vzorka často stačí na odhad vlastností celého datasetu, ak je vybraná rovnomerne.
• - Ak sa dáta zmestia do pamäte, vzorku veľkosti K získame zamiešaním poľa a vzatím prvých K prvkov.
• - Pre stream a vzorku veľkosti 1: i-ty prvok sa ponechá s pravdepodobnosťou 1/i, inak sa zahodí.
• - Algoritmus potrebuje lineárny čas, konštantnú pamäť a nemusí vopred poznať veľkosť vstupu.
• - Pre vzorku veľkosti K sa prvých K prvkov uloží do poľa a každý ďalší prvok sa do vzorky dostane s pravdepodobnosťou K/(n+1).
• - Pravdepodobnosť sa odvodí ako podiel počtu K-prvkových výberov obsahujúcich nový prvok a všetkých výberov, teda C(n,K-1)/C(n+1,K).
• - Prednáška v názve avizuje aj Bloom filter, ktorý sa v úvodnej časti prepisu ešte nedostal na rad.

Zhrnutie pripravené s pomocou AI z prepisu videa.