ponedeljek, 8. december 2025 Gerth Stølting Brodal: External-Memory Priority Queues and Persistent Search Trees
V ponedeljek, 8. decembra 2025, bo ob 16:00 uri izvedeno
predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE
Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.
ČAS/PROSTOR: 8. december 2025 ob 16.00 v FAMNIT-VP3.
------------------------------------------------------
PREDAVATELJ: Gerth STØLTING BRODAL
------------------------------------------------------
Gerth Stølting Brodal is a Professor at the Department of Computer Science, Aarhus University, Denmark. He received his PhD in computer science in 1997 from Aarhus University. His main research interests are the design and analysis of algorithms and data structures. He has done work on fundamental data structures, including dictionaries and priority queues, persistent data structures, computational geometry, graph algorithms, string algorithms, I/O-efficient and cache-oblivious algorithms and data structures, algorithm engineering, and computational biology.
-------------------------------------------------------------------------------------------------
NASLOV: External-Memory Priority Queues and Persistent Search Trees
-------------------------------------------------------------------------------------------------
POVZETEK:
We present recent results on priority queues and search trees in the external memory model by Aggarwal and Vitter [CACM 1988]. In this model we have an (infinite) external memory and a limited internal memory, where all computations need to be performed in internal memory. The IO cost of a computation is the number of block transfers of data between internal and external memory. In the first part of the talk we discuss the first external memory priority queue that achieves simultaniously optimal amortized internal computation cost and IO cost, where insertions are constant and deletions logarithmic. In the second part we discuss how to make a B-tree partially persistent, i.e., all previous versions of the tree are remembered, while simultaniously speeding up the amortized IO cost of insertions and deletions by a factor B^{1-ɛ̝}, for any constant ɛ̝ > 0.
The talk is based on joint work with Michael Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Casper Moldrup Rysgaard, Nodari Sitchinava, and Rolf Svenning presented at ESA 2025:
http://dx.doi.org/10.4230/LIPIcs.ESA.2025.5 and
http://dx.doi.org/10.4230/LIPIcs.ESA.2025.s
Seminar bo potekal v angleškem jeziku v predavalnici FAMNIT-VP3 s pričetkom ob 16:00 uri.
Vabljeni!
