Effective Structural Inference for Large XML Documents

Effective Structural Inference for Large XML Documents Jason Sankey Raymond K. Wong School of Computer Science & Engineering University of New South Wales Sydney 2052, Australia Abstract This paper investigates methods to automatically infer structural information from large XML doc- uments. Using XML as a reference format, we ap- proach the schema generation problem by applica- tion of inductive inference theory. In doing so, we re- view and extend results relating to the search spaces of grammatical inferences for large data set. We evaluate the result of an inference process using the concept of Minimum Message Length. Comprehen- sive experimentation reveals our new hybrid method to be the most effective for large documents. Finally tractability issues, including scalability analysis, are discussed. 1 Introduction Given the recent emergence of XML, there are many problems that must be solved to facilitate its most effective use. Amongst the most important of these involves addressing the differences between the new, loosely formatted data and traditional, structured data. Clearly, the ability to infer the structure of XML documents would be a very powerful tool for bridging the gap. Given such a method of infer- ence, XML information may be handled in more ef- fective ways without loosing the advantage of flex- ibility. There are still many possible approaches to the problem, and correspondingly many suitable outcomes. For this reason it is best to firstly de- rive a suitable measure for the quality of an inferred DTD. As will be seen in section 3.1, determining the relative utility of content models is a task in itself. This paper extends the hybrid method from our pre- vious work (Sankey & Wong 2001) to automatically infer structural information from large XML docu- ments. Comprehensive experimentation reveals the proposed method to be the most effective for large documents. The paper is presented in the following fashion. Section 2 provides details of previous work in this and related fields. Section 3 provides an overview of our solution method, followed by details of the inference algorithms in section 4. Section 5 includes comprehensive testing for large models and section 6 discusses the tractability considerations, followed by conclusions in section 7. 2 Previous Work The inference of structure in XML information is a relatively new area of research. However, there are several closely related topics that have been studied for a longer period. Many of these topics fall into the general field of Inductive Inference, more specif- ically the sub-field of Grammatical Inference. This sub-field is concerned with the theory and methods for learning grammars from example data. For fur- ther details concerning the field of Grammatical In- ference the reader is referred to the surveys of Pitt (Pitt 1989) and Sakakibara (Sakakibara 1997). In addition, there has also been prior research into au- tomatic recognition of document structure. Earlier attempts by (Chen 1991), (Fankhauser & Yu 1994) and (Shafer 1995) in similar problem spaces all use solutions based on heuristic methods. In each case, the generalisation step involves searching for sim- …

Content truncated to 500 words