vedavyzkum.cz
„Myslím, že když chcete být při žádosti o ERC grant úspěšní, musíte být realističtí, ale ne přehnaně skromní,“ říká Pavel Veselý z Informatického ústavu UK, který v červnu získal prestižní grant ERC CZ. Díky němu se zaměří na výzkum malých datových struktur robustních proti útokům, jejichž cílem je způsobit velkou chybu.
Na Matfyzu se zabýváte algoritmy pro analýzu velkých dat. O co přesně jde?
Jedná se o takzvané proudové (streaming) algoritmy, kterým stačí jen malá paměť a jeden průchod přes data. Používají se k odhadu jednoduše definovaných statistik s co nejmenší chybou v daném prostoru. Výsledným datovým strukturám se říká skeče, neboť se v malém prostoru snaží zachytit důležité vlastnosti vstupních dat.
Tradiční algoritmy mají prakticky libovolný přístup k datům a mohou po nich „skákat“ sem a tam jako po nějakém poli a nejsou typicky omezené pamětí, kterou si mohou navyšovat přímo úměrně velikosti dat. Oproti nim proudové algoritmy se na vstup dat dívají jako na sekvenci, jež postupně přichází. Představte si, že běží na síťovém zařízení, které monitoruje provoz, nebo na serveru, jemuž přichází určité požadavky, a on si měří, jak dlouho mu trvá každý zpracovat. Tyto informace se předají do datové struktury neboli proudového algoritmu. Ten ale nemá možnost se vrátit do minulosti k předchozím pozorováním.
Proudový algoritmus si tedy nemůže svoje poznatky ukládat?
Nemůže si uložit vše, protože pracuje s malou pamětí a ta možnosti ukládání poznatků o vstupu výrazně omezuje. Každé nové pozorování, které přijde, dokáže zpracovat velmi rychle, což je jeho další typická vlastnost. Kvůli své malé paměti umí úspěšně řešit jen určité základní problémy a musí se také naučit dobře zapomínat a vytáhnout z dat důležité vlastnosti, jež k řešení určitého problému potřebujeme. Například zjišťujeme, kolik požadavků trvalo víc jak půl sekundy nebo sekundu nebo i deset sekund. Takto dlouhých požadavků už může být relativně málo a zároveň si je nechceme, a kvůli té malé paměti ani nemůžeme, ukládat všechny.
Problém je, že kvůli tomu, že si proudové algoritmy nepamatují všechno, kromě naprosto triviálních úkolů (například součet všech čísel na vstupu) u nich vždycky musíme počítat s určitou chybou.
K čemu se proudové algoritmy v praxi používají?
Využívají se u aplikací, které pracují s velkými daty, u nichž nepotřebujeme znát přesný výsledek, ale stačí nám pouze přibližný. Například v oblasti online reklamy, kdy zadavatel potřebuje vědět, kolik různých uživatelů ji vidělo. Nepotřebuje však znát jejich přesný počet (zda jde o 101 nebo 102 tisíc lidí), takže nám malá chyba v řádech jednotek procent většinou nevadí.
Jak dlouho se proudovými algoritmy zabýváte?
Dostal jsem se k nim během postdoktorandského výzkumného pobytu na University of Warwick. Byl jsem postdokem Grahama Cormoda, jednoho z předních odborníků na tuto problematiku, jíž se zabývá přes dvacet let. Byla to pro mě ohromná příležitost se naučit něco nového.
O algoritmy se ale zajímám mnohem déle. Na doktorátu jsem řešil online algoritmy, které také zpracovávají vstup dat po jednotlivých prvcích. U nich nejsme omezeni pamětí, ale zase tím, že se během zpracování nového prvku musíme okamžitě rozhodnout. Například nám chodí úlohy k rozvržení, a my každou musíme hned přiřadit na nějaký stroj, který ji zpracuje, aniž bychom dopředu věděli, jaké další úlohy k nám budou přicházet. Tím pádem nemusíme vždy získat optimální řešení.
Continue Reading →