text: In contrast to XML query languages as e.g. XPath which require knowledge on the query language as well as on the document structure, keyword search is open to anybody. As the size of XML sources grows rapidly, the need for efficient search indices on XML data that support keyword search increases. In this paper, we present an approach of XML keyword search which is based on the DAG of the XML data, where repeated substructures are considered only once, and therefore, have to be searched only once. As our performance evaluation shows, this DAG-based extension of the set intersection search algorithm[1], [2], can lead to search times that are on large documents more than twice as fast as the search times of the XML-based approach. Additionally, we utilize a smaller index, i.e., we consume less main memory to compute the results.
  @cite_9: Keyword search for smallest lowest common ancestors (SLCAs)in XML data has recently been proposed as a meaningful way to identify interesting data nodes inXML data where their subtrees contain an input set of keywords. In this paper, we generalize this useful search paradigm to support keyword search beyond the traditional AND semantics to include both AND and OR boolean operators as well. We first analyze properties of the LCA computation and propose improved algorithms to solve the traditional keyword search problem (with only AND semantics). We then extend our approach to handle general keyword search involving combinations of AND and OR boolean operators. The effectiveness of our new algorithms is demonstrated with a comprehensive experimental performance study.
summary: @cite_9 presents an anchor-based approach to compute the SLCA. From the set of current nodes of each relevant keyword list, they search the so-called anchor, i.e., that node that is closest to all current nodes. As soon as an anchor is identified, they try to exchange each node @math of each other keyword list @math by the next node next( @math ) of @math , in order to check, whether next( @math ) is closer to the anchor than @math and whether next( @math ) defines a new anchor. Finally, the set of anchor nodes form the set of LCA candidates that do not have another LCA candidate child is then reduced to the set of SLCA nodes.