Bolin Ding, Haixun Wang, Ruoming Jin, Jiawei Han, and Zhongyuan Wang
Query substitution is an important problem in information retrieval. Much work focuses on how to ﬁnd substitutes for any given query. In this paper, we study how to eﬃciently process a keyword query whose substitutes are deﬁned by a given taxonomy. This problem is challenging because each term in a query can have a large number of substitutes, and the original query can be rewritten into any of their combinations. We propose to build an additional index (besides inverted index) to eﬃciently process queries. For a query workload, we formulate an optimization problem which chooses the additional index structure, aiming at minimizing the query evaluation cost, under given index space constraints. We show the NP-hardness of the problem, and propose a pseudo-polynomial time algorithm using dynamic programming, as well as an (1−1/e)/4-approximation algorithm to solve the problem. Experimental results show that, with only 10% additional index space, our approach can greatly reduce the query evaluation cost.
|Published in||Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2012)|