Disertační práce

English

Title:

Problém Online Labelingu

Autor:

Jan Bulánek, Ph.D.

Školitel:

Doc. Mgr. Michal Koucký, Ph.D.

Obhajoba:

Praha, 2014

Pracoviště:

Matematický ústav Akademie věd České republiky

Pracoviště:

Katedra teoretické informatiky a matematické logiky

Ke stažení

Přihláška: Application.pdf

Disertační práce: Thesis.pdf

Rozšířený abstrakt: ExtendedAbstract.pdf

Životopis: cv.pdf

Posudek Doc. Mgr. Michal Koucký Ph.D. (školitel): AdvisorReview.pdf

Posudek Prof. Gerth Stolting Brodal (oponent): BrodalReview.pdf

Posudek Prof. John Iacono (oponent): IaconoReview.pdf

Abstrakt

Setříděné pole je základní algoritmický pojem, jehož on-line varianta je podstatou pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel délky n z univerza {1,..., r} v libovolném pořadí. Naším úkolem je udržovat všechna čísla, která byla vložena do pole, setříděná. Mezi vloženými čísly mohou být volná políčka. Protože závěrečné pořadí čísel nelze určit, dokud nejsou všechna čísla vložena, je povoleno vložená čísla přesouvat. Cílem je minimalizovat počet přesunů.

Již od konce osmdesátých let jsou známy algoritmy s amortizovanou cenou O(log2(n)) za vložené číslo v případě, že velikost pole je m=O(n). V této dizertaci ukážeme, že tyto algoritmy jsou asymptoticky optimální. Dále byly známy algoritmy pro určité velikosti m. Nám se podařilo rozšířit tyto algoritmy pro prakticky všechny hodnoty m a zároveň dokázat, že jsou asymptoticky optimální. Žádný známý algoritmus nevyužívá vztahu mezi velikostí universa r a velikostí pole m. Není přitom zjevné, že pro r srovnatelné s m nelze zkonstruovat výrazně rychlejší algoritmus. Pro určité velikosti m, zejména pak pro lineární případ, dokážeme, že něco takového není možné. Toto je první výsledek zabývající se touto otázkou. Některé naše optimální dolní odhady jsme ukázali také pro randomizované algoritmy. V těchto případech jsme dokázali, že očekávaný čas randomizovaných algoritmů je stejný jako pro deterministické algoritmy.

Publikace

1.  J. Bulánek, M. Koucký, M. Saks
On Randomized Online Labeling with Polynomially Many Labels
International Colloquium on Automata, Languages and Programming, ICALP’13 , pp. 291-302, 2013.

2.   Z. Falt , J. Bulánek, J. Yaghob
On Parallel Sorting of Data Streams
17. Advances in Databases and Information Systems, ADBIS’ 12 , pp. 69-77, 2012.

3.   M. Babka, J. Bulánek, V. Čunát, M. Koucký, M. Saks,
On online labeling with polynomially many labels
20th Annual European Symposium on Algorithms, ESA'12, pp. 121-132, 2012.

4.   J. Bulánek, M. Koucký, M. Saks      
Tight lower bounds for online labeling problem
44th Annual ACM Symposium on Theory of Computing, STOC'12, pp. 1185-1198, 2012.

5.   J. Bulánek
Prefix vs. unordered bucketing
V přípravě.

6.   J. Bulánek
A note on list coloring of squares of cycles
Manuscript.

Popularizační přehled výsledků

Návrh efektivních algoritmů a datových struktur je hlavním cílem teoretické informatiky již od jejích prvopočátků. Kvůli rostoucímu množství zpracovávaných dat je tento cíl stále důležitý i přes rostoucí výpočetní sílu zařízení. Proto potřebujeme navrhnout co nejlepší algoritmy nebo datové struktury. Abychom toho mohli dosáhnout, je potřeba určit, co je nejlepší řešení. Je tedy nutné najít dolní odhad na časovou (paměťovou) složitost algoritmu či datové struktury.

 

V této práci se zabýváme obojím, jak návrhem algoritmů, tak důkazy odpovídajících dolní odhadů. Pro konkrétní problém, tzv. problém online labelingu, navrhneme nový algoritmus, který pro určité vstupy překonává známá řešení a zároveň dokážeme obecný, těsný dolní odhad.

 

Problém online labelingu je úzce spojen s tříděním. Třídění je nepochybně jeden z nejdůležitějších problémů informatiky. Známe optimální časovou složitost třídění. Setříděné pole se snadno používá, je možné v nich vyhledávat v optimálním čase a optimálně využívají mezipaměti při sekvenčních průchodech.

 

Přirozená otázka zní, zda je možné efektivně modifikovat setříděné pole, tj. například vložit nový prvek. Taková datová struktura by měla přímé praktické použití, např. dynamická setřízená pole, prioritní fronty, slovníky atd.

Kromě přímých aplikací existují i další oblasti pro něž je online labeling klíčový. Emek a Korman ukázali spojitost mezi online labelingem a problémem distributed controller. V této úloze dostávají uzly v asynchronní distribuované síti vnější požadavky na použití omezeného zdroje a tyto uzly pak udělují svolení k použítí zdroje. Kombinace jejich a našich výsledků implikuje optimální dolní odhad pro problém distributed controller.

Popis problému online labelingu

