Multistage intelligent database search method
View Patent ↗An improved multistage intelligent database search method includes (1) a prefilter that uses a precomputed index to compute a list of most “promising” records that serves as input to the original multistage search method, resulting in dramatically faster response time; (2) a revised polygraph weighting scheme correcting an erroneous weighting scheme in the original method; (3) a method for providing visualization of character matching strength to users using the bipartite graphs computed by the multistage method; (4) a technique for complementing direct search of textual data with search of a phonetic version of the same data, in such a way that the results can be combined; and (5) several smaller improvements that further refine search quality, deal more effectively with multilingual data and Asian character sets, and make the multistage method a practical and more efficient technique for searching document repositories.
1. A method of searching a database for a query comprising the steps of:
(a) providing a database of strings of characters;
(b) providing a query string;
(c) identifying polygraphs that occur in said query string and also in said database strings;
(d) providing a match cost to each said identified polygraph, and weighting the polygraphs match costs in inverse proportion to the length of the polygraph;
(e) positioning the query string relative to each database string;
(f) matching polygraph occurrences in the query string with those in each database string, the cost of matching providing a numerical indication of the similarity between said query string and each said database string, and the match cost attenuating the effects of polygraph inclusion on the matching step;
(g) realigning said query string to reduce the match cost by examining edges present in a matching solution;
(h) repeating said matching step (f) and said realigning step (g) a predetermined number of times or until the match cost fails to improve;
(i) repeating the steps (c) to (h) above for each database string for the purpose of identifying those database strings most similar to said query string;
(j) computing a match strength of each character in each database string based upon the match cost of each matching polygraph that includes that character; and,
(k) displaying the database strings most similar to the query string using highlighting techniques to visually represent relative match strengths of database characters.
2. A method of searching a database for a query as set forth in claim 1 in which steps (e) through (g) are performed a minimal number of times for each alignment in a set of initial alignment positions, which may include left-alignment, right-alignment, and a number of intermediate alaignment points, and in which step (h) is replaced by identifying the initial alignment which has produced the best matching so far obtained, and repeating steps (e) through (g) for this initial alignment a predetermined number of times, or until the match cost fails to improve.
3. A method of searching a database for a query as set forth in claim 2 in which matched database strings are penalized in proportion to the departure from left-alignment of the query alignment that produces the best matching.
4. A method of searching a database for a query as set forth in claim 3 in which matched database strings are penalized in proportion to their length.
5. A method of searching a database for a query as set forth in claim 4 further comprising the step of post-processing of the matchings computed for each database string in order to improve match quality, either by adjusting the contribution of some graph edges to the total match cost of a database string, or by making any other adjustments or alterations to a bipartite graph.
6. A method of searching a database for a query as set forth in claim 5 further comprising a prefilter means for operating on a pre-computed index of polygraphs to eliminate database strings from further consideration.
7. A method of searching a database for a query as set forth in claim 6 further comprising the step of operating on a pre-computed index of all polygraphs of a fixed length N, wherein each index entry is a list of all strings in the database that contain a particular N-graph.
8. A method of searching a database for a query as set forth in claim 7 in which said prefilter means retrieves database strings from the index lists one list at a time, traversing the lists in order of increasing list length.
9. A method of searching a database for a query as set forth in claim 8 in which said prefilter means retrieves database strings from the index lists in such a way as to keep track of how many distinct N-graphs each retrieved database string has in common with the query, returning preferentially those strings having the most N-graphs in common with the query.
10. A method of searching a database for a query as set forth in claim 5 comprising the step of performing a search on a transduced version of the database using a transduced version of the query; or two parallel searches on transduced and non-transduced versions of the database using transduced and non-transduced versions of the query respectively, with the results of the two searches being merged.
11. A method of searching a database for a query as set forth in claim 10 further comprising the step of identifying database strings occurring more than once in the merged output list and removing all occurrences but the most similar occurrence.
12. A method of searching a database for a query as set forth in claim 11 in which the transductive preprocessing applied to query string and database strings produces a phonetic transcription of the query and the database.
13. A method of searching as set forth in claim 11 further comprising searching non-alphabetic textual data by applying transductive preprocessing to database strings and query string that transforms non-alphabetic text into an alphabetic equivalent.
14. A method of searching a database for a query as set forth in claim 5 where said database strings are paragraphs or other natural subdivisions of the documents in a document collection, and where the relation of each paragraph to its source document is preserved by associating with each paragraph a pointer or link to the source document, and the sequence number of the paragraph in the source document.
15. A method of searching a database for a query as set forth in claim 14 , in which the output is a list of matching links to source documents, together with the paragraph in the document that is most similar to the query, or the paragraph or paragraphs that are deemed most significant based on matching costs and/or relative location and distribution within the source document.
16. A method of searching a database for a query as set forth in claim 15 which re-parses source documents and/or re-compares them with a query, such that when a user views the source document, said user is placed automatically at the position of a matching paragraph.
17. A method of searching a database as set forth in claim 1 where the highlighting techniques visually represent to the user the relative match strengths of the bipartite graph of database characters, the highlighting techniques comprising colored fonts, typefaces of differing size, typefaces of differing style, and underlining.