Original title:
Implicitní reprezentace množin
Translated title:
An implicit representation of sets
Authors:
Lieskovský, Matej ; Mareš, Martin (advisor) ; Majerech, Vladan (referee) Document type: Bachelor's theses
Year:
2018
Language:
eng Abstract:
[eng][cze] The 2003 paper by Gianni Franceschini and Roberto Grossi titled "Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees" suggests a data structure that supports Insert, Find and Delete operations in O(log n) worst-case time while also being implicit and cache-oblivious. We explain the general idea of the original data structure, identify flaws and gaps in its description, and describe a reimagined version of one of the two major components of the data structure. 1Článek " Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees" od Gianniho Franceschiniho a Roberta Grossiho (2003) nastiňuje datovou strukturu, která podporuje operace Insert, Find a Delete v čase O(log n) v nejhorším případě a zároveň je implicitní a cache-oblivious. Vysvětlujeme obecné myšlenky původní datové struktury, identifikujeme vady a mezery v jejím popisu a popisujeme přetvořenou verzi jedné z jejích dvou hlavních součástí. 1
Keywords:
optimal worst-case implicit cache-oblivious search tree; optimální worst-case implicitní cache-oblivious vyhledávací strom
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/99785