Prezentácia

Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti dátových štruktúr. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok.

Termíny

• Výber článku na prezentáciu do pondelka 24.4. v systéme Moodle. Každý článok môže prezentovať iba jeden študent, takže odovzdajte svoj výber radšej skôr. Kto si článok do uvedeného termínu nevyberie, bude mu nejaký priradený vyučujúcou.
• Prezentácie na prednáškach v posledných týždňoch semestra
• Prezentáciu vo formáte pdf odovzdať prostredníctvom Moodlu najneskôr 1 hodinu pred prednáškou, na ktorej máte prezentovať.

Rozvrh prezentácií

V rozvrhu uvádzam len skrátené názvy článkov zo zoznamu nižšie

Streda 10.5.

• Komanová Average case analysis of Java 7’s dual pivot
• D. Simeunovič Hollow heaps
• Miklošovič Disjoint Set Union with Randomized Linking
• R. Simeunovič Weighted dynamic finger in binary search trees

Utorok 16.5.

• Červeň Searchable Encryption with Small Leakage
• Krajčovič A right-optimized write-optimized file system.
• Fikar The string B-tree
• Bezca Cache-oblivious priority queue

Streda 17.5.

• Rudolf The level ancestor problem simplified.
• Matušák Nearest common ancestors
• Jariabka Counting Bloom filters
• Petrucha GK arrays
• Novák Optimized succinct data structures

Utorok 23.5.

• Rabatin Fast indexing strategies for robust image hashes
• Šuppa Extended bloom filter: an aid to network processing
• Smolík Adaptive and approximate orthogonal range counting
• Ivančík Bonsai: a compact representation of trees

Streda 24.5.

• Batmendijn Data Structure for Processing Palindromes in Strings
• Metohajrová Space-efficient top-k string retrieval problems
• Kraml Relative FM-indexes
• Hraška The engineering of a compression boosting library (BWT)
• Vošček String search experimentation using massive data

Rady k prezentácii

• Na prezentáciu budete mať 15 minút (plus diskusia), pričom tento limit bude striktne dodržiavaný. Nechystajte si teda priveľa materiálu, rátajte aspoň 1,5 minúty na slajd.
• K dispozícii bude dátový projektor a notebook, na ktorom bude nahraná vaša odovzdaná prezentácia. Môžete si priniesť aj vlastný počítač. Môžete použiť tabuľu, ale s mierou, lebo vysvetľovanie pri tabuli ide pomalšie.
• Hlavným cieľom je porozprávať niečo zaujímavé z vášho článku vo forme prístupnej vašim spolužiakom (ktorí chodili na tento predmet, nepamätajú si však každý detail z každej prednášky). Nemusíte pokryť celý obsah článku a nemusíte použiť rovnaké poradie, označenie alebo príklady, ako autori článku.
• Nedávajte do prezentácie veľa textu, použite dostatočne veľký font a dobre viditeľné farby (podobné farby, napr. žltá na bielej, nemusia byť na projektore vôbec viditeľné).
• Použite čo najmenej definícií a označenia. Pojmy, algoritmy a dôkazy radšej ilustrujte na obrázku alebo príklade, než zložitým textom.

Typická osnova prezentácie (podľa potreby ju však možete meniť):

• Úvod: aký problém autori študujú, prečo je dôležitý alebo zaujímavý? Má nejaký vzťah k učivu z prednášok, prípradne k iným predmetom?
• Prehľad výsledkov: V čom je presne prínos autorov oproti predchádzajúcim prácam? Nemusíte robiť rozsiahly prehľad predchádzajúcich prác, len uveďte, čo je v článku nové. Malo by to byť jasné najmä z úvodu a záveru článku.
• Jadro: Vysvetlite nejaký kúsok zo samotného obsahu článku (časť algoritmu alebo dôkazu, niektoré výsledky z testovania na dátach a pod.)
• Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo)

Typy vhodných článkov

• Články o dátových štruktúrach alebo ich variantoch, ktoré neboli/nebudú pokryté na prednáške
• Články empiricky porovnávajúce dátové štruktúry na reálnych dátach alebo popisujúce použitie týchto algoritmov v reálnych aplikáciach.
• Články o podrobnejšej analýze dátových štruktúr: dolné a horné odhady, analýza v priemernom prípade a pod.

Príklady článkov

Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.

• Andoni A, Razenshteyn I, Nosatzki NS. Lsh forest: Practical algorithms made theoretical. SODA 2017 [1]

• Iacono, J., & Langerman, S. Weighted dynamic finger in binary search trees. SODA 2016. p. 672-691. http://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch49

• Alstrup, Stephen, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. "Nearest common ancestors: A survey and a new algorithm for a distributed environment." Theory of Computing Systems 37, no. 3 (2004): 441-456. [2] Tento článok je už obsadený.

• Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [3]

• Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48, no. 4 (2001): 723-760. pdf Ako udržiavať súvislé komponenty v dynamickom grafe. Dlhší článok, stačí naštudovať a prezentovať časť o súvislosti a aj tá je pomerne náročná.

• Wild, Sebastian, and Markus E. Nebel. "Average case analysis of Java 7’s dual pivot quicksort." ESA 2012, pp. 825-836. [4] Síce ide o triedenie a nie dátové štruktúry, ale tieto dve oblasti spolu úzko súvisia. Tento článok je už obsadený.

• Goel, Ashish, Sanjeev Khanna, Daniel H. Larkin, and Robert E. Tarjan. "Disjoint Set Union with Randomized Linking." SODA 2014 [5]

