Abstract
We consider an ordinal tree T on n nodes, with each node assigned a ddimensional weight vector w in {1,2,...,n}^d, where d in N is a constant. We study path queries as generalizations of wellknown {orthogonal range queries}, with one of the dimensions being tree topology rather than a linear order. Since in our definitions d only represents the number of dimensions of the weight vector without taking the tree topology into account, a path query in a tree with ddimensional weight vectors generalize the corresponding (d+1)dimensional orthogonal range query. We solve {ancestor dominance reporting} problem as a direct generalization of dominance reporting problem, in time O(lg^{d1}{n}+k) and space of O(n lg^{d2}n) words, where k is the size of the output, for d >= 2. We also achieve a tradeoff of O(n lg^{d2+epsilon}{n}) words of space, with query time of O((lg^{d1} n)/(lg lg n)^{d2}+k), for the same problem, when d >= 3. We solve {path successor problem} in O(n lg^{d1}{n}) words of space and time O(lg^{d1+epsilon}{n}) for d >= 1 and an arbitrary constant epsilon > 0. We propose a solution to {path counting problem}, with O(n(lg{n}/lg lg{n})^{d1}) words of space and O((lg{n}/lg lg{n})^{d}) query time, for d >= 1. Finally, we solve {path reporting problem} in O(n lg^{d1+epsilon}{n}) words of space and O((lg^{d1}{n})/(lg lg{n})^{d2}+k) query time, for d >= 2. These results match or nearly match the best tradeoffs of the respective range queries. We are also the first to solve path successor even for d = 1.
BibTeX  Entry
@InProceedings{he_et_al:LIPIcs:2019:11541,
author = {Meng He and Serikzhan Kazi},
title = {{Path and Ancestor Queries over Trees with Multidimensional Weight Vectors}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {45:145:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11541},
URN = {urn:nbn:de:0030drops115415},
doi = {10.4230/LIPIcs.ISAAC.2019.45},
annote = {Keywords: path queries, range queries, algorithms, data structures, theory}
}
Keywords: 

path queries, range queries, algorithms, data structures, theory 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 