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: 2017/2018
• Thesis type: Bachelor's 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: 14.02.2018
• Date of assignment: 14.02.2018
• Confirmed by Study dept. on: 21.02.2018
• Date and time of defence: 22.06.2018 10:00
• Date of electronic submission: 18.05.2018
• Date of submission of printed version: 18.05.2018
• Date of proceeded defence: 22.06.2018
• 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. Cílem této práce je prozkoumat uvedenou strukturu (zejména její distriktovou vrstvu), napravit nedostatky v jejím fungování a posoudit praktickou použitelnost.

References

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

Bender, Michael et al.: Cache-oblivious B-trees. Proceedings of FOCS 2000.