UCLA

A query result of an XML keyword search is usually defined as a set of the most specific elements containing all query keywords. Search systems find the query result by considering the combinations of all elements in the inverted indexes of the query keywords. However, we conclude that it is not necessary to consider the combinations of all the elements, when an “effective result depth” (which represents how deeply nested elements are eligible for the query result) is given. This paper describes a way to construct partitioned indexes on the effective result depth, guaranteeing that the combinations of elements in different partitions never produce result elements. Therefore, search systems can find query results by considering only combinations of elements in the same partitions. Partitioned indexes are adaptable; when an effective result depth is changed, partitioned indexes constructed on the original depth can be used efficiently without being reconstructed physically on the changed depth. The experimental results show that our approach worked quite well in most cases.