Approximation of trees by self-nested trees

Romain Azaïs, Jean-Baptiste Durand, Christophe Godin

Abstract

The class of self-nested trees presents remarkable compression properties because of the systematic repetition of subtrees in their structure. In this paper, we provide a better combinatorial characterization of this specific family of trees. In particular, we show from both theoretical and practical viewpoints that complex queries can be quickly answered in self-nested trees compared to general trees. We also present an approximation algorithm of a tree by a self-nested one that can be used in fast prediction of edit distance between two trees.
BibTeX
@inproceedings{azais2018approximation,
  author = {Romain Azaïs and Jean-Baptiste Durand and Christophe Godin},
  title = {{Approximation of trees by self-nested trees}},
  booktitle = {HAL},
  year = {2018},
  doi = {10.48550/arxiv.1810.10860},
}

Loading related content...

Figure