• Bender, Michael A., Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." [6] Zovšeboecnenie modelu cache-oblivious algoritmov.

• Arge L, Bender MA, Demaine ED, Holland-Minkley B, Munro JI. Cache-oblivious priority queue and graph algorithm applications. In Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing 2002 May 19 (pp. 268-276). ACM. [7]

• Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., & Varghese, G. (2006). An improved construction for counting Bloom filters. In Algorithms–ESA 2006 (pp. 684-695). Springer. [8] Tento článok je už obsadený.

• Song H, Dharmapurikar S, Turner J, Lockwood J. Fast hash table lookup using extended bloom filter: an aid to network processing. ACM SIGCOMM Computer Communication Review. 2005 Oct 1;35(4):181-92. [9]

Kirsch A, Mitzenmacher M. Less hashing, same performance: building a better bloom filter. ESA 2006 (pp. 456-467). Springer [10]

• Winter C, Steinebach M, Yannikos Y. Fast indexing strategies for robust image hashes. Digital Investigation. 2014 May 31;11:S27-35. [11] Tento článok je už obsadený.

• Bender, Michael A., and Martın Farach-Colton. The level ancestor problem simplified. Theoretical Computer Science 321.1 (2004): 5-12. pdf Tento článok je už obsadený.

• Belazzougui D. Linear time construction of compressed text indices in compact space. STOC 2014 [12]

• Darragh JJ, Cleary JG, Witten IH. Bonsai: a compact representation of trees. Software: Practice and Experience. 1993 Mar 1;23(3):277-91. [13] Tento článok je už obsadený.

• Gawrychowski P, Nicholson PK. Optimal Encodings for Range Top-k, Selection, and Min-Max. ICALP 2015 [14]

• Chan TM, Wilkinson BT. Adaptive and approximate orthogonal range counting. SODA 2013 [15]

• Dumitran M, Manea F. Longest gapped repeats and palindromes. MFCS 2015 [16]

• Ferragina P, Grossi R. The string B-tree: a new data structure for string search in external memory and its applications. JACM 1999 [17]

• Belazzougui D, Gagie T, Gog S, Manzini G, Sirén J. Relative FM-indexes. SPIRE 2014 [18] Tento článok je už obsadený.

• Hon WK, Shah R, Vitter JS. Space-efficient framework for top-k string retrieval problems. FOCS 2009. [19] Tento článok je už obsadený.

• Jannen, William, et al. "BetrFS: A right-optimized write-optimized file system." 13th USENIX Conference on File and Storage Technologies (FAST 15). 2015. [20] Tento článok je už obsadený.

• Gog S, Moffat A, Petri M. CSA++: Fast Pattern Search for Large Alphabets. ALENEX 2017 [21]

• Hansen TD, Kaplan H, Tarjan RE, Zwick U. Hollow Heaps. arXiv preprint arXiv:1510.06535. 2015 [22] Tento článok je už obsadený.

• Ferragina, Paolo, Raffaele Giancarlo, and Giovanni Manzini. "The engineering of a compression boosting library: Theory vs practice in BWT compression." European Symposium on Algorithms. 2006. [23] Tento článok je už obsadený.

• Gog S, Petri M. Optimized succinct data structures for massive data. Software: Practice and Experience. 2014 Nov 1;44(11):1287-314.

[24] Tento článok je už obsadený.

• Moffat A, Gog S. String search experimentation using massive data. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 2014 [25]

Články navrhnuté študentami

• Rubinchik M, Shur AM. EERTREE: an efficient data structure for processing palindromes in strings. In International Workshop on Combinatorial Algorithms 2015 Oct 5 (pp. 321-333). [26] Tento článok je už obsadený.

• Stefanov E, Papamanthou C, Shi E. Practical Dynamic Searchable Encryption with Small Leakage. In NDSS 2014 Feb (Vol. 71, pp. 72-75). [27] Tento článok je už obsadený.

Rady k hľadaniu článkov

• Podľa kľúčových slov sa články dobre hľadajú na Google Scholar. Tam okrem iného nájdete aj linky na iné články, ktoré daný článok citujú, čo môže byť dobrý zdroj ďalších informácií.

• The DBLP Computer Science Bibliography je dobrý zdroj bibtexových záznamov, ak píšete projekt alebo inú prácu v Latexu a tiež sa dá použiť na nájdenie zoznamu článkov od jedného autora alebo z jednej konferencie a podobne.

• Konferencie CPM a SPIRE sú dobrým zdrojom článkov o vyhľadávaní v texte, iné dátové štuktúry nájdete na všeobecných konferenciách pre teoretickú informatiku, napr STOC, FOCS, SODA. ESA. WADS, MFCS, ISAAC. Praktické implementácie sú námetom konferencií WAE a ALENEX.

Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň voľne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma. Pre niektoré zdroje (napr. ACM, IEEE a ďalšie) je plný text článku prístupný z fakultnej siete. Z domu sa môžete prihlásiť cez univerzitný proxy (v prehliadači nastavte automatický konfiguračný skript http://www.uniba.sk/proxy.pac ). Celý text článku (pdf) sa v mnohých prípadoch dá nájsť na webe (napr. na webstránke autora). V najhoršom prípade, ak neviete zohnať článok, ktorý k projektu alebo prezentácii veľmi potrebujete, kontaktujte ma e-mailom a môžem sa pokúsiť ho zohnať.