文章基本信息

标题：Reconstructing Biological and Digital Phylogenetic Trees in Parallel
本地全文：下载
作者：Ramtin Afshar ; Michael T. Goodrich ; Pedro Matias 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：3:1-3:24
DOI：10.4230/LIPIcs.ESA.2020.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.
关键词：Tree Reconstruction; Parallel Algorithms; Privacy; Phylogenetic Trees; Data Structures; Hierarchical Clustering