Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Táto stránka sa týka školského roku 2016/17. V školskom roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://people.ksp.sk/~kuko/ds


Prezentácia: Rozdiel medzi revíziami

Z VPDS
Prejsť na: navigácia, hľadanie
(→‎Rady k hľadaniu článkov)
 
56 medziľahlých revízií od jedného používateľa nie je zobrazených.
Riadok 1: Riadok 1:
  
−
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 vyhľadávania v texte. 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. K tomuto článku môžete dostať otázku aj na skúške.
+
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==
 
==Termíny==
  
−
* Výber článku na prezentáciu do piatka 22.4. v systéme Moodle.  Každý článok môže prezentovať iba jeden študent, takže odovzdajte svôj výber radšej skôr. Kto si článok do uvedeného termínu
+
* 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.
−
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ť.
  
−
* Prezentácie na prednáškach v posledných týždňoch semestra.
+
==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==
 
==Rady k prezentácii==
  
−
* Na prezentáciu budete mať 15-20 minút, pričom tento limit bude striktne dodržiavaný. Nechystajte si teda priveľa materiálu, rátajte aspoň 1,5 minúty na slajd.
+
* 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. Prezentáciu si doneste na USB kľúči v pdf formáte alebo na vlastnom počítači (aj tak je dobré doniesť si aj pdf, keby niečo nefungovalo). Môžete použiť tabuľu, ale s mierou, lebo vysvetľovanie pri tabuli ide pomalšie.
+
* 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.
 
* 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 na slidy 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é).
+
* 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.
 
* 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ť):
 
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 niečomu  z prednášok?
+
* Ú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ť 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.
+
* 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.)
+
* 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)
 
* Záver: zhrnutie prezentácie, váš názor (čo sa Vám na článku páčilo alebo nepáčilo)
  
Riadok 27: Riadok 62:
 
* Č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 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.
 
* Č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==
 
==Príklady článkov==
Riadok 33: Riadok 67:
 
Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.  
 
Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.  
  
