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 spacetime tradeoffs:
 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:120:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770743},
ISSN = {18688969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8689},
URN = {urn:nbn:de:0030drops86898},
doi = {10.4230/LIPIcs.CPM.2018.20},
annote = {Keywords: Data Structure, String Algorithms, Orthogonal Range Queries}
}
18.05.2018
Keywords: 

Data Structure, String Algorithms, Orthogonal Range Queries 
Seminar: 

Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Issue date: 

2018 
Date of publication: 

18.05.2018 