News

  • Lars Arge and Mikkel Thorup get best paper award at ISACC 2013

  • MADALGO researchers publish in Nature Communications

  • Pankaj Agarwal appointed honorary doctor at Aarhus University

  • MADALGO Summer School 2013: Feature

  • Lars Arge in Danish TV News broadcast

  • MADALGO awarded grant from The Danish National Advanced Technology foundation

  • Danish Minister for Science, Innovation and Higher Education visits MADALGO

  • MADALGO selected as success story in a new DNRF publication

  • Lars Arge named 2012 ACM Fellow

  • Kasper receives Best Paper and Best Student Paper Award at STOC’12
__________________________


Visitors to MADALGO

__________________________


MADALGO in the media


 

CACHE-OBLIVIOUS ALGORITHMS

Unlike I/O-efficient algorithms that are efficient in terms of movements of blocks of data between main memory and external memory, cache-oblivious algorithms are algorithms designed to be efficient in terms of movements between all levels of a multilevel memory hierarchy.

More precisely, cache-oblivious algorithms are algorithms designed in the I/O-model – but without knowledge of M and B– and then analyzed as I/O-model algorithms. The beauty of the model is that since the I/O-model analysis holds for any block and memory size, it holds simultaneously on all levels of any multi-level memory hierarchy.

Thus the cache-oblivious model is a way of modeling a complicated (even unknown and/or changing) multi-level hierarchy using the simple two-level I/O-model.

Unlike the I/O-efficient algorithms area, the cache-oblivious algorithms area is relatively new and even though efficient algorithms have been developed for a number of fundamental sorting and searching problems, as well as a few geometric and graph problems, many even very fundamental problems remains open. The center considers a number of problems in the cache-oblivious model, including a number of fundamental geometric data structure and batched problems. Please refer to the centers annual reports for a discussion of obtained result.

MADALGO - Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation / Department of Computer Science / Aarhus University