Efficient query processing and index tuning using proximity scores

Abstract

In the presence of growing data, the need for efficient query processing under result quality and index size control becomes more and more a challenge to search engines. We show how to use proximity scores to make query processing effective and efficient with focus on either of the optimization goals. More precisely, we make the following contributions: • We present a comprehensive comparative analysis of proximity score models and a rigorous analysis of the potential of phrases and adapt a leading proximity score model for XML data. • We discuss the feasibility of all presented proximity score models for top-k query processing and present a novel index combining a content and proximity score that helps to accelerate top-k query processing and improves result quality. • We present a novel, distributed index tuning framework for term and term pair index lists that optimizes pruning parameters by means of well-defined optimization criteria under disk space constraints. Indexes can be tuned with emphasis on efficiency or effectiveness: the resulting indexes yield fast processing at high result quality. • We show that pruned index lists processed with a merge join outperform top-k query processing with unpruned lists at a high result quality. • Moreover, we present a hybrid index structure for improved cold cache run times.

Angesichts wachsender Datenmengen stellt effiziente Anfrageverarbeitung, die gleichzeitig Ergebnisqualität und Indexgröße berücksichtigt, zusehends eine Herausforderung für Suchmaschinen dar. Wir zeigen, wie man Proximityscores einsetzen kann, um Anfragen effektiv und effizient zu verarbeiten, wobei der Schwerpunkt auf eines der Ziele gelegt wird. Die Hauptbeiträge dieser Arbeit gliedern sich wie folgt: • Wir präsentieren eine umfassende vergleichende Analyse von Proximityscoremodellen sowie eine gründliche Analyse des Potenzials von Phrasen und passen ein führendes Proximityscoremodell für die Verwendung mit XML-Daten an. • Wir diskutieren für die präsentierten Proximityscoremodelle die Eignung zur Top-k-Anfrageverarbeitung und präsentieren einen neuen Index, der einen Inhalts- und Proximityscore kombiniert, um Top-k-Anfrageverarbeitung zu beschleunigen und die Güte zu verbessern. • Wir präsentieren ein neues, verteiltes Indextuningpaket für Term- und Termpaarlisten, das Tuningparameter mittels wohldefinierter Optimierungskriterien unter Größenbeschränkung bestimmt. Indizes können auf Effizienz oder Güte optimiert werden und sind bei hoher Güte performant. • Wir zeigen, dass gekürzte Indizes mit einem Merge Join-Ansatz Top-k Algorithmen mit ungekürzten Indizes bei hoher Güte schlagen. • Außerdem präsentieren wir eine hybride Indexstruktur, die Cold Cache-Effizienz verbessert.