Published in

2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX), p. 84-97

DOI: 10.1137/1.9781611972900.9

Links

Tools

Export citation

Search in Google Scholar

Succinct Trees in Practice

Proceedings article published in 2010 by Diego Arroyuelo, Rodrigo Cánovas ORCID, Gonzalo Navarro, Kunihiko Sadakane
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Green circle
Published version: archiving allowed
Data provided by SHERPA/RoMEO

Abstract

We implement and compare the major current techniques for representing general trees in succinct form. This is impor- tant because a general tree of n nodes is usually represented in pointer form, requiring O(nlog n) bits, whereas the suc- cinct representations we study require just 2n + o(n) bits and carry out many sophisticated operations in constant time. Yet, there is no exhaustive study in the literature comparing the practical magnitudes of the o(n)-space and the O(1)-time terms. The techniques can be classified into three broad trends: those based on BP (balanced parenthe- ses in preorder), those based on DFUDS (depth-first unary degree sequence), and those based on LOUDS (level-ordered unary degree sequence). BP and DFUDS require a balanced parentheses representation that supports the core operations findopen, findclose, and enclose, for which we implement and compare three major algorithmic proposals. All the tree rep- resentations require also core operations rank and select on bitmaps, which are already well studied in the literature. We show how to predict the time and space performance of most variants via combining these core operations, and also study some tree operations for which specialized im- plementations exist. This is especially relevant for a recent proposal (K. Sadakane and G. Navarro, SODA'10) which, although belonging to class BP, deviates from the main tech- niques in some cases in order to achieve constant time for the widest range of operations. We experiment over vari- ous types of real-life trees and of traversals, and conclude that the latter technique stands out as an excellent practi- cal combination of space occupancy, time performance, and functionality, whereas others, particularly LOUDS, are still interesting in some limited-functionality niches.