Text search ordered along one or more dimensions

• US 7,206,778 B2
• Filed: 12/17/2001
• Issued: 04/17/2007
• Est. Priority Date: 12/17/2001
• Status: Expired due to Term

• Current Assignee: Avolin LLC
• Original Assignee: Knova Software Incorporated (Aptean Superior Holdings, Inc.)
• Inventors: Copperman, Max, Bode, Andreas
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US10/023,433
• Publication Number:
  US 20030115187A1
• Time in Patent Office: 1,947 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

This document discusses, among other things, systems and methods for searching for relevant documents in a document corpus. Using, among other things, text provided by a user'"'"'s query, the system undertakes a dynamic search process that includes at least one ordered sequence of searches. The results of a first search are evaluated to determine how to formulate a second or subsequent search, whether to perform a second or subsequent search, or whether or how to present to the user results from the search or searches performed up to that point. In one example, the first search uses tight criteria in conjunction with the language of the user'"'"'s query. If the number of documents in the search results do not meet or exceed a threshold value, the search criteria is progressively loosened over subsequent searches. The search list may depend on, among other things, a characteristic of the user query or upon a result returned by a previous search on the user query.

Claims

1. A computer-implemented method including:

(a) obtaining from a user a user query including at least some language;

(b) classifying the user query into a query class;

(c) selecting a search strategy using the query class in which the user query is classified, the selecting the search strategy including obtaining a set of search criteria;

(d) performing a first search for documents relevant to the user query using at least one search criteria selected from the set of search criteria, the set of search criteria including at least two different search criteria defining different search specificities when using identical terms from the user query language; and

(e) evaluating a first search result returned by the first search to determine whether to perform a subsequent search using at least one different search criteria from the set of search criteria.

2. The method of claim 1, further including, if a subsequent search is indicated by (e), modifying the search criteria and repeating (d) and (e).

3. The method of claim 1, further including, if a subsequent search is indicated by (e), modifying the search criteria and repeating (d) and (e) unless a list of different searches has been exhausted.

4. The method of claim 1, further including:

(f) returning a list of documents to the user.

5. The method of claim 1, further including:

(f) ranking documents; and

(g) returning a list of ranked documents to the user.

6. The method of claim 5, in which the ranking of a particular document is based at least in part on which performed search returned that particular document.

7. The method of claim 5, in which the ranking of a particular document is based at least in part on a degree to which a particular document satisfied the search criteria associated with the particular performed search that returned that particular document.

8. The method of claim 5, in which the ranking of a particular document is based at least in part on a weight with which the particular document is associated with a particular concept node in one of multiple taxonomies.

9. The method of claim 1, further including determining a characteristic of the subsequent search based at least in part on the first search result.

10. The method of claim 9, in which determining a characteristic of the subsequent search includes formulating more specific criteria than criteria of the first search.

11. The method of claim 9, in which determining the characteristic of the subsequent search includes determining, based at least in part on the first search result, at least one of:

a criteria of the subsequent search within a dimension;

a dimension of the subsequent search criteria;

a search ordering of the subsequent search with respect to other subsequent searches having different criteria or dimensions; and

a scheme in which the search ordering is traversed.

12. The method of claim 11, in which the determining the scheme in which the search ordering is traversed includes using an approximately binary divide-and-conquer traversal of the search ordering.

13. The method of claim 1, in which selecting the search strategy includes selecting at least one of:

a criteria of the subsequent search within a dimension;

a dimension of the subsequent search criteria;

a search ordering of the subsequent search with respect to other subsequent searches having different criteria or dimensions; and

a scheme in which the search ordering is traversed.

14. The method of claim 1, in which classifying the user query includes:

parsing the user query into information-bearing terms, based at least in part on any noninformation-bearing stopwords included in the user query; and

classifying the user query into a query class based on at least one of;

how many information-bearing terms are obtained from the user query; and

how many words are included in the information-bearing terms obtained from the user query.

15. The method of claim 1, in which classifying the user query into a query class includes classifying the user query into query classes that include:

a first query class in which the user query includes a single information-bearing term;

a second query class in which the user query includes between two and three information-bearing terms, inclusive;

a third query class in which the user query includes more than three information-bearing terms without any accompanying noninformation-bearing stopwords; and

a fourth query class in which the user query includes more than three information-bearing terms and at least one noninformation-bearing stopword.

16. The method of claim 15, further including a first ordered list of searches associated with the first query class, in which the first ordered list is ordered as:

(1) a first search for the term in particular regions of the document;

(2) a second search for at least one of the term and word form variations of the term in the particular regions of the document;

(3) a third search for the term anywhere in the document;

(4) a fourth search for at least one of the term and word form variations of the term anywhere in the document; and

(5) a fifth search for at least one of the term, word form variations of the term, and synonyms of the term anywhere in the document.

