Text search ordered along one or more dimensions

• US 20030115187A1
• Filed: 12/17/2001
• Published: 06/19/2003
• Est. Priority Date: 12/17/2001
• Status: Active Grant

• Current Assignee: Avolin LLC
• Original Assignee: Consona CRM Incorporated (Aptean Superior Holdings, Inc.)
• Inventors: Bode, Andreas, Copperman, Max
• Granted Patent: US 7,206,778 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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-assisted method including:

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

(b) performing a search for documents relevant to the user query using at least one search criteria; and

(c) evaluating a first search result returned by the first search to determine whether to perform a subsequent search using different search criteria.

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

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

4. The method of claim 1, further including:

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

5. The method of claim 1, further including:

(d) ranking documents; and

(e) 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, further including selecting a search strategy based at least in part on the user query.

14. The method of claim 13, 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.

15. The method of claim 13, further including classifying the user query into a query class, and in which the selecting the search strategy is based on the query class in which the user query is classified.

16. The method of claim 15, 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.

17. The method of claim 15, 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.

18. The method of claim 17, 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.

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

20. The method of claim 17, 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.

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

22. The method of claim 17, 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.

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

24. The method of claim 17, 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.

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

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

27. A computer-assisted method including:

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

using an ordered list of S1, S2, . . . , SN searches, each search using at least one criteria that is different from the other searches; 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.

28. The method of claim 27, 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).

29. The method of claim 28, 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).

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

31. The method of claim 30, 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.

32. The method of claim 28, in which the search criteria use the language from the user query.

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

34. The method of claim 28, in which specificity of the search criteria varies along at least one of a textual dimension, a linguistic dimension, and a thesaurus dimension.

35. The method of claim 28, in which the search criteria uses at least one predefined portion of the documents.

36. The method of claim 35, 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 35, in which the predefined portion of the documents uses at least one of a title portion, a summary portion, and an abstract portion.

38. The method of claim 27, further including, before the returning the list, ranking the documents.

39. The method of claim 38, 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.

40. The method of claim 38, 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.

41. The method of claim 38, 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.

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

43. The method of claim 42, 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.

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

45. The method of claim 27, 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.

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

47. A computer-assisted 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 of S1, S2, . . . , SN searches, each search using at least one criteria that is different from the other searches, in which 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);

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.

48. The method of claim 47, 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.

49. The method of claim 47, 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.

50. The method of claim 47, 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.

51. The method of claim 47, in which the at least approximately more specific search criteria uses an at least approximately more exact matching of language 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 language from the user query to language in the documents.

52. The method of claim 47, 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.

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

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

a search engine, including a 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; and

in which the search query generator and search engine operate to generate or perform at least one subsequent search using different search criteria, if indicated by the evaluation of the search result by the search result evaluator.

55. The system of claim 54, further including a result ranking engine, coupled to the search engine output to rank documents returned in at least one search result, the result ranking engine including an output user interface.

56. The system of claim 55, in which the result ranking engine ranks a particular document based at least in part on which search returned that particular document.

57. The system of claim 55, 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.

58. The system of claim 55, 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.

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

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

61. The system of claim 60, 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.

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

63. 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 of S1, S2, . . . , SN searches using the user query to formulate corresponding search criteria, each search including at least one criteria that is different from the other searches;

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

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.

64. The system of claim 63, in which the 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, . . . , S(N−

1).

65. The method of claim 64, 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).

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

67. The method of claim 66, 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.

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

69. The system of claim 64, in which the at least approximately more specific search criteria uses at least approximately more exact matching between user query language and document language, and the at least approximately more general search criteria uses at least approximately less exact matching between user query language and document language.

70. The system of claim 69, in which the search criteria includes at least one predefined portion of the documents.

71. The system of claim 70, 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.

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

73. The system of claim 63, further including a result ranking engine, coupled to the search engine output to rank documents returned in at least one search result, the result ranking engine including an output user interface.

74. The system of claim 73, in which the result ranking engine ranks a particular document based at least in part on which search returned that particular document.

75. The system of claim 73, 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.

76. The system of claim 73, 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.

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

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

79. The system of claim 78, 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.

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

81. The system of claim 63, 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.

82. A computer-assisted 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 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; 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.

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

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

85. The method of claim 82, in which moving to and performing another search in the list includes moving to and performing the next search in the list.

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

87. The method of claim 82, 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 said particular one of the query classes.

88. The method of claim 87, further including 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.

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