HackerPapers

arXiv:1601.06939cs.DS

Simple and Efficient Fully-Functional Succinct Trees

Joshimar Cordova, Gonzalo Navarro

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

Abstract

The fully-functional succinct tree representation of Navarro and Sadakane (ACM Transactions on Algorithms, 2014) supports a large number of operations in constant time using $2n+o(n)$ bits. However, the full idea is hard to implement. Only a simplified version with $O(\log n)$ operation time has been implemented and shown to be practical and competitive. We describe a new variant of the original idea that is much simpler to implement and has worst-case time $O(\log\log n)$ for the operations. An implementation based on this version is experimentally shown to be superior to existing implementations.

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 Sep 2023 to Sep 2023.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. The stack monoid revisited 1 comment

    • Do succint trees like https://arxiv.org/pdf/1601.06939.pdf solve the same problems that stack monoids solve? I'll take some more time to fully digest the contents of this family of problems, but on first glance they seem closely related, with the input Balanced Parentheses being…

      qazxcvbnmView on HNParent context

Submitted to Hacker News

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