Search system

• US 7,296,009 B1
• Filed: 06/30/2000
• Issued: 11/13/2007
• Est. Priority Date: 07/02/1999
• Status: Expired due to Term

• Current Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Original Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Inventors: Rowles, Christopher David, Raskutti, Bhavani Laxman, Jiang, Jason, Wen, Wilson, Ryan, Simon David
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US10/030,331
• Time in Patent Office: 2,692 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5
• US Class Current: 1/1
• 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. A search system for use in a computer system, including:

query means for processing a query to the computer system to assign respective weights to terms of said query based on grammatical structure of the query and for generating a query vector including said weights in respective fields for said terms, wherein said query means generates a plurality of sections of terms which form said query, said sections representing grammatical elements and the terms in said sections being allocated to grammatical categories for determining said weights, and parses said sections to select a set of sections forming said query vector, 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, and 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; and

index means for processing said query vector to output at least one index to data in response to said query.

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

3. A search system as claimed in claim 1, wherein said weights are assigned to said query based on the meaning of the terms of the query.

4. A search system as claimed in claim 1, wherein said query means analyses said terms using a dictionary and thesaurus of terms of said data, and said respective fields are for terms of said dictionary.

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

6. A search system as claimed in claim 1, wherein said weights are linguistic weights.

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

8. A search system as claimed in claim 1, wherein said index means maintains a hierarchal structure of nodes representing said data and indices to said data, said nodes each include a text vector having weights for terms of said data, and leaf nodes of said structure including indices to said data.

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

10. A search system as claimed in claim 9, 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.

11. A search system as claimed in claim 1, including feature extraction means for accessing respective unique and important terms of said data and adding said terms to said dictionary.

12. A search system as claimed in claim 1, including 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 said document space and wherein said index means is a neural network generated on the basis of training examples including said term weight pairs.

13. A search system as claimed in claim 12, 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.

14. A search system as claimed in claim 1, wherein said terms represent one of a word and a phrase.

15. A search system for use in a computer system, including:

query means for processing a query to the computer system to assign respective weights to terms of said query based on grammatical structure of the query and for generating a query vector including said weights in respective fields for said terms; and

index means for processing said query vector to output at least one index to data in response to said query, wherein said index means maintains a hierarchal structure of nodes representing said data and indices to said data, said nodes each including a text vector having weights for terms of said data and leaf nodes of said structure including indices to said data, wherein said index means compares said query vector with the text vectors of said nodes to select said at least one index in response to said query, said comparing being executed from an upper level of the hierarchal structure to a lower level, with paths in the structure being selected on the basis of the comparison between the vectors, and 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.

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

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

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

19. A search system as claimed in claim 18, wherein said sections are key centered 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.

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

21. A search system as claimed in claim 20, 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.

22. A search system as claimed in claim 21, including feature extraction means for receiving content features of said categories from said cluster means and selecting a unique descriptive feature for each category.

23. A search system as claimed in claim 21, 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.

24. A search system as claimed in claim 15, wherein said index means is a self generating neural network having nodes of weight vectors representing categories and terms of said data, said nodes further including pointers to a first child node and a next sibling node, and leaf nodes of said network including an index to said data.

25. A search system as claimed in claim 24, wherein said weights are normalized, 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.

26. A search engine stored on a computer readable storage medium for use in a computer system, including:

a query analyser for processing a query to the computer system to assign respective weights to terms of said query based on grammatical structure of the query and for generating a query vector including said weights in respective fields for said terms, wherein said query analyser generates a plurality of sections of terms which form said query, said sections representing grammatical elements and the terms in said sections being allocated to grammatical categories for determining said weights, and parses said sections to select a set of sections forming said query vector, 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, and 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; and

an index network for processing said query vector to output at least one index to data in response to said query.

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

28. A search engine as claimed in claim 26, wherein said weights are assigned to said query based on the meaning of the terms of the query.

29. A search engine as claimed in claim 26, wherein said query analyser analyses said terms using a dictionary and thesaurus of terms of said data, and said respective fields are for terms of said dictionary.

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

31. A search engine as claimed in claim 26, wherein said weights are linguistic weights.

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

33. A search engine as claimed in claim 26, wherein said index network maintains a hierarchal structure of nodes representing said data and indices to said data, said nodes each include a text vector having weights for terms of said data, and leaf nodes of said structure including indices to said data.

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

35. A search engine as claimed in claim 34, 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.

36. A search engine as claimed in claim 26, including feature extraction means for accessing respective unique and important terms of said data and adding said terms to said dictionary.

37. A search engine as claimed in claim 26, including 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 said document space and wherein said index means is a neural network generated on the basis of training examples including said term weight pairs.

38. A search engine as claimed in claim 37, 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.

39. A search engine as claimed in claim 26, wherein said terms represent one of a word and a phrase.

40. A search engine stored on a computer readable storage medium for use in a computer system, including:

a query analyser for processing a query to the computer system to assign respective weights to terms of said query based on grammatical structure of the query and for generating a query vector including said weights in respective fields for said terms; and

an index network for processing said query vector to output at least one index to data in response to said query, wherein said index network maintains a hierarchal structure of nodes representing said data and indices to said data, said nodes each include a text vector having weights for terms of said data and leaf nodes of said structure including indices to said data, wherein said index network compares said query vector with the text vectors of said nodes to select said at least one index in response to said query, said comparing being executed from an upper level of the hierarchal structure to a lower level, with paths in the structure being selected on the basis of the comparison between the vectors, 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.

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

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

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

44. A search engine as claimed in claim 43, 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.

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

46. A search engine as claimed in claim 45, 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.

47. A search engine as claimed in claim 45, including feature extraction means for receiving content features of said categories from said cluster means and selecting a unique descriptive feature for each category.

48. A search engine as claimed in claim 46, 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.

49. A search engine as claimed in claim 40, wherein said index network is a self generating neural network having nodes of weight vectors representing categories and terms of said data, said nodes further including pointers to a first child node and a next sibling node, and leaf nodes of said network including an index to said data.

50. A search engine as claimed in claim 49, wherein said weights are normalized, 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.