Improving the performance of identifying contributors for XML keyword search
Journal
SIGMOD Record
Journal Volume
40
Journal Issue
1
Pages
5-10
Date Issued
2011
Author(s)
Abstract
Keyword search is a friendly mechanism for users to identify desired information in XML databases, and LCA is a popular concept for locating the meaningful subtrees corresponding to query keywords. Among all the LCA-based approaches, MaxMatch [9] is the only one which could achieve the property of monotonicity and consistency , by outputting only contributors instead of the whole subtree. Although the MaxMatch algorithm performs efficiently in some cases, there is still room for improvement. In this paper, we first propose to improve its performance by avoiding unnecessary index accesses. We then speed up the process of subset detection , which is a core procedure for determining contributors. The resultant algorithm is called MinMap and MinMap +, respectively. At last, we analytically and empirically demonstrate the efficiency of our methods. According to our experiments, our two algorithms work better than the existing one, and MinMap + is particularly helpful when the breadth of the tree is large and the number of keywords grows.
Type
conference paper