Algoritmy pro rozsáhlá data Mgr. Adéla Laštovičková

Zápočet

• Pro splnění zápočtu je nutné vypracovat tři úkoly.

První zápočtový úkol

Máte soubor o velikosti cca 200GB obsahujíc miliardu uživatelských komentářů tvaru

     { comment-id:	289459745,
       article-id:	772445,
       user-id:		007,
       text:	        I’m Bond, James Bond.,
       views:		29397,
       likes:		59 }  .

Navrhněte algoritmus, jenž:

1. v souboru najde nejčastěji se vyskytující komentář.
2. v souboru najde zadaný komentář.
3. zjistí, kolik různých komentářů soubor obsahuje.

Algoritmy navrhněte tak, abyste je byli schopni spustit na svém počítači. U každého algoritmu odhadněte jeho složitost. V rámci řešení můžete soubor před spuštěním algoritmu upravit. Například můžete komentáře v souboru přeuspořádat.
Své řešení odevzdejte na cvičení napsané rukou a čitelně do 15.10.2025.

Druhý zápočtový úkol

Podrobně si prostudujte

1. Bloomovy filtry nebo Kvocientové filtry,
2. Count-Min Sketch,
3. HyperLogLog

a s jejich pomocí vyřešte problémy prvního úkolu. U každého řešení opět odhadněte jeho složitost. Dále své nové a původní řešení porovnejte. Například můžete určit, k jak velké(mu) úspoře místa (zrychlení) došlo.
Řešení odevzdejte na cvičení nejpozději v zápočtovém týdnu. (17.12.2025)

Třetí zápočtový úkol

Podívejte se na operace prováděné s B-stromy. Poté simulujte průběh přidání klíče 111 a následně smazání klíče 18 z B-stromu řádu 3 zaslaného mailem.
Své řešení odevzdejte na papíře nejpozději na cvičení v zápočtovém týdnu. (17.12.2025)