ABSTRACT
The focus of this chapter is on the data structures and algorithms for the efficient identification of fragments and regions in the target. Each fragment is a set of nodes bound by the ancestor-descendant relationship in the target. A general purpose indexing structure along with an indexing structure depending on the pattern P is employed for improving the performances of our approach. Fragments are merged into regions only when the similarity between P and the generated region is greater than the similarity between P and each single fragment. Target sub-trees covered by a region should be evaluated only by accessing nodes in the regions and information contained in the auxiliary indexing structures.
