Fast top-k preserving query processing using two-tier indexes |
| |
| Institution: | 1. Institute of Computing, Federal University of Amazonas –Av. Gen. Rodrigo Otávio, 3000, Manaus 69077-000, AM, Brazil;2. Neemu S/A, Av. Via Lactea, 1374, Manaus 69060-020, AM, Brazil;1. Universidad Técnica Federico Santa María, Santiago, Chile;2. Universidad de Santiago de Chile, Santiago, Chile;3. CONICET, Universidad Nacional de San Luis, Argentina;4. Software Competence Center Hagenberg, Austria;1. Qatar Computing Research Institute, HBKU, Doha, Qatar;2. Department of Computer Science and Engineering, College of Engineering, Qatar University, Doha, Qatar;1. School of Library and Information Science, Kent State University, 314 University Library Kent, OH 44242-0001, United States;2. School of Informatics and Computing, Indiana University Bloomington, 1320 East 10th Street, Bloomington, IN 47405-3907, United States |
| |
| Abstract: | 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.29 ms per query, while the average time achieved by BMW-CSP was 19.64 ms 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
