Efficient Engines for Keyword Proximity Search Benny Kimelfeld and Yehoshua Sagiv   View Paper (PDF)   Return to Paper Session 4: Keyword Search, Peer-to-Peer Systems, and Web Abstract This paper presents a formal framework for investigating keyword proximity search. Within this framework, three variants of keyword proximity search are defined. 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 fixed, but the other algorithms do not make this assumption. All the algorithms are provably efficient, 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 defined in this paper. ©2006 Association for Computing Machinery