Fast Smallest Lowest Common Ancestor Computation Based on Stable Match
| Autor: | Guoxiang Lan, Ziyang Chen, Junfeng Zhou, Xian Tang |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Theoretical computer science
Basis (linear algebra) Semantics (computer science) Computer science computer.internet_protocol Computation Computer Science Applications Theoretical Computer Science Computational Theory and Mathematics Hardware and Architecture Node (computer science) Theory of computation ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Focus (optics) Lowest common ancestor Algorithm computer Software XML |
| Zdroj: | Journal of Computer Science and Technology. 28:366-381 |
| ISSN: | 1860-4749 1000-9000 |
| DOI: | 10.1007/s11390-013-1337-1 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink