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 [10, 14, 22]. In this pa-per we propose an efficient algorithm called Indexed Stack to find answers to keyword queries based on XRank’s se-mantics to LCA [10]. 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|). We analytically and experimentally evaluate the Indexed Stack algorithm and the two core algorithms in [10]. The results show that the Indexed Stack algorithm outperforms in terms of both CPU and I/O costs other algorithms by orders of magnitud