License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.21
URN: urn:nbn:de:0030-drops-78820
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7882/
Go to the corresponding LIPIcs Volume Portal

Stølting Brodal, Gerth ; Mampentzidis, Konstantinos

Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

pdf-format:
LIPIcs-ESA-2017-21.pdf (0.7 MB)

Abstract

We study the problem of computing the triplet distance between two rooted unordered trees with n labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically best algorithm is an O(nlogn) time algorithm by Brodal et al. [SODA 2013]. Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log^3 n) time, in practice it outperforms the theoretically faster O(n log n) algorithm. Both algorithms do not scale to external memory.

We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees and the second a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require O(n log n) time, and in the cache oblivious model O(n/B log_{2}(n/M)) I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and practice, for this problem.

BibTeX - Entry

@InProceedings{stltingbrodal_et_al:LIPIcs:2017:7882,
  author =	{Gerth St\olting Brodal and Konstantinos Mampentzidis},
  title =	{{Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7882},
  URN =		{urn:nbn:de:0030-drops-78820},
  doi =		{10.4230/LIPIcs.ESA.2017.21},
  annote =	{Keywords: Phylogenetic tree, tree comparison, triplet distance, cache oblivious algorithm}
}

Keywords: Phylogenetic tree, tree comparison, triplet distance, cache oblivious algorithm
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI