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.CPM.2018.20
URN: urn:nbn:de:0030-drops-86898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8689/
Abedin, Paniz ;
Hooshmand, Sahar ;
Ganguly, Arnab ;
Thankachan, Sharma V.
The Heaviest Induced Ancestors Problem Revisited
Abstract
We revisit the heaviest induced ancestors problem, which has several interesting applications in string matching. Let T_1 and T_2 be two weighted trees, where the weight W(u) of a node u in either of the two trees is more than the weight of u's parent. Additionally, the leaves in both trees are labeled and the labeling of the leaves in T_2 is a permutation of those in T_1. A node x in T_1 and a node y in T_2 are induced, iff their subtree have at least one common leaf label. A heaviest induced ancestor query HIA(u_1,u_2) is: given a node u_1 in T_1 and a node u_2 in T_2, output the pair (u_1^*,u_2^*) of induced nodes with the highest combined weight W(u^*_1) + W(u^*_2), such that u_1^* is an ancestor of u_1 and u^*_2 is an ancestor of u_2. Let n be the number of nodes in both trees combined and epsilon >0 be an arbitrarily small constant. Gagie et al. [CCCG' 13] introduced this problem and proposed three solutions with the following space-time trade-offs:
- an O(n log^2n)-word data structure with O(log n log log n) query time
- an O(n log n)-word data structure with O(log^2 n) query time
- an O(n)-word data structure with O(log^{3+epsilon}n) query time.
In this paper, we revisit this problem and present new data structures, with improved bounds. Our results are as follows.
- an O(n log n)-word data structure with O(log n log log n) query time
- an O(n)-word data structure with O(log^2 n/log log n) query time.
As a corollary, we also improve the LZ compressed index of Gagie et al. [CCCG' 13] for answering longest common substring (LCS) queries. Additionally, we show that the LCS after one edit problem of size n [Amir et al., SPIRE' 17] can also be reduced to the heaviest induced ancestors problem over two trees of n nodes in total. This yields a straightforward improvement over its current solution of O(n log^3 n) space and O(log^3 n) query time.
BibTeX - Entry
@InProceedings{abedin_et_al:LIPIcs:2018:8689,
author = {Paniz Abedin and Sahar Hooshmand and Arnab Ganguly and Sharma V. Thankachan},
title = {{The Heaviest Induced Ancestors Problem Revisited}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {20:1--20:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8689},
URN = {urn:nbn:de:0030-drops-86898},
doi = {10.4230/LIPIcs.CPM.2018.20},
annote = {Keywords: Data Structure, String Algorithms, Orthogonal Range Queries}
}
|
Keywords: |
|
Data Structure, String Algorithms, Orthogonal Range Queries |
|
Collection: |
|
Annual Symposium on Combinatorial Pattern Matching (CPM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.05.2018 |
