Search System

• US 20080133508A1
• Filed: 11/12/2007
• Published: 06/05/2008
• Est. Priority Date: 07/02/1999
• Status: Active Grant

• Current Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Original Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Inventors: Rowles, Christopher David, Raskutti, Bhavani Laxman, Wen, Wilson, Ryan, Simon David, JIANG, Jason
• Granted Patent: US 7,870,118 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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

A search engine and system for data, such as Internet web pages, including a query analyser for processing a query to assign respective weights to terms of the query and to generate a query vector including the weights, and an index network responsive to the query vector to output at least one index to data in response to the query. The index network is a self-generating neural network built using training examples derived from a feature extractor. The feature extractor is used during both the search and training phase. A clusterer is used to group search results.

Claims

1-54. -54. (canceled)

55. A search system, including:

query means for processing a query to assign respective weights to terms of said query based on the grammatical structure of the query and the meaning of the terms of the query and to generate a query vector including said weights;

index means responsive to said query vector to output at least one index to data in response to said query, said index means being a self generating neural network having nodes of weight vectors representing categories and terms of said data, said nodes further including pointers to other nodes, and leaf nodes of said network including an index to said data;

feature extraction means for extracting indices and respective terms of said data as term weight pairs, the weights of the pairs being based on the importance and uniqueness of component ngrams of the terms of an indexed document and the terms being extracted on the basis of the distribution of ngrams in a document space of indexed documents of said data; and

wherein said neural network is generated on the basis of training examples including said term weight pairs, and the format of said query vectors and said weight vectors of said network is generated on the basis of said training examples.

56. A search system as claimed in claim 55, wherein the weights in said query vector are assigned based on the importance of the terms in said query.

57. A search system as claimed in claim 55, wherein said query means analyses said terms using a dictionary and thesaurus of terms of said data.

58. A search system as claimed in claim 55, wherein said query means generates sections of terms which form said query, said sections representing grammatical elements.

59. A search system as claimed in claim 58, wherein the terms in said sections are allocated to grammatical categories for determining said weights.

60. A search system as claimed in claim 59, wherein said query means generates a plurality of said sections, and parses said sections to select a set of sections forming said query vector.

61. A search system as claimed in claim 60, wherein said sections are selected on the basis of syntactical structure.

62. A search system as claimed in claim 57, wherein the query vector includes respective fields for terms of said dictionary.

63. A search system as claimed in claim 55, wherein said weights are linguistic weights.

64. A search system as claimed in claim 60, wherein said sections are key-centred phrase structure frames with a key grammatical category, and said query means executes frame instantiation on the terms of said query and generates a frame relation graph of said frames.

65. A search system as claimed in claim 64, wherein said query means executes parallel parsing on said frame relation graph to generate a nodal tree structure of the query to generate said query vector.

66. A search system as claimed in claim 55, wherein said query vector has said weights placed in respective fields corresponding to terms of at least one term list.

67. A search system as claimed in claim 55, wherein said index means compares said query vector with the weight vectors of said nodes to select said at least one index in response to said query.

68. A search system as claimed in claim 67, wherein said comparing is executed from the upper level of the tree structure to the lower level, with paths in the structure being selected on the basis of the comparison between the vectors.

69. A search system as claimed in claim 68, wherein said index means obtains the product of said query vector and the text vector of the nodes of a level of said structure, and obtains said product for nodes of a succeeding level of said structure which are connected to nodes for which the product has exceeded a predetermined threshold.

70. A search system as claimed in claim 69, wherein the indices of nodes having a query vector node vector product higher than a predetermined threshold are output by said index means.

71. A search system as claimed in claim 55, wherein said weights are normalised, and said network is searched in response to a query by determining the inner product of said query vector and said weight vectors to locate nodes producing a high inner product.

72. A search system as claimed in claim 70 or 71, including cluster means for processing indices output by said index means in response to said query, generating term frequency vectors for data indexed by said indices, comparing similarities between the indexed data on the basis of a distance between said frequency vectors and generating content based categories on the basis of said distances and placing the output indices into said categories for display.

73. A search system as claimed in claim 72, wherein the feature extraction means receives content features of said categories from said cluster means and selects a unique descriptive feature for each category.

74. A search system as claimed in claim 72, wherein said cluster means generates a plurality of clusters of the indices and determines the quality of each cluster on the basis of inter-cluster distances and intra-cluster distances between term frequency vectors for the indices of the clusters relative to a term frequency vector centroid for each cluster.

75. A search system as claimed in claim 55, wherein the feature extraction means accesses respective unique and important terms of said data and adds said terms to said dictionary.

98. A search system as claimed in claim 55, wherein said terms represent a word or phrase.

76. A search engine stored on a computer readable storage medium, including:

a query analyser for processing a query to assign respective weights to terms of said query based on the grammatical structure of the query and the meaning of the terms of the query and to generate a query vector including said weights;

an index network responsive to said query vector to output at least one index to data in response to said query, said index network being a self generating neural network having nodes of weight vectors representing categories and terms of said data, said nodes further including pointers to other nodes, and leaf nodes of said network including an index to said data; and

a feature extractor for extracting indices and respective terms of said data as term weight pairs, the weights of the pairs being based on the importance and uniqueness of component ngrams of the terms of an indexed document and the terms being extracted on the basis of the distribution of ngrams in a document space of index documents of said data; and

wherein said neural network is generated on the basis of training examples including said term weight pairs, and the format of said query vectors and weights vectors of said network is generated on the basis of said training examples.

77. A search engine as claimed in claim 76, wherein the weights of said query vector are assigned based on the importance of the terms in said query.

78. A search engine as claimed in claim 76, wherein said query analyser analyses said terms using a dictionary and thesaurus of terms of said data.

79. A search engine as claimed in claim 76, wherein said query analyser generates sections of terms which form said query, said sections representing grammatical elements.

80. A search engine as claimed in claim 79, wherein the terms in said sections are allocated to grammatical categories for determining said weights.

81. A search engine as claimed in claim 80, wherein said query analyser generates a plurality of said sections, and parses said sections to select a set of sections forming said query vector.

82. A search engine as claimed in claim 81, wherein said sections are selected on the basis of syntactical structure.

83. A search engine as claimed in claim 78, wherein the query vector includes respective fields for terms of said dictionary.

84. A search engine as claimed in claim 76, wherein said weights are linguistic weights.

85. A search engine as claimed in claim 81, wherein said sections are key-centred phrase structure frames with a key grammatical category, and said query analyser executes frame instantiation on the terms of said query and generates a frame relation graph of said frames.

86. A search engine as claimed in claim 85, wherein said query analyser executes parallel parsing on said frame relation graph to generate a nodal tree structure of the query to generate said query vector.

87. A search engine as claimed in claim 76, wherein said query vector has said weights placed in respective fields corresponding to terms of at least one term list.

88. A search engine as claimed in claim 76, wherein said index network compares said query vector with the weight vectors of said nodes to select said at least one index in response to said query.

89. A search engine as claimed in claim 88, wherein said comparing is executed from the upper level of the tree structure to the lower level, with paths in the structure being selected on the basis of the comparison between the vectors.

90. A search engine as claimed in claim 89, wherein said index network obtains the product of said query vector and the text vector of the nodes of a level of said structure, and obtains said product for nodes of a succeeding level of said structure which are connected to nodes for which the product has exceeded a predetermined threshold.

91. A search engine as claimed in claim 90, wherein the indices of nodes having a query vector node vector product higher than a predetermined threshold are output by said index network.

92. A search engine as claimed in claim 76, wherein said weights are normalised, and said network is searched in response to a query by determining the inner product of said query vector and said weight vectors to locate nodes producing a high inner product.

93. A search engine as claimed in claim 91 or 92, including a clusterer for processing indices output by said index network in response to said query, generating term frequency vectors for data indexed by said indices, comparing similarities between the indexed data on the basis of a distance between said frequency vectors and generating content based categories on the basis of said distances and placing the output indices into said categories for display.

94. A search engine as claimed in claim 93, wherein the feature extractor receives content features of said categories from said clusterer and selects a unique descriptive feature for each category.

95. A search engine as claimed in claim 93, wherein said clusterer generates a plurality of clusters of the indices and determines the quality of each cluster on the basis of inter-cluster distances and intra-cluster distances between term frequency vectors for the indices of the clusters relative to a term frequency vector centroid for each cluster.

96. A search engine as claimed in claim 76, wherein the feature extractor accesses respective unique and important terms of said data and adds said terms to said dictionary.

97. A search engine as claimed in claim 76, wherein said neural network is a self generating neural network and the format of said query vectors and vectors of nodes of said network is generated on the basis of said training examples.

99. A search engine as claimed in claim 76, wherein said terms represent a word or phrase.