Skip to main content


eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Expressiveness and Performance of Full-Text Search Languages
Authors: Botev, Chavdar
Amer-Yahia, Sihem
Shanmugasundaram, Jayavel
Keywords: computer science
technical report
Issue Date: 14-Mar-2005
Publisher: Cornell University
Abstract: We study the expressiveness and performance of full-text search languages. Our main motivation is to provide a formal basis for comparing such languages and todevelop a model for full-text search that can be tightly integrated withstructured search. We develop a formal model for full-text search based on thepositions of tokens (words) in the input text, and develop a full-text calculus(FTC) and a full-text algebra (FTA) with equivalent expressive power. Thissuggests a notion of completeness for full-text search languages and can be usedas a basis for a study of their expressiveness. We show that existing full-textlanguages are incomplete and develop {\tt COMP}, a complete full-text searchlanguage. We also identify practical subsets of {\tt COMP} that are morepowerful than existing languages, develop efficient query evaluation algorithmsfor these subsets, and study experimentally their performance.
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
TR2005-1984.pdf348.94 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us