Dynamic Tree Cross Products

摘要

Range searching over tree cross products - a variant of classic range searching - recently has been introduced by Buchsbaum et al. (Proc. 8th ESA, vol. 1879 of LNCS, pp. 120-131, 2000). A tree cross product consist of hyperedges connecting the nodes of trees T_1, ... , T_d. In this context, range searching means to determine all hyperedges connecting a given set of tree nodes. Buchsbaum et al. describe a data structure which supports, besides queries, adding and removing of edges; the tree nodes remain fixed. In this paper we present a new data structure, which additionally provides insertion and deletion of leaves of T_1, ... , T_d; it combines the former approach with a novel technique of using search trees superimposed over ordered list maintenance structures. The extra cost for this dynamization is roughly a factor of O(log n/log log n). The trees being dynamic is especially important for maintaining hierarchical graph views, a problem that can be modeled as tree cross product. Such views evolve from a large base graph by the contraction of subgraphs defined recursively by an associated hierarchy. The graph view maintenance problem is to provide methods for refining and coarsening a view. In previous solutions only the edges of the underlying graph were dynamic; with the application of our data structure, the node set becomes dynamic as well.