The Heaviest Induced Ancestors Problem Revisited

Keywords

Data structure; Orthogonal range queries; String algorithms

Abstract

We revisit the heaviest induced ancestors problem, which has several interesting applications in string matching. Let T1 and T2 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 T2 is a permutation of those in T1. A node x ∈ T1 and a node y ∈ T2 are induced, iff their subtree have at least one common leaf label. A heaviest induced ancestor query HIA(u1, u2) is: given a node u1 ∈ T1 and a node u2 ∈ T2, 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 u1 and u∗2 is an ancestor of u2. Let n be the number of nodes in both trees combined and ϵ > 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 log2 n)-word data structure with O(log n log log n) query time an O(n log n)-word data structure with O(log2 n) query time an O(n)-word data structure with O(log3+ℓ 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 (log2 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 log3 n) space and O(log3 n) query time.

Publication Date

5-1-2018

Publication Title

Leibniz International Proceedings in Informatics, LIPIcs

Volume

105

Number of Pages

201-2013

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.4230/LIPIcs.CPM.2018.20

Socpus ID

85048293636 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85048293636

This document is currently not available here.

Share

COinS