17. The method of claim 16, in which at least one of the searches allows casing variations.

18. The method of claim 15, further including a second ordered list of searches associated with the second query class, in which the second ordered list is ordered as:

(1) a first search for all of the terms appearing together as a phrase in particular regions of the document;

(2) a second search for all of the terms appearing together as a phrase anywhere in the document;

(3) a third search for all of the terms appearing near each other anywhere in the document;

(4) a fourth search for all of the terms appearing anywhere in the document;

(5) a fifth search for all of the terms, allowing word form variations of the terms, anywhere in the document;

(6) a sixth search for in-sequence pairs of terms anywhere in the document; and

(7) a seventh search for any of the terms anywhere in the document.

19. The method of claim 18, in which at least one of the searches allows casing variations.

20. The method of claim 15, further including a third ordered list of searches associated with the third query class, in which the third ordered list is ordered as:

(1) a first search for all of the terms appearing near each other anywhere in the document;

(2) a second search for all of the terms appearing anywhere in the document;

(3) a third search for all of the terms, allowing word form variations, anywhere in the document;

(4) a fourth search for all subsets of the terms appearing anywhere in the document, in which the subset includes all but one of the terms; and

(5) a fifth search for all subsets of the terms appearing anywhere in the document, in which the subset size is sequentially decreased from all but one of the terms to subsets of individual terms.

21. The method of claim 20, in which at least one of the searches allows casing variations.

22. The method of claim 15, further including a fourth ordered list of searches associated with the fourth query class, in which the fourth ordered list is ordered as:

(1) a first search for all terms appearing together as a phrase anywhere in the document;

(2) a second search for all terms appearing anywhere in the document;

(3) a third search iterating through subsets of terms, in which the subset size is sequentially decreased from all but one of the terms to subsets of individual terms;

(4) a fourth search iterating through subsets of terms, allowing word form variations, in which the subset size is sequentially decreased from all but one of the terms to subsets of individual terms;

(5) a fifth search for any complete term anywhere in the document; and

(6) a sixth search for any term anywhere in the document, allowing subphrases within each term.

23. The method of claim 22, in which at least one of the searches allows casing variations.

24. A computer-readable medium including instructions that, when executed on a computer, perform the method of claim 1.

25. The method of claim 1, in which the set of search criteria is automatically generated.

26. A computer-implemented method including:

obtaining from a user a user query including at least some language;

using an ordered list, S1, S2, . . . , SN, of at least two searches, each search using at least one search criteria that is different from the other searches, the search criteria selected from a multidimensional set of automatically generated search criteria, the set of search criteria including at least two different dimensions representing different approaches of varying search specificity; and

performing a search for documents relevant to the user query using one of the S1, S2, . . . , SN searches, starting with the S1 search, evaluating search results corresponding to the search performed to determine whether to perform a subsequent search and, if the search results yielded an insufficient number of documents relevant to the user query, moving to and performing another search in the list; and

returning a list of the documents returned by the at least one search that was performed.

27. The method of claim 26, in which the using the ordered list includes using a list ordered at least substantially according to specificity of the search criteria, in which S1 provides at least approximately more specific search criteria than S2, . . . , SN, and in which SN provides at least approximately more general search criteria than S1, S2, . . . , S(N−

1).

28. The method of claim 27, in which S1 provides more specific search criteria than S2, . . . , SN, and in which SN provides more general search criteria than S1, S2, . . . , S(N−

1).

29. The method of claim 28, in which the using the ordered list includes using a list ordered throughout according to specificity of the search criteria.

30. The method of claim 29, in which the list is ordered dynamically based at least in part on a result obtained from a previously-executed search on the user query.

31. The method of claim 27, in which the search criteria uses the language from the user query.

32. The method of claim 27, in which the at least approximately more specific search criteria uses an at least approximately more exact matching of a particular term from the user query to language in the documents, and the more general search criteria uses an at least approximately less exact matching of the particular term from the user query to language in the documents.

33. The method of claim 27, in which specificity of the search criteria varies along at least two of a textual dimension, a linguistic dimension, and a thesaurus dimension.

34. The method of claim 27, in which the search criteria specifies at least one predefined portion of the documents to be used in carrying out the search.

35. The method of claim 34, in which the predefined portion of the documents uses at least one of a title portion, a summary portion, and an abstract portion.

36. The method of claim 27, in which the at least approximately more specific search criteria uses a more specific portion of the documents, and the at least approximately more general search criteria uses a less specific portion of the documents.

37. The method of claim 26, further including, before the returning the list, ranking the documents.

38. The method of claim 37, in which the ranking of a particular document is based at least in part on which of the at least one performed searches returned that particular document.

39. The method of claim 37, in which the ranking of a particular document is based at least in part on a degree to which a particular document satisfied the search criteria associated with the at least one performed searches that returned that particular document.

40. The method of claim 37, in which the ranking of a particular document is based at least in part on a weight with which the particular document is associated with a particular concept node.

41. The method of claim 26, further including forming the ordered list based at least in part on the user query.

42. The method of claim 41, further including classifying the user query, and in which forming the ordered list based at least in part on the user query includes forming the ordered list based at least in part on the classification of the user query.

43. The method of claim 26, further including adjusting the ordered list based at least in part on search results from a previous search on the obtained user query.

44. The method of claim 26, in which the insufficient number of documents is determined by at least one of:

too few documents;

too many documents; and

the number of documents being outside a predetermined range.

45. A computer-readable medium including instructions that, when executed on a computer, perform the method of claim 26.

46. A computer-implemented method of searching for documents that are relevant to a user'"'"'s query, the method including:

obtaining from a user a user query including at least some language;

using an ordered list, S1, S2, . . . , SN, of at least two searches, each search using at least one search criteria that is different from the other searches, in which the list is ordered substantially according to specificity of the search criteria, in which S1 provides at least approximately more specific search criteria than S2, . . . , SN, and in which SN provides at least approximately more general search criteria than S1, S2, . . . , S(N−

1), and wherein the search criteria is selected from an automatically generated set of search criteria that includes at least two different search criteria that specify different regions of the document to be used in carrying out the search;

performing a search for documents relevant to the user query using one of the S1, S2, . . . , SN searches, starting with the S1 search, evaluating search results corresponding to the search performed to determine whether to perform a subsequent search and, if the search results yielded an insufficient number of documents relevant to the user query, moving to and performing another search in the list;

ranking the documents; and

returning a ranked list of the documents returned by the at least one search that was performed.

47. The method of claim 46, in which the ranking of a particular document is based at least in part on which of the at least one performed searches returned that particular document.

48. The method of claim 46, in which the ranking of a particular document is based at least in part on a degree to which a particular document satisfied the search criteria associated with the at least one performed searches that returned that particular document.

49. The method of claim 46, in which the ranking of a particular document is based at least in part on a weight with which the particular document is associated with a particular concept node.

50. The method of claim 46, in which the at least approximately more specific search criteria uses an at least approximately more exact matching of a particular term from the user query to language in the documents, and the at least approximately more general search criteria uses an at least approximately less exact matching of a particular term from the user query to language in the documents.

51. The method of claim 46, in which the insufficient number of documents is determined by at least one of:

too few documents;

too many documents; and

the number of documents being outside a predetermined range.

52. A computer-readable medium including instructions that, when executed on a computer, perform the method of claim 46.

53. An automated content provider system including:

a user query input to receive a user query;

a search query generator, coupled to the user query input, the search query generator to generate a search using the user query to formulate corresponding search criteria selected from an automatically generated set of search criteria, the set of search criteria including at least two different search criteria defining different search specificities when using identical terms from the user query language;

a search engine, including an input coupled to the search query generator and an output, the search engine using the search criteria to perform the search and to provide a corresponding search result at the search engine output;

a search result evaluator, coupled to the search engine output and an input of the search query generator, the search result evaluator to evaluate the search result, in which the search query generator and search engine operate to generate or perform at least one subsequent search using different search criteria from the set of search criteria, if indicated by the evaluation of the search result by the search result evaluator; and

a result ranking engine, coupled to the search engine output to rank documents returned in at least one search result, in which the result ranking engine includes an output user interface, in which the result ranking engine ranks a particular document based at least in part on which search returned that particular document.

54. The system of claim 53, in which the result ranking engine ranks a particular document based at least in part on a degree to which that particular document satisfied the search criteria used in at least one search that returned that particular document.

55. The system of claim 53, further including a knowledge corpus including documents associated with concept nodes arranged in multiple taxonomies, and in which the result ranking engine ranks a particular document based at least in part on a weight with which the particular document is associated with a particular concept node.

56. The system of claim 53, in which the content provider includes an ordered list of searches executed by the search engine if indicated by the search result evaluator.

57. The system of claim 56, in which the search query generator forms the ordered list based at least in part on the user query.

58. The system of claim 57, in which the search query generator classifies the user query and forms the ordered list based at least in part on the classification of the user query.

59. The system of claim 56, in which the search query generator modifies the ordered list based at least in part on a search result provided by the search engine.

60. An automated content provider system including:

a user query input to receive a user query;

a search query generator, coupled to the user query input, the search query generator to generate an ordered list, S1, S2, . . . , SN, of at least two searches using the user query to formulate corresponding search criteria, each search including at least one search criteria that is different from the other searches, the search criteria selected from an automatically generated set of search criteria, the set of search criteria including at least two different search criteria defining different search specificities when using identical terms from the user query language;

a search engine, including a input coupled to the search query generator and an output, the search engine using the search criteria to perform ones of the S1, S2, . . . , SN searches, starting with the S1 search;

and to provide a corresponding search result at the search engine output;

a search result evaluator, coupled to the search engine output and an input of the search query generator, the search result evaluator to evaluate the search result to determine whether to perform a subsequent search from the ordered list based on whether existing search results yielded an insufficient number of documents relevant to the user query; and

a result ranking engine, coupled to the search engine output to rank documents returned in at least one search result, in which the result ranking engine includes an output user interface, in which the result ranking engine ranks a particular document based at least in part on which search returned that particular document.

61. The system of claim 60, in which the ordered list is ordered at least substantially according to specificity of the search criteria, in which S1 provides at least approximately more specific search criteria than S2, . . . , SN, and in which SN provides at least approximately more general search criteria than S1, S2, . . . , S(N−

1).

62. The system of claim 61, in which S1 provides more specific search criteria than S2, . . . , SN, and in which SN provides more general search criteria than S1, S2, . . . , S(N−

1).

63. The system of claim 62, in which the ordered list includes a list ordered throughout according to specificity of the search criteria.

64. The system of claim 63, in which the ordered list is ordered dynamically based at least in part on a result obtained from a previously-executed search on the user query.

65. The system of claim 61, in which specificity of the search criteria varies along at least one of a textual dimension, a linguistic dimension, and a thesaurus dimension.

66. The system of claim 61, in which the at least approximately more specific search criteria uses at least approximately more exact matching between a particular term in user query language and document language, and the at least approximately more general search criteria uses at least approximately less exact matching between a particular term in user query language and document language.

67. The system of claim 66, in which the search criteria specifies at least one predefined portion of the documents to be used in carrying out the search.

68. The system of claim 66, in which the at least approximately more specific search criteria uses a more specific portion of the documents, and the at least approximately more general search criteria uses a less specific portion of the documents.

69. The system of claim 68, in which the predefined portion of the documents uses at least one of a title portion, a summary portion, and an abstract portion.

70. The system of claim 60, in which the result ranking engine ranks a particular document based at least in part on a degree to which that particular document satisfied the search criteria used in at least one search that returned that particular document.

71. The system of claim 60, further including a knowledge corpus including documents associated with concept nodes arranged in multiple taxonomies, and in which the result ranking engine ranks a particular document based at least in part on a weight with which the particular document is associated with a particular concept node.

72. The system of claim 60, in which the content provider includes an ordered list of searches executed by the search engine if indicated by the search result evaluator.

73. The system of claim 72, in which the search query generator forms the ordered list based at least in part on the user query.

74. The system of claim 73, in which the search query generator classifies the user query and forms the ordered list based at least in part on the classification of the user query.

75. The system of claim 60, in which the search query generator modifies the ordered list based at least in part on a search result provided by the search engine.

76. The system of claim 60, in which the insufficient number of documents is determined by at least one of:

too few documents;

too many documents; and

the number of documents being outside a predetermined range.

77. A computer-implemented method of searching for documents that are relevant to a user'"'"'s query, the method including:

obtaining from a user a user query including at least some language;

using an automatically generated ordered list of S1, S2, . . . , SN searches, the searches using search criteria taken from a plurality of dimensions, each dimension including a plurality of search criteria ranging from approximately more specific to approximately more general, the plurality of dimensions including at least two different dimensions representing different approaches of varying search specificity; and

performing a search for documents relevant to the user query using one of the S1, S2, . . . , SN searches, starting with the S1 search, evaluating search results corresponding to the search performed to determine whether to perform a subsequent search and, if the evaluation deems the search results insufficient, then moving to and performing another search in the list.

78. The method of claim 77, in which the ordered list is ordered according to a varying specificity along each particular dimension while holding specificity of other dimensions constant.

79. The method of claim 77, in which each search in the ordered list includes a criteria from each dimension.

80. The method of claim 77, in which moving to and performing another search in the ordered list includes moving to and performing the next search in the list.

81. The method of claim 77, in which moving to and performing another search in the ordered list includes moving through the list in an at least approximately binary strategy that divides a portion of the ordered list to be searched into two segments and selects a particular segment of the ordered list based on an evaluation of the search results.

82. The method of claim 77, in which the ordered list is one of a plurality of ordered search lists that are mapped to query classes, and further including evaluating the user query for classification into a particular one of the query classes and using an ordered search list corresponding to the particular one of the query classes.

83. The method of claim 77, further including automatically reclassifying the user query to a different one of the query classes if results of a performed search provide an indication for such a reclassification.

84. The method of claim 77, in which the ordered list is one of a plurality of ordered lists, and further including automatically switching to a different one of the ordered lists if results of a performed search provide an indication for such a switching.