Clustering query results to support keyword search on tree data

Keyword search conveniently allows users to search for information on tree data. Several semantics for keyword queries on tree data have been proposed in recent years. Some of these approaches filter the set of candidate results while others rank the candidate result set. In both cases, users might spend a significant amount of time searching for their intended result in a plethora of candidates. To address this problem, we introduce an original approach for clustering keyword search results on tree data at different levels. The clustered output allows the user to focus on a subset of the results while looking for the relevant results. We also provide a ranking of the clusters at different levels to facilitate the selection of the relevant clusters by the user. We present an algorithm that efficiently implements our approach. Our experimental results show that our proposed clusters can be computed efficiently and the clustering methodology is effective in retrieving the relevant results.