Efficient Engines for Keyword Proximity Search.
Benny Kimelfeld, Yehoshua Sagiv · International Workshop on the Web and Databases · 2005
This paper presents a formal framework for investigating keyword proximity search. Within this framework, three variants of keyword proximity search are dened. For each variant, there are algorithms for enumerating all the results in an arbitrary order, in the exact order and in an approximate order. The algorithms for enumerating in the exact order make the inevitable assumption that the size of the query (i.e., the number of keywords) is xed, but the other algorithms do not make this assumption. All the algorithms are provably ecien t, that is, run with polynomial delay. The algorithms for enumerating in an approximate order are provably correct for a natural notion of approximation that is dened in this paper.