License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5086/
Go to the corresponding LIPIcs Volume Portal

Albers, Susanne

Modeling Real-World Data Sets (Invited Talk)

pdf-format:
3.pdf (0.2 MB)

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
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI