US7051017B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Inverse inference engine for high performance web search
Assignee: Fiver LLC
•
Filing: 2002-12-10
•
Granted: 2006-05-23
•
Expires: 2022-12-10
Abstract
Abstract An information retrieval system that deals with the problems of synonymy, polysemy, and retrieval by concept by allowing for a wide margin of uncertainty in the initial choice of keywords in a query. For each input query vector and an information matrix, the disclosed system solves an optimization problem which maximizes the stability of a solution at a given level of misfit. The disclosed system may include a decomposition of the information matrix in terms of orthogonal basis functions. Each basis encodes groups of conceptually related keywords. The bases are arranged in order of decreasing statistical relevance to a query. The disclosed search engine approximates the input query with a weighted sum of the first few bases. Other commercial applications than the disclosed search engine can also be built on the disclosed techniques.
Inventors
- 👤 Giovanni B. Marchisio
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 23:10
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F16/90; G06F16/95; G06F16/954; G06F40/00; G06F40/20; G06F40/205; G06F40/216; G06F40/268; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 70
Claim 1
Independent Claim
251 words
An information retrieval system comprising: an information file processing component that is structured to generate a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; and generate a term-spread matrix to produce a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent to which terms are correlated; a query mechanism that is structured to receive a query consisting of at least one term and generate a query vector based upon use received query, wherein the query vector has as many elements as the rows of the term-spread matrix; and an optimization engine that is structured to formulate, based upon the term-spread matrix and query vector, a constrained optimization problem description, wherein the choice of a stabilization parameter in the problem description determines the extent of a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generate a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of each the information files, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 2
Dependent Claim
251 words
An information retrieval system comprising: an information file processing component that is structured to generate a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; and generate a term-spread matrix to produce a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent to which terms are correlated; a query mechanism that is structured to receive a query consisting of at least one term and generate a query vector based upon use received query, wherein the query vector has as many elements as the rows of the term-spread matrix; and an optimization engine that is structured to formulate, based upon the term-spread matrix and query vector, a constrained optimization problem description, wherein the choice of a stabilization parameter in the problem description determines the extent of a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generate a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of each the information files, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 3
Dependent Claim
38 words
The information retrieval system of claim 1 wherein the generating the term-document matrix includes generating elements in the matrix that reflect the number of occurrences of each one of the terms in each one of the information files.
Claim 4
Dependent Claim
72 words
The information retrieval system of claim 1 wherein the information file processing component is further structured to determine whether the received query includes at least one phrase; and responsive to determining that the received query includes at least one phrase, adding a new row to the term-document matrix, each element in the new row containing the number occurrences of the at least one phrase in the respective one of the information files.
Claim 5
Dependent Claim
110 words
The information retrieval system of claim 3 wherein the information file processing component is further structured to: parse electronic text contained within the information files to generate concept identifiers; generate an auxiliary data structure indexed by the concept identifiers, the data structure storing the positions of all terms contained within the information files; and determine the number of occurrences of that at least one phrase in each respective one of the information files using the number of occurrences of the individual terms composing the at least one phrase and the proximity of the terms as indicated by the relative positions of the individual terms contained in the auxiliary data structure.
Claim 6
Dependent Claim
40 words
The information retrieval system of claim 1 wherein the information file processing component is further structured to generate each element in the term-document matrix as a binary value denoting the presence or absence of a respective one of the terms.
Claim 7
Dependent Claim
63 words
The information retrieval system of claim 1 wherein the information file processing component is further structured to generate a weight for each element in the term-document matrix based upon a number of occurrence of a respective one of the terms within a respective one at the information files and distribution of the respective one of the terms across all of the information files.
Claim 8
Dependent Claim
26 words
The information retrieval system of claim 6 wherein the information file processing component is further structured to sort the document weights based on a predetermined ordering.
Claim 9
Dependent Claim
14 words
The information retrieval system of claim 7 wherein the predetermined ordering is decreasing order.
Claim 10
Dependent Claim
62 words
The information retrieval system of claim 1 wherein the optimization engine is further structured to automatically generate a lexical knowledge base responsive to the solution of the constrained optimization problem description, wherein the generating includes cross-multiplying the term-document matrix, other than the term-spread matrix, by the document weights to generate a plurality of term weights, one for each one of the terms.
Claim 11
Dependent Claim
24 words
The information retrieval system of claim 9 wherein the optimization engine is further structured to sort the term weights based on a predetermined ordering.
Claim 12
Dependent Claim
14 words
The information retrieval system of claim 9 wherein the predetermined ordering is decreasing order.
Claim 13
Dependent Claim
238 words
A computer-readable memory medium containing instructions for controlling a computer processor to retrieve information by: generating a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; generating a term-spread matrix, wherein the term-spread matrix is a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent in which terms are correlated; receiving a query consisting of at least one term; in response to receiving the query, generating a query vector, wherein the query vector has as many elements as the rows of the term-spread matrix; formulating, based upon the term-spread matrix and query vector, a constrained optimization problem description, wherein the choice of a stabilization parameter in the problem description determines the extent a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generating a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of each the information flies, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 14
Dependent Claim
238 words
A computer-readable memory medium containing instructions for controlling a computer processor to retrieve information by: generating a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; generating a term-spread matrix, wherein the term-spread matrix is a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent in which terms are correlated; receiving a query consisting of at least one term; in response to receiving the query, generating a query vector, wherein the query vector has as many elements as the rows of the term-spread matrix; formulating, based upon the term-spread matrix and query vector, a constrained optimization problem description, wherein the choice of a stabilization parameter in the problem description determines the extent a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generating a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of each the information flies, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 15
Dependent Claim
61 words
The memory medium of claim 12 , the instructions further controlling the processor by automatically generating a lexical knowledge base responsive to the solution of the constrained optimization problem description, wherein the generating includes cross-multiplying the term-document matrix, rather than the term-spread matrix, by the document weights to generate a plurality of term weights, one for each one of the terms.
Claim 16
Dependent Claim
23 words
The memory medium of claim 13 , the instruction further controlling the processor by sorting the term weights based on a predetermined ordering.
Claim 17
Dependent Claim
14 words
The memory medium of claim 14 , wherein the predetermined ordering is decreasing order.
Claim 18
Dependent Claim
28 words
The memory medium of claim 12 , the instructions further controlling the processor by: parsing electronic text contained within the information files, wherein the parsing includes recognizing acronyms.
Claim 19
Dependent Claim
30 words
The memory medium of claim 12 , the instruction further controlling the processor by: parsing electronic text contained within the information files, wherein the parsing further includes recording term positions.
Claim 20
Dependent Claim
34 words
The memory medium of claim 12 , the instructions further controlling the processor by: parsing electronic text contained within the information files, wherein the parsing further include processing tag information within the information files.
Claim 21
Dependent Claim
16 words
The memory medium of claim 18 wherein the tag information includes one or more HTML tags.
Claim 22
Dependent Claim
16 words
The memory medium of claim 18 wherein the instructions further includes one or more XML tags.
Claim 23
Dependent Claim
30 words
The memory medium of claim 12 , the instructions further controlling the processor by: passing electronic text contained within the information files, wherein the parsing further includes extracting word roots.
Claim 24
Dependent Claim
30 words
The memory medium of claim 12 , the instructions further controlling the processor by: passing electronic text contained within the information files, wherein the parsing further includes generating concept identifiers.
Claim 25
Dependent Claim
44 words
The memory medium of claim 22 , the instructions further controlling the processor by: generating an auxiliary data structure, the auxiliary data structure being indexed by the concept identifiers, and the data structure storing the positions of all terms contained within the information files.
Claim 26
Dependent Claim
41 words
The memory medium of claim 23 , wherein the auxiliary data structure further stores tag information associated with respective ones of the information files, wherein the tag information reflects at least one characteristic of the respective ones of the information files.
Claim 27
Dependent Claim
25 words
The memory medium of claim 24 , wherein the tag information reflects at least one date associated with each respective one of the information files.
Claim 28
Dependent Claim
33 words
The memory medium of claim 12 , the instructions further controlling the processor by: parsing electronic text contained within the information files, wherein the parsing includes counting term occurrences in each information file.
Claim 29
Dependent Claim
37 words
The memory medium of claim 12 wherein the generating the term-document matrix includes generating elements in the matrix that reflect the number of occurrences of each one of the terms in each one of the information files.
Claim 30
Dependent Claim
69 words
The memory medium of claim 12 , the instructions further controlling the processor by: determining whether the user query includes at least one phrase; and responsive to determining that the query includes at least one phrase, adding a new row to the term-document matrix, each element in the new row containing the number of occurrences of the at least one phrase in the respective one of the information files.
Claim 31
Dependent Claim
107 words
The memory medium of claim 28 , the instructions further controlling the processor by: parsing electronic text contained within the information files to generate concept identifiers. generating an auxiliary data structure indexed by the concept identifiers, the data structure storing the positions of all terms contained within the information files; and determining the number of occurrences of the at least one phrase in each respective one of the information files using the number of occurrences of the individual terms composing the at least one phrase and the proximity of the terms as indicated by the relative positions of the individual terms contained in the auxiliary data structure.
Claim 32
Dependent Claim
38 words
The memory medium of claim 12 wherein the generating of the term-document matrix further comprises generating each element in the term-document matrix as a binary value denoting the presence or absence of a respective one of the terms.
Claim 33
Dependent Claim
58 words
The memory medium at claim 12 wherein the generating of the term-document matrix further comprises weighting each element in the term-document matrix by a number of occurrence of a respective one of the terms within a respective one of the information files and by distribution of the respective one of the terms across all of the information files.
Claim 34
Dependent Claim
22 words
The memory medium of claim 31 , the instructions further controlling the processor by sorting the document weights based one predetermined ordering.
Claim 35
Dependent Claim
13 words
The memory medium of claim 32 wherein the predetermined ordering is decreasing order.
Claim 36
Dependent Claim
229 words
An information retrieval method comprising of: generating a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; generating a term-spread matrix, wherein the term-spread matrix is a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent to which terms are correlated; receiving a user-query consisting of at least one term; in response to receiving the query, generating a query vector, wherein the query vector has as many elements as the rows of the term-spread matrix; formulating, based upon the term-spread matrix and query vector, a constrained optimization problem description wherein the choice of a stabilization parameter in the problem description determines the extent of a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generating a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of the information files, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 37
Dependent Claim
229 words
An information retrieval method comprising of: generating a term-document matrix to represent electronic information files stored in a computer system, each element in the term-document matrix indicating a number of occurrences of a term within a respective one of the electronic information files; generating a term-spread matrix, wherein the term-spread matrix is a weighted autocorrelation of the generated term-document matrix, the term-spread matrix indicating an amount of variation in term usage in the information files and the extent to which terms are correlated; receiving a user-query consisting of at least one term; in response to receiving the query, generating a query vector, wherein the query vector has as many elements as the rows of the term-spread matrix; formulating, based upon the term-spread matrix and query vector, a constrained optimization problem description wherein the choice of a stabilization parameter in the problem description determines the extent of a trade-off between a degree of fit and the stability of all solutions to the constrained optimization problem description; generating a solution vector to the constrained optimization problem description, the vector including a plurality of document weights, each one of the plurality of document weights corresponding to one of the information files, wherein each of the document weights reflects a degree of correlation between the query and the corresponding one of the information files; and providing an information response reflecting the document weights.
Claim 38
Dependent Claim
40 words
The information retrieval method of claim 34 wherein the generating of the term-document matrix further comprises generating each element in the term-document matrix as a binary weight value denoting the presence or absence of a respective one of the terms.
Claim 39
Dependent Claim
61 words
The information retrieval method of claim 34 further comprising: determining whether the user query includes at least one phrase; and responsive to determining that the query includes at least one phrase, adding a new row to the term-document matrix, each element in the new row containing the number of occurrences of the phrase in the respective one of the information files.
Claim 40
Dependent Claim
102 words
The information retrieval method of claim 36 further comprising: parsing electronic text contained within the information files to generate concept identifiers. generating an auxiliary data structure indexed by the concept identifiers, the data structure storing the positions of all terms contained within the information files; and determining the number of occurrences of the at least one phrase in each respective one of the information files using the number of occurrences of the individual terms composing the at least one phrase and the proximity of the terms as indicated by the relative positions of the individual terms contained in the auxiliary data structure.
Claim 41
Dependent Claim
40 words
The information retrieval method of claim 34 wherein the step of generating the term-document matrix includes generating elements in the matrix that reflect the number of occurrences of each one of the terms in each one of the information files.
Claim 42
Dependent Claim
28 words
The information retrieval method of claim 34 further comprising: parsing electronic text contained within the information files, wherein the parsing includes counting term occurrences in each information file.
Claim 43
Dependent Claim
26 words
The information retrieval method of claim 34 , further comprising: parsing electronic text contained within the information files, wherein the parsing further includes generating concept identifiers.
Claim 44
Dependent Claim
40 words
The information retrieval method of claim 40 , further comprising: generating an auxiliary data structure, the auxiliary data structure being indexed by the concept identifiers, and the data structure storing the positions of all terms contained within the information files.
Claim 45
Dependent Claim
42 words
The information retrieval method of claim 41 , wherein the auxiliary data structure further stores tag information associated with respective ones of the information files, wherein the tag information reflects at least one characteristic of the respective ones of the information files.
Claim 46
Dependent Claim
25 words
The information retrieval method of claim 42 wherein the tag information reflects at least one date associated with each respective one of the information files.
Claim 47
Dependent Claim
25 words
The information retrieval method of claim 34 further comprising: parsing electronic text contained within the information files, wherein the parsing further includes extracting word roots.
Claim 48
Dependent Claim
29 words
The information retrieval method of claim 34 further comprising: parsing electronic text contained within the information files, wherein the parsing further includes processing tag information within the information files.
Claim 49
Dependent Claim
17 words
The information retrieval method of claim 45 wherein the tag information includes one or more HTML tags.
Claim 50
Dependent Claim
16 words
The information retrieval method of claim 45 wherein the information includes one or more XML tags.
Claim 51
Dependent Claim
25 words
The information retrieval method of claim 34 further comprising; parsing electronic text contained within the information files, wherein the parsing further includes recording term positions.
Claim 52
Dependent Claim
23 words
The information retrieval method of claim 34 further comprising: parsing electronic text contained within the information files, wherein the parsing includes recognizing acronyms.
Claim 53
Dependent Claim
59 words
The information retrieval method of claim 34 wherein the generating of the term-document matrix further comprises weighting each element in the term-document matrix by a number of occurrence of a respective one of the terms within a respective one of the information files and by distribution of the respective one of the terms across all of the information files.
Claim 54
Dependent Claim
18 words
The information retrieval method of claim 50 further comprising sorting the document weights based on a predetermined ordering.
Claim 55
Dependent Claim
14 words
The information retrieval method of claim 51 wherein the predetermined ordering is decreasing order.
Claim 56
Dependent Claim
56 words
The information retrieval method of claim 34 further comprising automatically generating a lexical knowledge base responsive to the solution of the constrained optimization problem description, wherein the generating includes cross-multiplying the term-document matrix, rather than the term-spread matrix, by the document weights to generate a plurality of term weights, one for each one of the terms.
Claim 57
Dependent Claim
18 words
The information retrieval method of claim 53 further comprising sorting the term weights based on a predetermined ordering.
Claim 58
Dependent Claim
14 words
The information retrieval method of claim 54 wherein the predetermined ordering is decreasing order.
Claim 59
Dependent Claim
25 words
The information retrieval system of claim 34 wherein the information file processing component is further structured to parse electronic text contained within the information files.
Claim 60
Dependent Claim
18 words
The information retrieval system of claim 56 wherein the parsing includes counting term occurrences in each information file.
Claim 61
Dependent Claim
19 words
The information retrieval system of claim 56 wherein the parsing further includes processing tag information within the information files.
Claim 62
Dependent Claim
15 words
The information retrieval system of claim 58 wherein the tag information includes one XML tags.
Claim 63
Dependent Claim
17 words
The information retrieval system of claim 56 wherein the tag information includes one or more HTML tags.
Claim 64
Dependent Claim
15 words
The information retrieval system of claim 56 wherein the parsing further includes recording term positions.
Claim 65
Dependent Claim
14 words
The information retrieval system of claim 56 wherein the parsing further includes recognizing acronyms.
Claim 66
Dependent Claim
15 words
The information retrieval system of claim 58 wherein the parsing further includes extracting word roots.
Claim 67
Dependent Claim
15 words
The information retrieval system of claim 56 wherein the parsing further includes generating concept identifiers.
Claim 68
Dependent Claim
42 words
The information retrieval system of claim 64 wherein the information file processing component is further structured to generate an auxiliary data structure indexed by the concept identifiers, and the data structure storing the positions of all terms contained within the information files.
Claim 69
Dependent Claim
41 words
The information retrieval system of claim 65 wherein the auxiliary data structure further stores tag information associated with respective ones of the information files, wherein the tag information reflects at least one characteristic of the respective ones of the information files.
Claim 70
Dependent Claim
25 words
The information retrieval system of claim 66 wherein the tag information reflects at least one date associated with each respective one of the information files.
References Cited (Backward Citations)
US4839853A
Cited
US5301109A
Cited
US5317507A
Cited
US5325298A
Cited
US5794178A
Cited
US5619709A
Cited
US6006221A
Cited
US6026388A
Cited
US5778362A
Cited
US5857179A
Cited
US5950189A
Cited
US6064951A
Cited
US6192360B1
Cited
US20020059161A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-05-22 | 2009-11-21 | 2010-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-05-22 | 2013-11-21 | 2014-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-05-22 | 2017-11-21 | 2018-05-23 | $7700.00 | Window Closed / Lapsed |