Modeling Real-World Data Sets (Invited Talk)

Author Susanne Albers



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.872.pdf
  • Filesize: 202 kB
  • 1 pages

Document Identifiers

Author Details

Susanne Albers

Cite As Get BibTex

Susanne Albers. Modeling Real-World Data Sets (Invited Talk). In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, p. 872, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.872

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.

Subject Classification

Keywords
  • Worst-case analysis
  • real data sets
  • locality of reference
  • paging
  • self-organizing lists

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail