Caching Scores for Faster Query Processing with Dynamic Pruning in Search Engines

Date

2019-01-01

Author

Yafay, Erman
Altıngövde, İsmail Sengör

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

95
views

0
downloads

We propose to use a score cache, which stores the score of the k.th result of a query, to accelerate top-k query processing with dynamic pruning methods (i.e., WAND and BMW). We introduce heuristics that, for a new query, generate its subsets and probe the score cache to obtain a lower-bound on its score threshold. Our experiments show up to 8.6% savings in mean processing time for the queries that are not seen before, i.e., cannot benefit from a result cache.

URI

https://hdl.handle.net/11511/41593

DOI

https://doi.org/10.1145/3357384.3358154

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Integer Linear Programming Solution for the Multiple Query Optimization Problem Dokeroglu, Tansel; Bayir, Murat Ali; Coşar, Ahmet (2014-10-28) Multiple Query Optimization (MQO) is a technique for processing a batch of queries in such a way that shared tasks in these queries are executed only once, resulting in significant savings in the total evaluation. The first phase of MQO requires producing alternative query execution plans so that the shared tasks between queries are identified and maximized. The second phase of MQO is an optimization problem where the goal is selecting exactly one of the alternative plans for each query to minimize the tota...
Multiple query optimization with depth first branch and bound and dynamic query ordering Coşar, Ahmet; Lım, Ee Peng; Srıvastava, Jaıdeep (null; 1993-09-01) In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set of closely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query...
Query Consolidation: Interpreting a Set of Independent Queries Using a Multidatabase Architecture in the Reverse Direction Acar, Aybar Can (null; 2008-08-23) We introduce the problem of query consolidation, which seeks to interpret a set of disparate queries submitted to independent databases with a single “global” query. This problem has multiple applications, from improving database design to protecting information from a seemingly innocuous set of apparently unrelated queries. The problem exhibits attractive duality with the much-researched problem of query decomposition, which has been addressed intensively in the context of multidatabase environments: How t...
Exploiting query views for static index pruning in web search engines Altıngövde, İsmail Sengör; Ulusoy, Özgür (2009-12-01) We propose incorporating query views in a number of static pruning strategies, namely term-centric, document-centric and access-based approaches. These query-view based strategies considerably outperform their counterparts for both disjunctive and conjunctive query processing in Web search engines.
Serializability of nested transactions in multidatabases Halıcı, Uğur; Dogac, A (1997-01-01) The correctness of nested transactions for multidatabases differs from that of flat transactions in that, for nested transactions the execution order of siblings at each related site should also be consistent. In this paper we first propose a simple but powerful theory for the serializability of nested transactions in multidatabases and then a technique called Nested Tickets Method for Nested transactions (NTNT). The NTNT technique provides correctness of nested transactions in multidatabases without violat...

Citation Formats

E. Yafay and İ. S. Altıngövde, “Caching Scores for Faster Query Processing with Dynamic Pruning in Search Engines,” 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41593.