Document Open Access Logo

Succinct List Indexing in Optimal Time

Author William L. Holland

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.65.pdf
  • Filesize: 0.77 MB
  • 17 pages

Document Identifiers

Author Details

William L. Holland
  • School of Computing and Information Systems, The University of Melbourne, Parkville, Australia

Funding

This work was supported by an Australian Government Research Training Program RTP Scholarship.

Acknowledgements

We acknowledge the Wurundjeri People of the Kulin Nations as traditional owners of the land on which we live and work.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2022.65

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Succinct Data Structures
  • Lists
  • Dynamic Data Structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Arne Andersson and Ola Petersson. Approximate indexed lists. Journal of Algorithms, 29(2):256-276, 1998. Google Scholar
  2. Yuriy Arbitman, Moni Naor, and Gil Segev. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In FOCS, pages 787-796. IEEE, 2010. Google Scholar
  3. Paul F Dietz. Optimal algorithms for list indexing and subset rank. In Workshop on Algorithms and Data Structures, pages 39-46. Springer, 1989. Google Scholar
  4. Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures. In STOC, pages 345-354, 1989. Google Scholar
  5. Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri. From theory to practice: Plug and play with succinct data structures. In SEA, pages 326-337. Springer, 2014. Google Scholar
  6. Alexander Golynski, J Ian Munro, and S Srinivasa Rao. Rank/select operations on large alphabets: a tool for text indexing. In SODA, volume 6, pages 368-373, 2006. Google Scholar
  7. Rodrigo González and Gonzalo Navarro. Rank/select on dynamic compressed sequences and applications. Theoretical Computer Science, 410(43):4414-4422, 2009. Google Scholar
  8. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In SODA, pages 841-850. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  9. Torben Hagerup. Highly succinct dynamic data structures. In International Symposium on Fundamentals of Computation Theory, pages 29-45. Springer, 2019. Google Scholar
  10. Meng He and J Ian Munro. Succinct representations of dynamic strings. In International Symposium on String Processing and Information Retrieval, pages 334-346. Springer, 2010. Google Scholar
  11. William L Holland, Anthony Wirth, and Justin Zobel. Recency queries with succinct representation. In 31st International Symposium on Algorithms and Computation (ISAAC 2020), 2020. Google Scholar
  12. Svante Janson. Large deviation inequalities for sums of indicator variables. arXiv preprint, 2016. URL: http://arxiv.org/abs/1609.00533.
  13. J Ian Munro and Yakov Nekrich. Compressed data structures for dynamic sequences. In Algorithms-ESA 2015, pages 891-902. Springer, 2015. Google Scholar
  14. J Ian Munro and Kaiyu Wu. Succinct data structures for chordal graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018. Google Scholar
  15. Gonzalo Navarro and Yakov Nekrich. Optimal dynamic sequence representations. In SODA, pages 865-876. SIAM, 2013. Google Scholar
  16. Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms (TALG), 10(3):1-39, 2014. Google Scholar
  17. Rasmus Pagh. Low redundancy in static dictionaries with o (1) worst case lookup time. In ICALP, pages 595-604. Springer, 1999. Google Scholar
  18. Rajeev Raman, Venkatesh Raman, and S Srinivasa Rao. Succinct dynamic data structures. In WADS, pages 426-437. Springer, 2001. Google Scholar
  19. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google Scholar
  20. Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing, 33(3):505-543, 2004. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact