JavaScript is disabled for your browser. Some features of this site may not work without it.
Expressiveness and Performance of Full-Text Search Languages

Author
Botev, Chavdar; Amer-Yahia, Sihem; Shanmugasundaram, Jayavel
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.
Date Issued
2005-03-14Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2005-1984
Type
technical report