Na vstupu je dáno pole velikosti m a posloupnost n čísel v libovolném pořadí, přičemž n<m. Vaším úkolem je udržovat všechny doposud vložené prvky v setříděném pořadí. Mezi vloženými čísly mohou být prázdná políčka. Protože konečné pořadí prvků není známo, dokud nevložíme všechny, je povoleno vložené prvky přesouvat. Počet přesunů by ale měl být minimalizován.

Nyní si ukážeme, jak vypadá jeden krok algoritmu řešícího problém online labelingu. Vložení dalšího čísla se skládá ze tří kroků.


Uvažme následující rozložení čísel v poli a posloupnost čísel jako vstup (tato posloupnost není algoritmu známa), kterých bylo dosaženo po učitém počtu vložení. Všimněte si, že pole je setříděno a že mezi některými čísly jsou prázdná políčka.

1. krok

Algoritmus dostane další číslo ke vložení a určí pozici v poli, na níž by toto číslo mělo být vloženo. Povšimněte si, že pro číslo 12 není v poli místo. Je dokonce možné ukázat, že pokud velikost pole není aspoň m≥2n nebo pokud vstupní posloupnost není známa dopředu, tak není možné zaručit prázdné políčko pro každé vkládané číslo.

2. krok

V dalším kroku algoritmus přesune (libovolná) z již vložených čísel tak, aby uvolnil políčko pro nové číslo. Počet těchto přesunů chceme minimalizovat a určují efektivitu algoritmu. V tomto případě je cena vložení 4. Posunuta byla 3 čísla (vzdálenost přesunu nehraje roli) a jedno číslo bylo vloženo.

3. krok

Nově vkládané číslo je vloženo do pole a můžeme pokračovat s číslem 14.

Triviální řešení posune až O(n) prvků v každém vložení, takže celková složitost je O(n2). Takové řešení ale vůbec nevyužívá toho, že velikost pole může být výrazně větší než n.

Toto je jedna z možných definic problému online labelingu, která je též známa jako file maintenance problem. V obecné verzi jsou prvkům z univerza U velikosti r přiřazeny labely z lineárně uspořádaného universa velikosti m. Pořadí labelů musí odpovídat pořadí příslušných prvků. Změna labelů prvků (což odpovídá přesouvání prvků v poli) je povolena, ale měla by být minimalizována. Takováto formulace je smysluplná i pro m řádově větší než n.

Známé algoritmy

Zatímco algoritmus se složitostí O(n2) je zřejmý a přímočarý, existence efektivního a přitom jednoduchého algoritmu není zjevná. První takový algoritmus byl navržen na začátku osmdesátých let (Itai, Konheim a Rodeh). Amortizovaná složitost jejich řešení byla O(log2(n)) za každý vložený prvek, přičemž velikost pole je cn pro libovolné c>1. Tento překvapivý výsledek byl dosažen pomocí vhodného využití volného místa. Od té doby vzniklo několik dalších algoritmů. Ten nejnovější z roku 2007 (Itai a Katriel) je možné implementovat na několik řádek kódu. Nejkomplikovanější částí jejich algoritmu je binární vyhledávání, které slouží k určení pozice nově vkládaného čísla. Na druhou stranu je potřeba netriviální analýza k tomu, abychom dokázali jeho správnost a určili jeho časovou složitost.

Přínos naší práce.

Po více než třicet let bylo otevřeným problémem, zda existující algoritmy (všechny s asymptotickou složitostí O(log2(n)) za vložený prvek) jsou asymptoticky optimální. Zejména nové aplikace v oblasti takzvaných cache oblivious algoritmů učinily tuto otázku velmi důležitou.

 

V naší práci zodpovíme tuto otázku nalezením odpovídajích dolních odhadů pro všechny tyto algoritmy. Ve skutečnosti dokážeme těsný dolní odhad pro téměř všechny možné velikosti pole a v případě lineárně velkých polí tento dolní odhad dokážeme dokonce za předpokladu omezeného universa r∊O(n) (zatímco všechny předchozí výsledky předpokládaly r≥2n). Dokážeme i první dolní odhad pro randomizované algoritmy řešící problém online labelingu.

 

Dále předvedeme první algoritmus pro pole velikosti nlog n 2n. Optimalita tohoto algoritmu plyne z námi dokázaných dolních mezí. Tento výsledek je smysluplný v obecné formulaci problému online labelingu přičemž bitová velikost labelů je logaritmická v m.

Naše výsledky tedy určují optimální složitost v podstatě všech deterministických algoritmů pro problém online labelingu.

Otevřené otázky

Existují dvě možné cesty, jak rozšířit naše výsledky: existují randomizované algoritmy, které dosahují asymptoticky lepší složitosti? Víme, že pro pole polynomiální velikosti tomu tak není, ale pro ostatní velikosti není odpověď známa. Druhým směrem je otázka, zda je možné získat lepší algoritmus v případě, že velikost univerza z něhož volíme vkládané prvky je srovnatelná s velikostí pole. Pro lineárně velká pole toto není pravda, nicméně pro větší pole takový výsledek chybí.

Poděkování

Rád bych poděkoval všem spoluautorům, jmenovitě Michalu Kouckému, Michaelu Saksovi, Martinu Babkovi a Vladimíru Čunátovi, bez nichž by žadný z těchto výsledků nevznikl. Tento text nicméně vyjadřuje pouze můj osobní pohled na tuto problematiku. Může tedy obsahovat chyby případně opomíjet některé důležité aspekty našich výsledků.