Nearest embedded and embedding self-nested trees - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Preprints, Working Papers, ... Year : 2017

Nearest embedded and embedding self-nested trees


Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by DAG compression. A method for quantifying the degree of self-similarity of plants through self-nested trees has been introduced by Godin and Ferraro in 2010. The procedure consists in computing a self-nested approximation, called the nearest embedding self-nested tree, that both embeds the plant and is the closest to it. In this paper, we propose a new algorithm that computes the nearest embedding self-nested tree with a smaller overall complexity, but also the nearest embedded self-nested tree. We show from simulations that the latter is mostly the closest to the initial data, which suggests that this better approximation should be used as a privileged measure of the degree of self-similarity of plants.
Fichier principal
Vignette du fichier
main.pdf (353.24 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01584078 , version 1 (08-09-2017)
hal-01584078 , version 2 (28-08-2019)



Romain Azaïs. Nearest embedded and embedding self-nested trees. 2017. ⟨hal-01584078v1⟩
167 View
141 Download



Gmail Facebook X LinkedIn More