DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.65

Succinct List Indexing in Optimal Time

Authors: William L. Holland

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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.

Cite as

William L. Holland. Succinct List Indexing in Optimal Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ISAAC.2022.65},
  URN =		{urn:nbn:de:0030-drops-173506},
  doi =		{10.4230/LIPIcs.ISAAC.2022.65},
  annote =	{Keywords: Succinct Data Structures, Lists, Dynamic Data Structures}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.49

Recency Queries with Succinct Representation

Authors: William L. Holland, Anthony Wirth, and Justin Zobel

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

In the context of the sliding-window set membership problem, and caching policies that require knowledge of item recency, we formalize the problem of Recency on a stream. Informally, the query asks, "when was the last time I saw item x?" Existing structures, such as hash tables, can support a recency query by augmenting item occurrences with timestamps. To support recency queries on a window of W items, this might require Θ(W log W) bits. We propose a succinct data structure for Recency. By combining sliding-window dictionaries in a hierarchical structure, and careful design of the underlying hash tables, we achieve a data structure that returns a 1+ε approximation to the recency of every item in O(log(ε W)) time, in only (1+o(1))(1+ε)(ℬ+Wlog(ε^(-1))) bits. Here, ℬ is the information-theoretic lower bound on the number of bits for a set of size W, in a universe of cardinality N.

Cite as

William L. Holland, Anthony Wirth, and Justin Zobel. Recency Queries with Succinct Representation. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{holland_et_al:LIPIcs.ISAAC.2020.49,
  author =	{Holland, William L. and Wirth, Anthony and Zobel, Justin},
  title =	{{Recency Queries with Succinct Representation}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.49},
  URN =		{urn:nbn:de:0030-drops-133931},
  doi =		{10.4230/LIPIcs.ISAAC.2020.49},
  annote =	{Keywords: Succinct Data Structures, Data Streams, Sliding Dictionary}
}

Search Results

Documents authored by Holland, William L.

Succinct List Indexing in Optimal Time

Abstract

Cite as

Recency Queries with Succinct Representation

Abstract

Cite as

Thanks for your feedback!

Could not send message