An implicit representation of sets

• Thesis title in Czech: Implicitní reprezentace množin
• Thesis title in English: An implicit representation of sets
• Key words: optimální worst-case implicitní cache-oblivious vyhledávací strom
• English key words: optimal worst-case implicit cache-oblivious search tree
• Academic year of topic announcement: 2019/2020
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: Mgr. Matej Lieskovský - assigned and confirmed by the Study Dept.
• Date of registration: 10.04.2020
• Date of assignment: 17.04.2020
• Confirmed by Study dept. on: 29.04.2020
• Date and time of defence: 08.07.2020 09:00
• Date of electronic submission: 28.05.2020
• Date of submission of printed version: 28.05.2020
• Date of proceeded defence: 08.07.2020
• Opponents: Mgr. Vladan Majerech, Dr.

Guidelines

Francheschini a Grossi publikovali v roce 2003 návrh datové struktury pro reprezentaci uspořádaných množin, která je současně implicitní, časově optimální a I/O-optimální v cache-oblivious modelu. Jejich článek ovšem pomíjí mnoho důležitých detailů a obsahuje četné drobné chyby. Matej Lieskovský ve své předchozí bakalářské práci prozkoumal a opravil distriktovou vrstvu této struktury. Cílem této práce je prozkoumat zbývající kyblíkovou vrstvu uvedené struktury, napravit nedostatky v jejím fungování a posoudit praktickou použitelnost celé struktury.

References

Gianni Franceschini and Roberto Grossi: Optimal worst-case operations for implicit cache-oblivious search trees. Workshop on Algorithms and Data Structures 2003.

Gianni Franceschini and Roberto Grossi: Optimal implicit and cache-oblivious dictionaries over unbounded universes. Full version, 2003.

Gianni Franceschini, Roberto Grossi, J. Ian Munro, and Linda Pagli: Implicit B-trees: New results for the dictionary problem. In IEEE Symposium on Foundations of Computer Science (FOCS), 2002.