−
* J. Fischer, V. Heun (2006) Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. CPM 2006. <i>Novší algoritmus na hľadanie najnižšieho spoločného predka, experimentálne porovnanie. </i> [http://ab.informatik.uni-tuebingen.de/people/fischer/fischer06theoretical.pdf pdf]  
+
* Andoni A, Razenshteyn I, Nosatzki NS. Lsh forest: Practical algorithms made theoretical. SODA 2017 [http://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.5]
  
−
* Hagai Cohen and Ely Porat (2010) Fast Set Intersection and Two-Patterns Matching. LATIN 2010. [http://www.springerlink.com/content/h6un61x8mh77652p/ Pdf od vydavateľa]
+
* 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
  
−
* Y. Xu, Y. Papakonstantinou (2007) Efficient LCA based keyword search in XML data. CIKM 2007: 1007-1010 http://www.db.ucsd.edu/pubsFileFolder/298.pdf pdf] <i>Vyhľadávanie v XML pomocou LCA.</i>
+
* 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. [http://www.it-c.dk/research/algorithms/Kurser/AD/2003E/Uge6/nca.pdf] '''Tento článok je už obsadený.'''
  
−
* L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [http://bioinformatics.oxfordjournals.org/cgi/reprint/25/14/1754 pdf] <i>Aplikácia v bioinformatike.</i>
+
* Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [http://arxiv.org/pdf/1206.6982]
  
−
* Orlin, James B., et al. "A faster algorithm for the single source shortest path problem with few distinct positive lengths." Journal of Discrete Algorithms 8.2 (2010): 189-198. [http://dspace.mit.edu/openaccess-disseminate/1721.1/67886]
+
* 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. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.919&rep=rep1&type=pdf pdf] <i>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á.</i>
  
−
* Gonzalo Navarro, Yakov Nekrich: Optimal Dynamic Sequence Representations. SODA 2013: 865-876 [http://arxiv.org/pdf/1206.6982]
+
* Wild, Sebastian, and Markus E. Nebel. "Average case analysis of Java 7’s dual pivot quicksort." ESA 2012, pp. 825-836. [http://arxiv.org/pdf/1310.7409] <i>Síce ide o triedenie a nie dátové štruktúry, ale tieto dve oblasti spolu úzko súvisia.</i>  '''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 [http://www.cs.princeton.edu/~dhlarkin/papers/soda14-disjoint-set-union-with-randomized-linking.pdf]
 +
 
 +
* Bender, Michael A., Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. "Cache-Adaptive Algorithms." [http://www.cs.sunysb.edu/~rob/papers/cache-adaptive.pdf] <i>Zovšeboecnenie modelu cache-oblivious algoritmov.</i>
 +
 
 +
* 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. [http://www.cs.technion.ac.il/~itai/Courses/Cache/PQ.pdf]
 +
 
 +
* 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. [http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006b.pdf] '''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. [http://courses.cs.ut.ee/2011/algorithmics/uploads/Main/p181-song.pdf]
 +
 
 +
Kirsch A, Mitzenmacher M. Less hashing, same performance: building a better bloom filter. ESA 2006 (pp. 456-467). Springer [https://pdfs.semanticscholar.org/2f9f/f0d7ae59304bc9c6088a5664abc85e5f45bc.pdf]
 +
 
 +
* Winter C, Steinebach M, Yannikos Y. Fast indexing strategies for robust image hashes. Digital Investigation. 2014 May 31;11:S27-35. [http://www.sciencedirect.com/science/article/pii/S1742287614000097] '''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. [http://www3.cs.stonybrook.edu/~bender/newpub/2004-level.pdf pdf] '''Tento článok je už obsadený.'''
 +
 
 +
* Belazzougui D. Linear time construction of compressed text indices in compact space. STOC 2014 [http://arxiv.org/pdf/1401.0936]
 +
 
 +
* Darragh JJ, Cleary JG, Witten IH. Bonsai: a compact representation of trees. Software: Practice and Experience. 1993 Mar 1;23(3):277-91. [http://onlinelibrary.wiley.com/doi/10.1002/spe.4380230305/abstract] '''Tento článok je už obsadený.'''
 +
 
 +
* Gawrychowski P, Nicholson PK. Optimal Encodings for Range Top-k, Selection, and Min-Max. ICALP 2015 [http://arxiv.org/pdf/1411.6581]
 +
 
 +
* Chan TM, Wilkinson BT. Adaptive and approximate orthogonal range counting. SODA 2013 [https://cs.uwaterloo.ca/~tmchan/orcount_soda.pdf]
 +
 
 +
* Dumitran M, Manea F. Longest gapped repeats and palindromes. MFCS 2015 [http://arxiv.org/pdf/1511.07180]
 +
 
 +
* Ferragina P, Grossi R. The string B-tree: a new data structure for string search in external memory and its applications. JACM 1999 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.5939&rep=rep1&type=pdf]
 +
 
 +
* Belazzougui D, Gagie T, Gog S, Manzini G, Sirén J. Relative FM-indexes. SPIRE 2014 [http://jltsiren.kapsi.fi/papers/Belazzougui2014.pdf] '''Tento článok je už obsadený.'''
 +
 
 +
* Hon WK, Shah R, Vitter JS. Space-efficient framework for top-k string retrieval problems. FOCS 2009. [http://www.ittc.ku.edu/~jsv/Papers/HSV09topk.pdf] '''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. [https://www.usenix.org/system/files/conference/fast15/fast15-paper-jannen_william.pdf] '''Tento článok je už obsadený.'''
 +
 
 +
* Gog S, Moffat A, Petri M. CSA++: Fast Pattern Search for Large Alphabets. ALENEX 2017 [https://arxiv.org/pdf/1605.05404.pdf]
 +
 
 +
* Hansen TD, Kaplan H, Tarjan RE, Zwick U. Hollow Heaps. arXiv preprint arXiv:1510.06535. 2015 [https://arxiv.org/abs/1510.06535] '''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. [http://cnd.mcgill.ca/~ivan/text-compression-boosting-italians.pdf] '''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.
 +
[http://people.eng.unimelb.edu.au/sgog/optimized.pdf] '''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 [http://rsta.royalsocietypublishing.org/content/372/2016/20130135.full]
 +
 
 +
 
 +
<!--
 +
* Hagai Cohen and Ely Porat (2010) Fast Set Intersection and Two-Patterns Matching. LATIN 2010. [http://www.springerlink.com/content/h6un61x8mh77652p/ Pdf od vydavateľa] <i>Štruktúra na rýchlejšie hľadanie prienikov utriedených množín</i>
 +
 
 +
* L. Heng, R. Durbin (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [http://bioinformatics.oxfordjournals.org/cgi/reprint/25/14/1754 pdf] <i>Aplikácia BWT v bioinformatike.</i>
 +
 
 +
* Orlin, James B., et al. "A faster algorithm for the single source shortest path problem with few distinct positive lengths." Journal of Discrete Algorithms 8.2 (2010): 189-198. [http://dspace.mit.edu/openaccess-disseminate/1721.1/67886]
 +
 
 +
 
 +
* Burcsi, Peter, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. "Algorithms for jumbled pattern matching in strings." International Journal of Foundations of Computer Science 23, no. 02 (2012): 357-374. [http://arxiv.org/pdf/1102.1746.pdf] <i>Indexovanie textu aby sa dala vyhľadávať vzorka s permutovanými znakmi.</i>
 +
 
 +
* Larkin, Daniel H., Siddhartha Sen, and Robert E. Tarjan. "A back–to–basics empirical study of priority queues." ALENEX 2014 [http://arxiv.org/pdf/1403.0252v1]
 +
 
 +
* Gog S, Navarro G. Improved Single-Term Top-k Document Retrieval. ALENEX 2015 [http://dcc.uchile.cl/~gnavarro/ps/alenex15.pdf] (replaced by older Hon et al)
 +
 
 +
-->
 +
 
 +
Č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). [https://arxiv.org/pdf/1506.04862.pdf] '''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). [https://pdfs.semanticscholar.org/4eba/ad904c732b59671bf3cfb7f0d971e2ce1419.pdf] '''Tento článok je už obsadený.'''
  
 
==Rady k hľadaniu článkov==
 
==Rady k hľadaniu článkov==
Riadok 50: Riadok 151:
  
 
* [http://www.informatik.uni-trier.de/~ley/db/index.html 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.
 
* [http://www.informatik.uni-trier.de/~ley/db/index.html 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.
−
 
−
* [http://isiknowledge.com/ ISI Web of Knowledge] je oficiálna databáza hlavne časopiseckých článkov a citácií, prístupná z fakultnej siete. Menej pohodlná na použitie ako Google Scholar.
 
  
 
* 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.
 
* 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ň volne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma.  Pre niektoré zdroje
+
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 [http://www.uniba.sk/?id=1867 ď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ť.
−
(napr. ACM, IEEE a [http://www.uniba.sk/?id=1867 ď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ť.
+

Aktuálna revízia z 15:22, 18. máj 2017

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]
  • 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ť.

Zdroj: „http://compbio.fmph.uniba.sk/vyuka/vpds/index.php?title=Prezentácia&oldid=717“