Minimal-interval semantics  associates with each query over a document a set of intervals, called witnesses, that are incomparable with respect to inclusion (i.e., they form an antichain): witnesses define the minimal regions of the document satisfying the query. Minimalinterval semantics makes it easy to define and compute several sophisticated proximity operators, provides snippets for user presentation, and can be used to rank documents: thus, computing efficiently the antichains obtained by operations such as logic conjunction and disjunction is a basic issue. In this paper we provide the first algorithms for computing such operators that are linear in the number of intervals and logarithmic in the number of input antichains. The space used is linear in the number of antichains. Moreover, the algorithms are lazy - they do not assume random access to the input antichains. These properties make the usage of our algorithms feasible in large-scale web search engines.
|Titolo:||Efficient lazy algorithms for minimal-interval semantics|
|Autori interni:||BOLDI, PAOLO|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2006|
|Digital Object Identifier (DOI):||10.1007/11880561_12|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|