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.SEA.2017.2
URN: urn:nbn:de:0030-drops-76336
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7633/
Go to the corresponding LIPIcs Volume Portal

Farach-Colton, Martin

Dictionaries Revisited

pdf-format:
LIPIcs-SEA-2017-2.pdf (0.2 MB)

Abstract

Dictionaries are probably the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extract-min. Given their centrality to both the theory and practice of data structures, surprisingly basic questions about them remain unsolved and sometimes even unposed. This talk focuses on questions that arise from the disparity between the way large-scale dictionaries are analyzed and the way they are used in practice.

BibTeX - Entry

@InProceedings{farachcolton:LIPIcs:2017:7633,
  author =	{Martin Farach-Colton},
  title =	{{Dictionaries Revisited}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7633},
  URN =		{urn:nbn:de:0030-drops-76336},
  doi =		{10.4230/LIPIcs.SEA.2017.2},
  annote =	{Keywords: B+-trees, file system, write optimization}
}

Keywords: B+-trees, file system, write optimization
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

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