A Concise Labeling Scheme for XML Data

In this paper, we look at the problem of assigning labels to nodes of a dynamic XML tree such that the labels encode all ancestor-descendant relationships between the nodes and the document-order between the nodes. Such labeling facilitates efficient XML query processing. A number of labeling schemes have been designed for this task. These schemes can be broadly classified into (1) Static Labeling Schemes and (2) Dynamic Labeling Schemes. While static schemes generate short labels, their performance degrades in update intensive environments. Dynamic schemes have nice update performance, but their size of labels is high. A good labeling scheme should generate concise labels and should perform better when there are arbitrary updates on the XML tree. In this paper, we present a new labeling scheme called Sector-based Labeling (SL) scheme which labels nodes with sectors. We analyze the proposed SL scheme and show that it generates smaller labels than the static schemes and has update performance as good as the dynamic schemes. We conduct experiments and show that the obtained results substantiate our analyses.