| 摘要 |
A method is provided for keyword proximity searching in a document database. An inverted list is constructed for each keyword in a query condition, where each list includes a location for each instance of the keyword in the document database. A plane-sweep mode is used to efficiently search the inverted lists, thereby excluding tuples that do not contribute to the output. Once an output tuple satisfying the proximity search query is detected, the plane-sweep mode is terminated. Because of the nature of the proximity search query, some tuples that are in the proximity of the output tuple also satisfy the proximity condition. Hence, the method also employs a nested-loop mode. The nested-loop mode performs a local nested loop join to enumerate all possible combinations of the keyword instances that satisfy the proximity search query which are in the neighborhood of the output tuple detected by plane-sweep mode. Upon enumerating all of these output tuples, the method switches back to the plane-sweep mode. The method alternates between these two modes of operation until all of the output tuples which satisfy the query condition are enumerated.
|
