Inverse inference engine for high performance web search

• US 7,051,017 B2
• Filed: 12/10/2002
• Issued: 05/23/2006
• Est. Priority Date: 03/23/1999
• Status: Expired due to Term

• Current Assignee: Fiver LLC
• Original Assignee: Insightful Corporation (Cloud Software Group)
• Inventors: Marchisio, Giovanni B.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US10/316,973
• Publication Number:
  US 20030217047A1
• Time in Patent Office: 1,260 Days
• Field of Search: 707 1- 10, 707/104.1, 707100-102, 707/513, 707530-531, 704/1, 704/9, 704/10
• US Class Current: 707/713
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. The information retrieval system of claim 7 wherein the predetermined ordering is decreasing order.

9. 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.

10. The information retrieval system of claim 9 wherein the optimization engine is further structured to sort the term weights based on a predetermined ordering.

11. The information retrieval system of claim 9 wherein the predetermined ordering is decreasing order.

12. 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.

13. 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.

14. The memory medium of claim 13, the instruction further controlling the processor by sorting the term weights based on a predetermined ordering.

15. The memory medium of claim 14, wherein the predetermined ordering is decreasing order.

16. 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.

17. 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.

18. 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.

19. The memory medium of claim 18 wherein the tag information includes one or more HTML tags.

20. The memory medium of claim 18 wherein the instructions further includes one or more XML tags.

21. 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.

22. 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.

23. 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.

24. 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.

25. The memory medium of claim 24, wherein the tag information reflects at least one date associated with each respective one of the information files.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. The memory medium of claim 31, the instructions further controlling the processor by sorting the document weights based one predetermined ordering.

33. The memory medium of claim 32 wherein the predetermined ordering is decreasing order.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.

46. The information retrieval method of claim 45 wherein the tag information includes one or more HTML tags.

47. The information retrieval method of claim 45 wherein the information includes one or more XML tags.

48. 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.

49. The information retrieval method of claim 34 further comprising:

parsing electronic text contained within the information files, wherein the parsing includes recognizing acronyms.

50. 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.

51. The information retrieval method of claim 50 further comprising sorting the document weights based on a predetermined ordering.

52. The information retrieval method of claim 51 wherein the predetermined ordering is decreasing order.

53. 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.

54. The information retrieval method of claim 53 further comprising sorting the term weights based on a predetermined ordering.

55. The information retrieval method of claim 54 wherein the predetermined ordering is decreasing order.

56. 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.

57. The information retrieval system of claim 56 wherein the parsing includes counting term occurrences in each information file.

58. The information retrieval system of claim 56 wherein the parsing further includes processing tag information within the information files.

59. The information retrieval system of claim 58 wherein the tag information includes one XML tags.

60. The information retrieval system of claim 56 wherein the tag information includes one or more HTML tags.

61. The information retrieval system of claim 56 wherein the parsing further includes recording term positions.

62. The information retrieval system of claim 56 wherein the parsing further includes recognizing acronyms.

63. The information retrieval system of claim 58 wherein the parsing further includes extracting word roots.

64. The information retrieval system of claim 56 wherein the parsing further includes generating concept identifiers.

65. 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.

66. 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.

67. 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.