An efficient approach for mining Top-k high utility specialized query expansions on social tagging systems

A specialized query expansion consists of a set of keywords, which is used to reduce the size of search results in order to help users find the required data conveniently. The utility of a specialized query expansion represents the qualities of the top-N high quality objects matching the expansion. Given the search results of a keyword query on social tagging systems, we want to find k specialized query expansions with the highest utilities without redundancy. Besides, the discovered expansions are guaranteed to match at least N objects. We construct a tree structure, called an UT-tree, to maintain the tag sets appearing in the search results for generating the specialized query expansions. We first propose a depth-first approach to find the top-k high utility specialized query expansions from the UT-tree. For further speeding up this basic approach, we exploit the lower bound and upper bound estimations of utilities for a specialized query expansion to reduce the size of the constructed UT-tree. Only the tag sets of objects which are possibly decide the top-k high utility specialized query expansions need to be accessed and maintained. By applying this strategy, we propose another faster algorithm. The experiment results demonstrate that the proposed algorithms work well on both the effectiveness and the efficiency.