2025/09/23 by He, Meng, Kazi, Serikzhan
paper · doi:10.57717/cgt.v4i1.39
We consider an ordinal tree T on n nodes, such that each node is assigned a d-dimensional weight vector w in 1,2,...,nd where d is a constant. We study path queries as generalizations of the well-known 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 d-dimensional weight vectors generalizes the corresponding (d+1)-dimensional orthogonal range query. We solve the ancestor dominance reporting problem as a direct generalization of dominance reporting problem, in time O(lgd-1 n + k) and space of O(n lgd-2n) words, where k is the size of the output, for d >=2. We also achieve a trade-off of O(nlgd-2+eps n) words of space, with query time of O((lgd-1 n)/(lglg n)d-2+k), for the same problem, when d >= 3. We solve the path successor problem in O(nlgd-1n) words of space and time O(lgd-1+eps n) for d >= 1 and an arbitrary constant eps > 0. We propose a solution to the path counting problem, with O(n(lg n/lglg n)d-1) words of space and O((lg n/lglg n)d) query time, for d >= 1. Finally, we solve the path reporting problem in O(nlgd-1+eps n) words of space and O((lgd-1 n)/(lglg n)d-2+k) query time, for d >= 2. These results match or nearly match the best trade-offs of the respective range queries. We are also the first to solve the path successor problem even for d = 1.