Binary Comparative Search for SLCA problem
Shao-yu Zang, Xiaoguang Hong, Lei Liu · 2009
Nowadays, searching information exactly from XML data has become more and more important. SLCA (smallest lowest common ancestors ) is a method of getting information from XML data. The method is that we are requested to find all the nodes corresponding to the tightest subtrees in XML data, which involves the given keywords. It's a convenient method to retrieve data from XML documents for searcher,especially who is not familiar with XML knowledge. There have been many proposed algorithms solving SLCA problem through transforming XML documents into XML trees labeled with Dewey codes, such as LISA and LISA II.This paper proposes a new solution, Binary Comparative Search (BCS), targeted to XML data retrieval. Compared with LISA II, which has been proven to be better than ILE and SE. The new method dose more efficiently. In the end, LISA II and BCS are tested analytically and experimentally on data generated by XMark.