{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/24508"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/24508","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Query-index co-optimization executing query templates for complex text search","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Li, Rui"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chang, Kevin C-C."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-25T14:25:44Z","date_published":"2011-05-25T14:25:44Z","updated_at":"2026-07-22T22:25:23Z","subjects":["Information Search","Query Optimization"],"languages":["en"],"rights":["Copyright 2011 Rui Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/24508","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chang, Kevin C-C."]},{"key":"dc:creator","label":"Author","values":["Li, Rui"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-25T14:25:44Z","2013-05-26T10:00:20Z","2011-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Information Search","Query Optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Rui Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/24508"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-23T13:24:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 thesis_ruili.pdf: 369515 bytes, checksum: 337aa76e38037414bab780b426297a78 (MD5)","Made available in DSpace on 2011-05-25T14:25:44Z (GMT). No. of bitstreams: 2 Li_Rui.pdf: 368403 bytes, checksum: d68dcaf965ad41425adee13fa6c62d38 (MD5) license.txt: 4054 bytes, checksum: d222ac383048ffa30ad6375cdfaf0c26 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2011-05-25T14:30:09Z Item is restricted until 2013-05-25T14:29:35Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 3 Li_Rui.pdf.txt: 98495 bytes, checksum: a89f727c3f6af833cdb8e29c803a7492 (MD5) Li_Rui.pdf: 368403 bytes, checksum: d68dcaf965ad41425adee13fa6c62d38 (MD5) license.txt: 4054 bytes, checksum: d222ac383048ffa30ad6375cdfaf0c26 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z"]},{"key":"dc:title","label":"Title","values":["Query-index co-optimization executing query templates for complex text search"]}]}],"canonical_facts":{"dc:contributor":["Chang, Kevin C-C."],"dc:creator":["Li, Rui"],"dc:date":["2011-05-25T14:25:44Z","2013-05-26T10:00:20Z","2011-05"],"dc:description":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-23T13:24:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 thesis_ruili.pdf: 369515 bytes, checksum: 337aa76e38037414bab780b426297a78 (MD5)","Made available in DSpace on 2011-05-25T14:25:44Z (GMT). No. of bitstreams: 2 Li_Rui.pdf: 368403 bytes, checksum: d68dcaf965ad41425adee13fa6c62d38 (MD5) license.txt: 4054 bytes, checksum: d222ac383048ffa30ad6375cdfaf0c26 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2011-05-25T14:30:09Z Item is restricted until 2013-05-25T14:29:35Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 3 Li_Rui.pdf.txt: 98495 bytes, checksum: a89f727c3f6af833cdb8e29c803a7492 (MD5) Li_Rui.pdf: 368403 bytes, checksum: d68dcaf965ad41425adee13fa6c62d38 (MD5) license.txt: 4054 bytes, checksum: d222ac383048ffa30ad6375cdfaf0c26 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2013-05-26T10:00:20Z"],"dc:identifier":["http://hdl.handle.net/2142/24508"],"dc:language":["en"],"dc:rights":["Copyright 2011 Rui Li"],"dc:subject":["Information Search","Query Optimization"],"dc:title":["Query-index co-optimization executing query templates for complex text search"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:23Z"}