N-Divided Travel Algorithm for SLCA Problem

Keyword search for smallest lowest common ancestors (SLCAs) is a convenient method to retrieve information from XML documents for most of users, especially who have no knowledge or experience on XML. There have been many proposed algorithms solving SLCA problem through transforming XML documents into XML trees labeled with Dewey codes. This paper presents a new solution, N-Divided Travel (NDT), targeted to light XML data retrieval. NDT scans Dewey codes at most once theoretically. Compared with LISA II, which has been proven to outperform ILE and SE, NDT do not need any join operations or mapping operations or extra data structures kept in memory. The new algorithm works more efficiently and fits for parallel environment after modification needed. LISA II and NDT also have been evaluated analytically and experimentally on data generated by XMark.