Path and Ancestor Queries over Trees with Multidimensional Weight Vectors

Abstract

We consider an ordinal tree T on n nodes, such that each node is assigned a d-dimensional weight vector w in {1,2,...,n}^d, 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.

Our study yields the following new results. We solve the 2D ancestor dominance reporting problem as a direct generalization of 3D dominance reporting problem, in time O(lg n + k) and space of O(n lg n) words, where k is the size of the output. We solve the path successor problem in O(n lg^d-1n) words of space and time O(lg^d-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(nlg^d-1+eps n) words of space and O((lg^d-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.