Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.872
URN: urn:nbn:de:0030-drops-50865
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5086/
Albers, Susanne
Modeling Real-World Data Sets (Invited Talk)
| pdf-format: |
|
Abstract
Traditionally, the performance of algorithms is evaluated using worst-case analysis. For a number of problems, this type of analysis gives overly pessimistic results: Worst-case inputs are rather artificial and do not occur in practical applications. In this lecture we review some alternative analysis approaches leading to more realistic and robust performance evaluations.Specifically, we focus on the approach of modeling real-world data sets. We report on two studies performed by the author for the problems of self-organizing search and paging. In these settings real data sets exhibit locality of reference. We devise mathematical models capturing locality. Furthermore, we present combined theoretical and experimental analyses in which the theoretically proven and experimentally observed performance guarantees match up to very small relative errors.
BibTeX - Entry
@InProceedings{albers:LIPIcs:2015:5086,
author = {Susanne Albers},
title = {{Modeling Real-World Data Sets (Invited Talk)}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {872--872},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5086},
URN = {urn:nbn:de:0030-drops-50865},
doi = {10.4230/LIPIcs.SOCG.2015.872},
annote = {Keywords: Worst-case analysis, real data sets, locality of reference, paging, self-organizing lists}
}
| Keywords: | Worst-case analysis, real data sets, locality of reference, paging, self-organizing lists | |
| Seminar: | 31st International Symposium on Computational Geometry (SoCG 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 12.06.2015 |
