Abstract:
Keyword proximity searching in a document database according to a query condition initiates with generation of inverted lists having a location for each instance of the keyword in the document database. A plane-sweep mode is used to efficiently search the inverted lists until an output tuple satisfying proximity criteria in the search query is detected. The method then shifts to a nested-loop search mode 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 in plane-sweep mode. The method alternates between these two modes of operation until all of the output tuples satisfying the query condition are enumerated.

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to a method for keyword proximity searching in a document database, and more particularly, the present invention optimizes CPU-time and reduces I/O operations associated with keyword proximity searching of a document database. 
     BACKGROUND OF THE INVENTION 
     Keyword proximity searching is an important tool for browsing and selecting relevant documents from a large document database. Proximity searching deals with the location and the distance relationship among keywords in a document. For example, the following is a typical keyword proximity search query: given a set of n keywords, find the documents that have a collection of keywords that are within r words from each other. More generally, keyword proximity search may have the form: find the documents in the database that contain all the n search keywords appearing in the same paragraph, page, or within r words, paragraphs, or pages, from each other by implementing a plane sweep search. 
     Algorithms for answering proximity search queries for a collection of point objects are covered extensively in the literature. Many of the algorithms described in the literature cover the topic from a computational geometry perspective, where the main interest is to develop algorithms that optimize the execution time (i.e., CPU-time) in terms of the input parameters of the problem. On the other hand, when large collections of objects are involved the disk-I/O cost is significant. As a result, from a database perspective, in addition to optimizing CPU-time, the interest is also in reducing the disk-I/O cost for answering such queries. 
     SUMMARY OF THE INVENTION 
     The present invention presents a new algorithm for answering keyword proximity search where the words represent objects that are points in the one-dimensional space. The algorithm takes into consideration the fact that the number of words in a document database is typically very large. Hence, it tries to reduce the overhead induced from multiple-retrieval of objects from auxiliary storage. In contrast to other algorithms in the literature, the performance of this new algorithm is optimal. As will be explain below, the overall performance of the algorithm is proportional to the total sizes of the input inverted lists and the size of the reported output tuples. 
     Assume a given collection of n keywords c 1  . . . c n , where each keyword has associated with it a list of instances. Each instance in the list contains the location of the keyword in the document database. For example, let the keyword c 1  be “dog”, c 2  be “cat”, and c 2  be “rat” (i.e., n=3), and the instances correspond to the occurrences of the keywords in various locations of the documents in the database. For example, the instances of the keyword “cat” are &lt;doc1, 15&gt;, &lt;doc1, 123&gt;, &lt;doc2, 25&gt;, and &lt;doc7, 115&gt;which implies that the keyword “cat” appears in document doc1 at locations 15 and 123, in document doc2 at location 25, and in document doc7 at location 115, where doc1, doc2, and doc7 are unique identifies for documents 1, 2, and 7. It should also be noted that page information can be added as part of the location of the word in the document. This helps in extending the proximity search to refer to pages (e.g., find the documents that have the keywords dog and cat within the same page). 
     The instances of a given keyword are stored in a linear list, where each entry in the list identifies the relative location of the keyword instance as well as an identifier to retrieve the rest of the keyword&#39;s description. This is also referred to as an inverted list. Keyword instances are stored in inverted lists so that a given keyword can easily be found in one or more documents. Assume that the entries in a given list (that corresponds to the locations of instances of a given keyword) are sorted according to their location. This is a reasonable assumption if we consider that the lists are constructed by traversing the document and inserting, for each keyword that appears in the documents, the entry (doc-id,pos) at the end of the list for the keyword. As an example, the following is possible entry in the inverted list for the keyword “complex” which appears in documents doc 1 , doc 2 , and doc 4 : [“complex”]—(doc 1 , 6), (doc 1 , 20), (doc 1 , 50), (doc 2 , 30), (doc 4 , 100), (doc 4 , 130). In this case, the list will be sorted in ascending order of the positions of the keyword in the database. For the purposes of the present invention it does not matter whether the elements are sorted in either ascending or descending order. 
     In contrast to a conventional nested loop searching algorithm, the goal of the present invention is to reduce the number of times the lists are traversed. The keyword proximity search algorithm of the present invention is based on a plane-sweep approach and performs like a merge join algorithm while trying to take advantage of the nature of the proximity condition. This is especially important for large documents and large document databases where the number of instances in each keyword entry is large and the lists of instances cannot be assumed to fit in main memory. 
     Accordingly, a proximity search algorithm is proposed for answering proximity search queries in a document database. The present invention alternates between two modes of operation to find the matching output tuples. 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 algorithm switches to 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 in the neighborhood of the output tuple detected by plane-sweep mode. Upon enumerating all of these output tuples, the algorithm switches back to the plane-sweep mode. 
     For a more complete understanding of the invention, its objects and advantages refer to the following specification and to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram illustrating a keyword proximity search query of a document database in accordance with the present invention; and 
     FIG. 2 is a diagram illustrating a plane-sweep search of the constructed inverted lists in accordance with the present invention; 
     FIG. 3 is a diagram illustrating how a search interval in updated for during a plane-sweep search in accordance with the present invention; and 
     FIG. 4 is a diagram illustrating a nested-loop search of the inverted lists in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 illustrates a keyword proximity search query, where the proximity search criterion is composed of five keywords a, b, c, d, and e (i.e., n=5) and a desired proximity distance, r, between each of the keywords. The horizontal lines  12  represent the inverted lists for each keyword while the X&#39;s on the lines show the locations  14  of the instances of each keyword. For simplicity, the inverted lists are each labeled a, b, c, d, and e, respectively. Notice that for a given document no two keywords can appear in the same location. In FIG. 1, all the instances a 2 , b 2,  b 3 , c 1 , c 2 , d 2 , and e 2  are within the desired proximity distance  16  from each other, and thus satisfy the proximity search criterion. In order to satisfy the proximity search query, all the possible instance-combinations from the above list have to be enumerated. For instance, &lt;, a 2,  b 2 , c 1 , d 2 , e 2 &gt;, &lt;a 2 , b 3 , c 1 , d 2 , e 2 &gt;, &lt;, a 2,  b 2 , c 2 , d 2 , e 2 &gt; and &lt;a 2 , b 3 , c 2 , d 2 , e 2 &gt; are four of the resulting output tuples. Further in the lists, the instance-combination &lt;a 4 , b 5 , c 4 , d 3 , e 4 &gt; forms another output tuple of the query. 
     The keyword proximity search algorithm of the present invention processes the lists in two different modes of operation: a plane-sweep mode and a nested-loop mode. Initially, a vertical plane starts at the leftmost of each list (i.e., at location 0, assuming that the locations of instances in the list goes from left to right). The plane sweep mode advances the sweeping vertical plane until an output tuple that satisfies the proximity search condition is located. Referring to FIG. 2, plane-sweep mode will take place until it encounters a first output tuple  20 , &lt;a 2 , b 2 , c 1 , d 2 , e 2 &gt;. Once such an output tuple is found, the algorithm switches into a nested-loop mode. The nested-loop mode is intended to check for and generate all the output tuples, if any, that immediately follow the first output tuple  20 . This is achieved by advancing the plane-sweep incrementally through the instances that immediately follow the first output tuple. For example, &lt;a 2 , b 3 , c 1 , d 2 , e 2 &gt;, &lt;, a 2,  b 2 , c 2 , d 2 , e 2 &gt; and &lt;a 2 , b 3 , c 2 , d 2 , e 2 &gt; are three output tuples enumerated by the nested-loop mode. Upon completion, the algorithm switches back to the plane-sweep mode which results in advancing the plane-sweep until a next output tuple  22  is detected, e.g., till the output tuple &lt;a 4 , b 5 , c 4 , d 3 , e 4 &gt; is detected as shown in FIG.  2 . This process continues until all the output tuples are detected and at least one of the lists is entirely traversed by the plane-sweep. At this point, the algorithm terminates. It should be noted that by using the plane-sweep approach, the algorithm processes all the lists in one direction (from left to right) and does not need to backtrack in any of the lists. 
     A more detailed description follows which illustrates how the plane-sweep mode and the nested-loop mode traverse the inverted lists. First, each of the inverted lists are maintained in an array type data structure. The algorithm also maintains n pointers p 1  . . . p n , where p i  points to the next instance of the keyword in the list c i . Prior to beginning execution of the plane-sweep mode, p 1  . . . p n  point to the first instance of each list. During one iteration, the algorithm designates one of the lists as the start-list (termed c s ) and uses this list&#39;s corresponding pointer p s  to access the next instance in c s . Next, the algorithm proceeds to process list c s+1 mod n,  to retrieve its next instance, etc. An iteration is completed once algorithm returns to the start-list or when an exception arises, e.g., when an iteration is restarted by reassigning another list to the start-list c s . 
     The plane-sweep mode processes the incoming instances from each list as shown in FIG.  3 . First, the algorithm assigns list a to be the start-list and retrieves element a 1 . For a 1  to be a part of an output tuple, keyword instances from all of the other lists have to be within the desired proximity distance, r, from a 1 . In order to detect this, the algorithm constructs a search interval 32, where a 1  lies in the middle of the search interval, v. The search interval is further defined as two equidistant segments, where each has a length equal to the desired proximity distance. When the algorithm processes the next list, it retrieves b 1  and determines the distance between a 1  and b 1 . In this case, b 1  happens to fall within the search interval, and thus b 1  is part of a candidate output tuple. In order to guarantee that the upcoming instances that fall within the search interval satisfy the search proximity criterion, the length of search interval is adjusted as shown at 34 based on the location of b 1 . When b 1  lies within the segment on the left side of a 1 , then the length of the other segment is reduced such that the distance from b 1  to the end of that segment is equal to the desired proximity distance. In this way, the search interval will only capture upcoming instances that lie within the desired proximity distance from both a 1  and b 1 . 
     Similarly, the instance c 1  of list c is determined to fall with the adjusted search interval. Therefore, c 1  also becomes part of a candidate output tuple and the search interval is updated accordingly. However, d 1  is outside and to the left of the search interval at 36 and hence is discarded. The next instance (d 2 ) of the same list is then retrieved. Since d 2  is also outside of the search interval, the algorithm is restarted with list d as the start-list. 
     Again, the algorithm constructs a search interval 32 for the current iteration, where d 2  lies in the middle of the search interval. In the new iteration, with d as the start-list, the other lists will be visited in the following order: e, a, b, c. When the algorithm processes the next list, e 1  is determined to lie outside and to the left of the new search interval. As a result, e 1  is discarded and e 2  is retrieved. Because e 2  lies within the search interval, it becomes part of a new candidate output tuple. In addition, the search interval is updated based on the location of e 2  as shown at 38. Next, instance a 1  is re-examined. Unlike the first iteration, a 1  is outside and to the left of the new search interval and thus is discarded. However, a 2  is retrieved and it does lie within the search interval. Therefore, a 2  also becomes part of the candidate output tuple and the search interval is updated accordingly. The algorithm processes lists b and c similarly as shown in FIG.  3 . At this point, the whole iteration is complete and the candidate tuple &lt;a 2 , b 2 , c 1 , d 2 , e 2 &gt; qualifies as an output tuple. 
     Next, the algorithm of the present invention switches to the nested-loop searching mode. It should be noted that the case where the keyword instances are clustered with high frequencies around each other, as in FIG. 2, is an uncommon occurrence in the typical document database. It is also instructive to mention that the plane-sweep searching mode, as described above, cannot properly handle this case. In other words, all of the possible output tuples will not be enumerated. In order to enumerate all of the possible output tuples, it is necessary to employ the nested-loop searching mode. 
     The status of the algorithm at the end of plane-sweep mode is passed as input to the nested-loop mode. This status is represented by the pointers p 1  . . . p n  that correspond to lists c 1  . . . c n , respectively, where the pointers point to the keyword instances in the lists that form an output tuple. The output n-tuple is x 1  . . . x n . An n-way nested loop is executed to find and enumerate all the tuples that satisfy the query condition. Each iteration of the nested loop produces an output tuple, except for the last iteration in each of the nested loops. As a result, the cost of the nested loop is asymptotically covered by the number of output tuples produced. In addition, at each iteration of the nested loop, the search interval is updated according to the current set of keyword instances that form the active set of instances of the current iteration. However, the CPU cost of maintaining the interval is very minimal and it does not involve any I/O cost. 
     A more detailed explanation of the nested-loop searching mode is provided in relation to FIG.  4 . The nested-loop mode starts with the current instance x 1  in list c 1  (e.g., a 2  in FIG.  4 ). Again, the keyword instances of an output tuple must all be within the desired proximity distance, r, from a 2 . Therefore, a search interval, v, is constructed, where a 2  lies in the middle of the search interval. Each of the other lists are then scanned to identify output tuples. 
     First, the next instance, b 3 , of the next list is retrieved and then determined to fall within the search interval. In this case, b 3  falls within the search interval, and thus b 3  is part of a candidate output tuple. As previously described, the search interval is then updated based on the location of b 3 . Next, the current instance for each of the other lists (i.e., c 1 , d 2  and e 2 ) are then evaluated. For each instance that falls within the search interval, the interval is updated based on the location of that instance. If any instance does not fall within the search interval, then processing moves to the next instance of the next list (i.e., b 4 ). If each of the current instances falls within the search interval, then the candidate output tuple qualifies as an output tuple. In this case, candidate tuple &lt;a 2 , b 3 , c 1 , d 2 , e 2 &gt; qualifies as an output tuple as shown in FIG.  4 . 
     Since an output tuple was identified, the nested-loop processing continues for the last list until an iteration fails to produce an output tuple. In other words, check if e 3  falls within the search interval. Since e 3  falls outside of the search interval, processing moves to the previous nested loop (i.e., the loop for list d). Again, the next instance, d 3 , for this list falls outside the search interval and processing moves to the previous nested loop (i.e., the loop for list c). In this case, the next instance, c 2 , falls within the search interval, and thus an output tuple is enumerated, &lt;a 2 , b 3 , c 2 , d 2 , e 2 &gt;. Since the next instance, c 3 , is determined to be outside the search interval, the nested-loop processing is completed for instance b 3 . At this point, the next instance, b 4 , is retrieved and the search interval is reconstructed around a 2 . However, this next instance, b 4 , falls outside the search interval and processing moves to the next list, c. 
     Similar nested-loop processing occurs for each of remaining lists (i.e., c, d, and e). If all of the possible n-tuples that contain a 2  are enumerated, then the nested-loop mode reports three additional output tuples, namely &lt;a 2 , b 2 , c 2 , d 2 , e 2 &gt;, &lt;a 2 , b 3 , c 1 , d 2 , e 2 &gt;and &lt;a 2 , b 3 , c 2 , d 2 , e 2 &gt;. 
     Upon completion of the nested loop mode to enumerate all the output n-tuples that satisfy the proximity query condition, the pointer p 1  is advanced to point to the instance in c 1 , say x′ 1 , that is next to x 1 . Let p′ 1  be the new value of p 1 . The rest of the pointers remain unchanged. The algorithm switches back to plane-sweep mode with c 1  as the start-list and the new list pointers p′ 1 , p 2 , . . . p n . As illustrated in FIG. 4, the algorithm switches back to plane-sweep mode with the pointers pointing to the list elements a 3 , b 2 , c 1 , d 2 , and e 2 . The execution of the nested-loop mode and the advancement of the pointer p 1 , to x′ 1  guarantees that no output n-tuple is reported twice. 
     Although the algorithm as stated above works properly, it would also have been possible to continue the execution of the nested-loop mode with the list x′ 1 , x 2,  . . . x n , until no matches are found (e.g., with elements a 3 , b 2 , c 1 , d 2 , and e 2  as in the case of our example). In this case, x′ 1  is within the range v that contains the output tuple x 1 , x 2 , . . . x n , and thus the nested-loop mode continues execution to enumerate all the output n-tuples that contain x′ 1 . 
     In other words, two cases may arise when the next keyword instance x′ 1  is retrieved from the list c 1 . If x′ 1  is within v, then the algorithm continues with the nested-loop mode; whereas if x′ 1  is outside v (i.e., to the right of v), then the algorithm switches back to the plane-sweep mode. Since execution of the nested-loop mode is costly, it is preferable to return to the plane-sweep mode as early as possible. On the other hand, the switch to the plane-sweep mode may be unnecessary if it results in immediately returning to the nested-loop mode. 
     The time complexity of time-sweep mode of the algorithm is at worst O(N), where N=Σ i=1   n s 1  and s 1  is the number of keyword instances in each linked list entry of a keyword that is involved in the proximity search query. This is due to the fact that the algorithm visits each instance in the involved linked list entries at most once, and upon visiting an instance p, the algorithm performs constant work, basically checking whether p lies inside the search interval, and possibly inserting p into the candidate output tuple or resetting the search interval. 
     The maintenance of the search interval is handled by the algorithm in constant time, i.e., is 0(1) per operation. Checking whether the location of an keyword instance lies inside the interval, inserting an instance into the interval and the modification of the boundaries of the interval upon insertion are all performed by simple constant time comparisons and operations, and hence are 0(1). Therefore, the overhead associated with plane-sweep mode of the algorithm is 0(1) per instance in the linked list entries in the proximity search query and hence sums up to O(N). 
     The nested-loop mode is the output generation phase of the algorithm. When the number of output tuples of the algorithm is k, then the complexity of nested-loop mode of the algorithm is only O(k). Notice that each iteration of the nested loop produces an output tuple, except for the last iteration in each of the nested loops. As a result, the cost of the nested loop is asymptotically covered by the number of output tuples produced. Moreover, the O(k) complexity implies that the cost per output tuple produced by the algorithm is constant, i.e., is 0(1) per output tuple. 
     Upon switching to nested-loop mode, the algorithm already contains an output tuple, o=&lt;° o 1 , o 2 , . . . , o n &gt;, that needs to be reported. Moreover, in the direct neighborhood of each keyword instance of the output tuple o, there may lie other output tuples. The purpose of the multiply nested loops of nested-loop mode is to report all the possible output tuples that are in the neighborhood of o that follow o in the inverted lists and also contain o 1 . More formally, assume that for stream x i , i=2, . . . n, there are c i  instances that follow instance o i , where all of the c i  instances form output tuples when combined with points from the other streams in the neighborhood of o and contain o 1  in them. As a result, the number of output tuples in this case is k=Π i=1   n c 1 . On the other hand, each iteration of the nested loop produces an output tuple, except for the last iteration in each of the nested loops. Therefore, the complexity of the multiply nested loops in nested-loop mode is: O(Π i=1   n c 1 )=0(k). Accordingly, the overall performance of the algorithm is O(N+k), i.e., is linearly proportional to the total sizes of the input inverted lists and the size of the reported output tuples. 
     The foregoing discloses and describes merely exemplary embodiments of the present invention. One skilled in the art will readily recognize from such discussion, and from accompanying drawings and claims, that various changes, modifications, and variations can be made therein without departing from the spirit and scope of the present invention.