Fast top k preserving query processing using two tier indexes
We present a new query processing method for text search.We extend the BMW CS algorithm to now preserve the top k results, proposing BMW CSP.We show through experiments that the method is competitive when compared to baselines. In this paper we propose and evaluate the Block Max WAND with Candidate Selection and Preserving Top K Results algorithm, or BMW CSP. It is an extension of BMW CS, a method previously proposed by us. Although very efficient, BMW CS does not guarantee preserving the top k results for a given query. Algorithms that do not preserve the top results may reduce the quality of ranking results in search systems. BMW CSP extends BMW CS to ensure that the top k results will have their rankings preserved. In the experiments we performed for computing the top 10 results, the final average time required for processing queries with BMW CSP was lesser than the ones required by the baselines adopted. For instance, when computing top 10 results, the average time achieved by MBMW, the best multi tier baseline we found in the literature, was 36.29zms per query, while the average time achieved by BMW CSP was 19.64zms per query. The price paid by BMW CSP is an extra memory required to store partial scores of documents. As we show in the experiments, this price is not prohibitive and, in cases where it is acceptable, BMW CSP may constitute an excellent alternative query processing method.
Inf. Process. Manag.