An Efficient and Practical Algorithm for the Many-Keyword Proximity Problem by Offsets.

One of the most important relevance factors in the Web search context is the proximity score, i.e., how close the keywords appear together in a given document. A basic proximity score is given by the size of the smallest range containing all the keywords in the query. We generalize the proximity score to include many practically important cases and present an O(n log k) time algorithm for the generalized problem, where k is the number of keywords and n is the number of occurrences of the keywords in a document. [ABSTRACT FROM AUTHOR]