Title :
The ADT proximity and text proximity problems
Author :
Baeza-Yates, Ricardo ; Cunto, Walter
Author_Institution :
Dept. de Ciencias de la Comput., Chile Univ., Santiago, Chile
Abstract :
Practical text proximity problems lead to the abstract data type proximity that handles close points in the plane. Different variants and implementations of proximity are proposed and tight-complexity bounds based on information theory are derived. This problem is related to evaluating Boolean queries in large text retrieval (as in Web search engines) and to the “Sorting X+Y” problem
Keywords :
abstract data types; computational complexity; database theory; full-text databases; information theory; query processing; string matching; very large databases; ADT proximity; Boolean queries; Sorting X+Y; Web search engines; abstract data type; information theory; large text retrieval; text proximity; tight-complexity bounds; Data preprocessing; Information theory; Niobium; Web search; Writing;
Conference_Titel :
String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware
Conference_Location :
Cancun
Print_ISBN :
0-7695-0268-7
DOI :
10.1109/SPIRE.1999.796574
