Indexed Tree Matching with Complete Answer Representations

by Holger Meuss

Centre for Information and Language Processing (CIS),
University of Munich
Oettingenstr. 67, 80538 Munich, Germany


Abstract

This paper picks up the Tree Matching approach to integrate the
paradigm of structured documents into the field of Information
Retrieval. The concept of Tree Matching is extended by the notion of
complete answer representations (CARs), which makes it possible to
avoid the combinatorial explosion in the number of solutions (and thus
complexity).

An algorithm is presented that combines a class of Tree Matching
problems with index-based search and returns a CAR in linear time.