We use cookies to improve your experience with our site.
Jun-Feng Zhou, Guo-Xiang Lan, Zi-Yang Chen, Xian Tang. Fast Smallest Lowest Common Ancestor Computation Based on Stable Match[J]. Journal of Computer Science and Technology, 2013, 28(2): 366-381. DOI: 10.1007/s11390-013-1337-1
Citation: Jun-Feng Zhou, Guo-Xiang Lan, Zi-Yang Chen, Xian Tang. Fast Smallest Lowest Common Ancestor Computation Based on Stable Match[J]. Journal of Computer Science and Technology, 2013, 28(2): 366-381. DOI: 10.1007/s11390-013-1337-1

Fast Smallest Lowest Common Ancestor Computation Based on Stable Match

  • In this paper, we focus on efficient processing of XML keyword queries based on smallest lowest common ancestor (SLCA) semantics. For a given query Q with m keywords, we propose to use stable matches as the basis for SLCA computation, where each stable match M consists of m nodes that belong to the m distinct keyword inverted lists of Q. M satisfies that no other lowest common ancestor (LCA) node of Q can be found to be located after the first node of M and be a descendant of the LCA of M, based on which the operation of locating a stable match can skip more useless nodes. We propose two stable match based algorithms for SLCA computation, i.e., BSLCA and HSLCA. BSLCA processes two keyword inverted lists each time from the shortest to the longest, while HSLCA processes all keyword inverted lists in a holistic way to avoid the problem of redundant computation invoked by BSLCA. Our extensive experimental results verify the performance advantages of our methods according to various evaluation metrics.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return