Algorithm Design Paradigms in the VAT-Model
Basic data for this talk
Type of talk: scientific talk
Name der Vortragenden: Dütsch, Fabian
Date of talk: 07/03/2016
Talk language: English
Information about the event
Name of the event: Data Structures and Advanced Models of Computation on Big Data
Event period: 06/03/2016 - 11/03/2016
Event location: Schloss Dagstuhl
Abstract
Recently, Jurkiewicz and Mehlhorn observed that the cost of virtual address translation affects the practical runtime behavior of several fundamental algorithms on modern computers.In this talk, we extend their results to two dimensions and investigate the translation cost of some algorithm design paradigms.For this purpose, we analyze closest pair algorithms representing the divide and conquer, plane-sweep and randomized incremental construction paradigms in the VAT-model.Furthermore, we investigate the VAT-complexities of hashing and comparison-based searching.Finally, we verify the theoretical analyses by experimental results.Speakers from the University of Münster
| Dütsch, Fabian | Professur für Praktische Informatik (Prof. Vahrenhold) |