License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.65
URN: urn:nbn:de:0030-drops-173506
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17350/
Go to the corresponding LIPIcs Volume Portal

Holland, William L.

Succinct List Indexing in Optimal Time

pdf-format:
LIPIcs-ISAAC-2022-65.pdf (0.8 MB)

Abstract

An indexed list supports (efficient) access to both the offsets and the items of an arbitrarily ordered set under the effect of insertions and deletions. Existing solutions are engaged in a space-time trade-off. On the one hand, time efficient solutions are composed as a package of data structures: a linked-list, a hash table and a tree-type structure to support indexing. This arrangement observes a memory commitment that is outside the information theoretic lower bound (for ordered sets) by a factor of 12. On the other hand, the memory lower bound can be satisfied, up to an additive lower order term, trivially with an array. However, operations incur time costs proportional to the length of the array.
We revisit the list indexing problem by attempting to balance the competing demands of space and time efficiency. We prepare the first succinct indexed list that supports efficient query and update operations. To implement an ordered set of size n, drawn from the universe {1, …, m}, the solution occupies n(log m + o(log n)) bits (with high probability) and admits all operations optimally in ?(log n/log log n) time.

BibTeX - Entry

@InProceedings{holland:LIPIcs.ISAAC.2022.65,
  author =	{Holland, William L.},
  title =	{{Succinct List Indexing in Optimal Time}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17350},
  URN =		{urn:nbn:de:0030-drops-173506},
  doi =		{10.4230/LIPIcs.ISAAC.2022.65},
  annote =	{Keywords: Succinct Data Structures, Lists, Dynamic Data Structures}
}

Keywords: Succinct Data Structures, Lists, Dynamic Data Structures
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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