University of Illinois Urbana-Champaign

Query-index co-optimization executing query templates for complex text search

Li, Rui

Content Files
Li_Rui.pdf

Permalink

https://hdl.handle.net/2142/24508

Description

Title
Query-index co-optimization executing query templates for complex text search
Author(s)
Li, Rui
Issue Date
2011-05-25T14:25:44Z
Director of Research (if dissertation) or Advisor (if thesis)
Chang, Kevin C-C.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2011-05-25T14:25:44Z
Keyword(s)
  • Information Search
  • Query Optimization
Abstract
Nowadays, many complex text search systems, such as Entity Search or Topic Search, have been proposed to allow users to retrieve fine granularity units (e.g., entities or topics) inside documents directly. As those search systems target on more complex search tasks, the traditional query processing method purely based on an inverted index can not execute those search queries efficiently. New execution algorithms and index structures need to be proposed. In this paper, we study the problem of automatically deriving an efficient execution algorithm and indexes that support the algorithm for those systems. We take a relational view of the problem and model it as optimizing a query template with views. This query template optimization problem raises new challenges including \emph{enumerating plans with views} and \emph{selecting plans for answering a template} for a query optimizer. We present a novel optimization framework with a new set of transformation rules and an efficient selection strategy to deal with those two challenges. We systematically evaluate our framework in two concrete application settings. Experiments show that: (1) The derived algorithm and indexes significantly improve the efficiency the keyword-based baseline method. (2) Our framework can automatically derive plans and indexes that are manually optimized for a system. (3) Our approach is general enough to be applied to different search systems.
Graduation Semester
2011-05
Permalink
http://hdl.handle.net/2142/24508
Copyright and License Information
Copyright 2011 Rui Li

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science