Cache oblivious algorithms for computing the triplet distance between trees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Cache oblivious algorithms for computing the triplet distance between trees. / Brodal, Gerth Stølting; Mampentzidis, Konstantinos.

25th European Symposium on Algorithms, ESA 2017. ed. / Kirk Pruhs; Christian Sohler. Vol. 87 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. p. 21:1--21:14 21 (Leibniz International Proceedings in Informatics, Vol. 87).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Brodal, GS & Mampentzidis, K 2017, Cache oblivious algorithms for computing the triplet distance between trees. in K Pruhs & C Sohler (eds), 25th European Symposium on Algorithms, ESA 2017. vol. 87, 21, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, vol. 87, pp. 21:1--21:14, 25th European Symposium on Algorithms, ESA 2017, Vienna, Austria, 04/09/2017. https://doi.org/10.4230/LIPIcs.ESA.2017.21

APA

Brodal, G. S., & Mampentzidis, K. (2017). Cache oblivious algorithms for computing the triplet distance between trees. In K. Pruhs, & C. Sohler (Eds.), 25th European Symposium on Algorithms, ESA 2017 (Vol. 87, pp. 21:1--21:14). [21] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, Vol.. 87 https://doi.org/10.4230/LIPIcs.ESA.2017.21

CBE

Brodal GS, Mampentzidis K. 2017. Cache oblivious algorithms for computing the triplet distance between trees. Pruhs K, Sohler C, editors. In 25th European Symposium on Algorithms, ESA 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. pp. 21:1--21:14. (Leibniz International Proceedings in Informatics, Vol. 87). https://doi.org/10.4230/LIPIcs.ESA.2017.21

MLA

Brodal, Gerth Stølting and Konstantinos Mampentzidis "Cache oblivious algorithms for computing the triplet distance between trees". and Pruhs, Kirk Sohler, Christian (editors). 25th European Symposium on Algorithms, ESA 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. (Leibniz International Proceedings in Informatics, Vol. 87). 2017, 21:1--21:14. https://doi.org/10.4230/LIPIcs.ESA.2017.21

Vancouver

Brodal GS, Mampentzidis K. Cache oblivious algorithms for computing the triplet distance between trees. In Pruhs K, Sohler C, editors, 25th European Symposium on Algorithms, ESA 2017. Vol. 87. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. p. 21:1--21:14. 21. (Leibniz International Proceedings in Informatics, Vol. 87). https://doi.org/10.4230/LIPIcs.ESA.2017.21

Author

Brodal, Gerth Stølting ; Mampentzidis, Konstantinos. / Cache oblivious algorithms for computing the triplet distance between trees. 25th European Symposium on Algorithms, ESA 2017. editor / Kirk Pruhs ; Christian Sohler. Vol. 87 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. pp. 21:1--21:14 (Leibniz International Proceedings in Informatics, Vol. 87).

Bibtex

@inproceedings{42e8c01a7dcf4364bc856976750a0613,
title = "Cache oblivious algorithms for computing the triplet distance between trees",
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(n log n) time algorithm by Brodal et al. (SODA 2013). Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log3 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 log2 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.",
keywords = "Cache oblivious algorithm, Phylogenetic tree, Tree comparison, Triplet distance",
author = "Brodal, {Gerth St{\o}lting} and Konstantinos Mampentzidis",
year = "2017",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.ESA.2017.21",
language = "English",
volume = "87",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "21:1----21:14",
editor = "Kirk Pruhs and Christian Sohler",
booktitle = "25th European Symposium on Algorithms, ESA 2017",
note = "25th European Symposium on Algorithms, ESA 2017 ; Conference date: 04-09-2017 Through 06-09-2017",

}

RIS

TY - GEN

T1 - Cache oblivious algorithms for computing the triplet distance between trees

AU - Brodal, Gerth Stølting

AU - Mampentzidis, Konstantinos

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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(n log n) time algorithm by Brodal et al. (SODA 2013). Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log3 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 log2 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.

AB - 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(n log n) time algorithm by Brodal et al. (SODA 2013). Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log3 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 log2 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.

KW - Cache oblivious algorithm

KW - Phylogenetic tree

KW - Tree comparison

KW - Triplet distance

UR - http://www.scopus.com/inward/record.url?scp=85030551283&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2017.21

DO - 10.4230/LIPIcs.ESA.2017.21

M3 - Article in proceedings

AN - SCOPUS:85030551283

VL - 87

T3 - Leibniz International Proceedings in Informatics

SP - 21:1--21:14

BT - 25th European Symposium on Algorithms, ESA 2017

A2 - Pruhs, Kirk

A2 - Sohler, Christian

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 25th European Symposium on Algorithms, ESA 2017

Y2 - 4 September 2017 through 6 September 2017

ER -