HackerPapers

arXiv:1805.11255cs.DS

Succinct data structure for dynamic trees with faster queries

Dekel Tsur

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Navarro and Sadakane [TALG 2014] gave a dynamic succinct data structure for storing an ordinal tree. The structure supports tree queries in either $O(\log n/\log\log n)$ or $O(\log n)$ time, and insertion or deletion of a single node in $O(\log n)$ time. In this paper we improve the result of Navarro and Sadakane by reducing the time complexities of some queries (e.g.\ degree and level\_ancestor) from $O(\log n)$ to $O(\log n/\log\log n)$.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Mar 2025 to Mar 2025.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Succinct data structures 1 comment

    • Note that succinct data structures may not be faster than conventional structures if your dataset fits in memory http://www.cs.cmu.edu/~huanche1/slides/FST.pdf . Of course, for large datasets where storage access times dominate, succinct data structures win all around. In any…

      qazxcvbnmView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.