Tree Pattern Aggregation for Scalable XML Data Dissemination

In this paper, we provide the first systematic study of subscription aggregation where subscriptions are specific with tree patterns (an important subclass of XPath expressions). The main challenge is to aggregate an input set of tree patterns into a smaller set of generalized tree patterns such that: (1) a given space constraint on the total size of the subscriptions is met, and (2) the loss in precision (due to aggregation) during document filtering is minimized. We propose an efficient tree-pattern aggregation algorithm that makes effective use of document distribution statistics in order to compute a precise set of aggregate tree patterns within the allotted space budget.