US5978797A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multistage intelligent string comparison method
Assignee: NEC Corp
•
Filing: 1997-07-09
•
Granted: 1999-11-02
•
Expires: 2017-07-09
Abstract
Abstract A multistage database search method includes a first stage that only considers textual polygraphic frequencies and a second stage that considers the location of the polygraphs and coarsely approximates the proper alignment between the query and the database strings and a third stage that provides a better approximation of the alignment. The final output is a listing of suggested database records ranked by their similarity to the query.
Inventors
- 👤 Peter N. Yianilos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 00:23
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24564; G06F16/2452; G06F16/24522; G06F16/24526; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
159 words
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 cost to each said identified 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; (g) realigning said query string to reduce the cost by examining edges present in the matching solution; (h) repeating said matching and said realigning a predetermined number of times or until the cost of matching fails to improve; and (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.
Claim 2
Independent Claim
159 words
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 cost to each said identified 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; (g) realigning said query string to reduce the cost by examining edges present in the matching solution; (h) repeating said matching and said realigning a predetermined number of times or until the cost of matching fails to improve; and (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.
Claim 3
Dependent Claim
28 words
A method of searching as set forth in claim 1, where polygraphs are longer than a predetermined fixed minimum length and shorter than a predetermined fixed maximum length.
Claim 4
Dependent Claim
21 words
A method of searching as set forth in claim 1, where the query string is initially left-aligned with each database string.
Claim 5
Dependent Claim
26 words
A method of searching as set forth in claim 1, where said matching is approximated by relying only on the number of matching of said polygraph.
Claim 6
Dependent Claim
62 words
A method of searching as set forth in claim 1, where said matching is approximately identified by dividing matching polygraphs into levels so that occurrences alternate between said query string and database string such that: when the number of occurrences is even, the matching is uniquely defined and when the number of occurrences is odd, omitting either the first or last occurrence.
Claim 7
Dependent Claim
20 words
A method of searching as set forth in claim 1, where said matching is identified by a quasi-convex matching method.
Claim 8
Dependent Claim
23 words
A method of searching as set forth in claim 1, where said examination of edges comprises computing the mean of the edge lengths.
Claim 9
Dependent Claim
23 words
A method of searching as set forth in claim 1, where said examination of edges comprises computing the median of the edge lengths.
Claim 10
Dependent Claim
22 words
A method of searching as set forth in claim 1, where said matching following realigning is approximated by mathematically adjusting edge lengths.
Claim 11
Dependent Claim
24 words
A method of searching as set forth in claim 1, where said identification of most similar database strings is performed using a heap data-structure.
Claim 12
Dependent Claim
24 words
A method of searching as set forth in claim 1, where said query strip and database string are mathematically padded to a predetermined length.
Claim 13
Dependent Claim
107 words
A multistage method of searching a database for a query comprising the steps of: providing a database of strings of characters; providing a query string; processing each database string using a first method selected on the basis of computational time efficiency for identifying database strings that are similar to said query string; processing said similar database strings using a second method selected to be more accurate but less time efficient than said first method for identifying smaller numbers of database strings that are similar to said query string, and providing final identification of most similar database strings based on the result of processing said similar database strings.
Claim 14
Dependent Claim
107 words
A multistage method of searching a database for a query comprising the steps of: providing a database of strings of characters; providing a query string; processing each database string using a first method selected on the basis of computational time efficiency for identifying database strings that are similar to said query string; processing said similar database strings using a second method selected to be more accurate but less time efficient than said first method for identifying smaller numbers of database strings that are similar to said query string, and providing final identification of most similar database strings based on the result of processing said similar database strings.
Claim 15
Dependent Claim
87 words
A multistage method of searching as set forth in claim 12, where said first method and said second method are selected from the group consisting of relying on the number of matchings of a polygraph, dividing matching polygraphs into levels so that occurrences alternate between said query string and database string such that when the number of occurrences is even, the matching is uniquely defined and when the number of occurrences is odd, omitting either the first or last occurrences, quasi-convex matching, and mathematically adjusting edge length.
Claim 16
Dependent Claim
27 words
A multistage method of searching as set forth in claim 13, where said providing final identification of most similar database strings is performed using a heap data-structure.
Claim 17
Dependent Claim
27 words
A multistage method of searching as set forth in claim 12, where said providing final identification of most similar database strings is performed using a heap data-structure.
References Cited (Backward Citations)
US4490811A
Cited
US4845610A
Cited
US5113340A
Cited
US5060143A
Cited
US5418951A
Cited
US5706365A
Cited
US5802515A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |