Efficient LCA Based Keyword Search in XML Data

Keyword search in XML documents based on the notion of Lowest Common Ancestors (LCAs) and modifications of it has recently gained research interest. This paper proposes an efficient algorithm called Indexed Stack to find answers to keyword queries based on XRank's semantics to LCA. The complexity of the Indexed Stack algorithm is O(kd|S1| log |S|) where k is the number of key-words in the query, d is the depth of the tree and |S1| (|S|) is the occurrence of the least (most) frequent keyword in the query. In comparison, the best worst case complexity of the core algorithms in [10] is O(kd|S|). They analytically and experimentally evaluate the Indexed Stack algorithm and the two core algorithms in.