Using a weighted tree to determine document relevance

• US 7,962,480 B1
• Filed: 07/31/2007
• Issued: 06/14/2011
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Li, Xiong, Yuhong, Feng, Shicong, Zhao, Yong
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Moser; Bruce M
• Application Number:
  US11/831,841
• Time in Patent Office: 1,414 Days
• Field of Search: 707/7, 707/100, 707/102, 707/104.1, 707/999.007, 707/999.1, 707/999.102, 707/999.104, 707/803, 707/804, 707/729, 707/730, 707/750
• US Class Current: 707/729
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

The relevance of documents is automatically determined based upon a weighted tree. Terms considered to be relevant are assigned to the leaf nodes of a tree data structure. A location can also be specified in a leaf node, indicating where in a document the term must appear to be considered relevant. Internal nodes of the tree are assigned operators (e.g., add, maximum or minimum). The connections between nodes are assigned weights. A relevance value for a given document is calculated as a function of occurrence in the document of terms assigned to leaves, operators assigned to internal nodes, and weights assigned to the associated node connections. Weighted trees can be used to process search queries. Documents with high relevance scores calculated against the tree can be returned to a user as the results to a query.

Claims

1. A computer implemented method for automatically determining document relevance, the method comprising:

representing a plurality of terms as a tree data structure comprising internal nodes and leaf nodes interconnected by respective node connections;

assigning to each of the leaf nodes of the tree data structure a respective one of the terms;

assigning to at least one of the leaf nodes a respective location specifying a designated location for the term assigned to the leaf node to appear within a document;

assigning a respective operator to each of the internal nodes of the tree data structure;

assigning a respective weight to each of the node connections in the tree data structure; and

calculating a respective relevance value for at least one document as a function of occurrence in the at least one document of the terms respectively assigned to the leaf nodes of the tree data structure, the operators assigned to internal nodes of the tree data structure, and the weights assigned to the associated node connections and, for each of the leaf nodes assigned a respective location, occurrence of the term assigned to the leaf node at the location in the at least one document specified by the respective location assigned to the leaf node.

2. The method of claim 1 wherein:

each assigned location is one from a group consisting of;

uniform resource locator, address, content, header and metadata.

3. The method of claim 1 wherein:

each assigned operator is one from a group consisting of;

maximum, minimum and add.

4. The method of claim 1 further comprising:

calculating a relevance value for at least one document for the terms assigned to leaf nodes of the tree structure; and

presenting to a user as results of a search query at least one document resulting from the search query meeting a given relevance threshold value.

5. The method of claim 4 wherein the given relevance threshold value comprises at least one of:

a minimum document relevance value; and

a specified number of documents having highest respective relevance values to present to the user as the results of the search query.

6. The method of claim 1 further comprising receiving terms, operators and weights of the tree data structure from at least one source from a group of sources consisting of:

a user interface;

at least one file;

a command line; and

a computer program.

7. At least one computer readable medium containing a computer program product for automatically determining document relevance, the computer program product comprising program code that, when executed by a computer, causes the computer to perform operations comprising:

representing a plurality of terms as a tree data structure comprising internal nodes and leaf nodes interconnected by respective node connections;

assigning to each of the leaf nodes of the tree data structure a respective one of the terms;

assigning to at least one of the leaf nodes a respective location specifying a designated location for the term assigned to the leaf node to appear within a document;

assigning a respective operator to each of the internal nodes of the tree data structure;

assigning a respective weight to each node connections in the tree data structure; and

calculating a respective relevance value for at least one document as a function of occurrence in the at least one document of the terms respectively assigned to the leaf nodes of the tree data structure, the operators assigned to parent internal nodes of the corresponding leaf nodes, and the weights assigned to the associated node connections and, for each of the leaf nodes assigned a respective location, occurrence of the term assigned to the leaf node at the location in the at least one document specified by the respective location assigned to the leaf node.

8. The computer program product of claim 7 wherein:

each assigned location is one from a group consisting of;

uniform resource locator, address, content, header and metadata.

9. The computer program product of claim 7 wherein:

each assigned operator is one from a group consisting of;

maximum, minimum and add.

10. The computer program product of claim 7 further comprising:

program code for calculating a relevance value for at least one document for the terms assigned to leaf nodes of the tree structure; and

program code for presenting to a user as results of a search query at least one document resulting from the search query meeting a given relevance threshold value.

11. The computer program product of claim 10 wherein the given relevance threshold value comprises at least one of:

a minimum document relevance value; and

a specified number of documents having highest respective relevance values to present to the user as the results of the search query.

12. The computer program product of claim 7 further comprising program code for receiving terms, operators and weights of the tree data structure from at least one source from a group of sources consisting of:

a user interface;

at least one file; and

a command line; and

a computer program.

13. A computer system for automatically determining document relevance, the computer system comprising computer hardware configured to perform operations comprising:

representing a plurality of terms as a tree data structure comprising internal nodes and leaf nodes interconnected by respective node connections;

assigning to each of the leaf nodes of the tree data structure a respective one of the terms;

assigning to at least one of the leaf nodes a respective location specifying a designated location for the term assigned to the leaf node to appear within a document;

assigning a respective operator to each of the internal nodes of the tree data structure;

assigning a respective operator to each of the node connections in the tree data structure; and

calculating a respective relevance value for at least one document as a function of occurrence in the at least one document of the terms respectively assigned to the leaf nodes of the tree data structure, the operators assigned to parent internal nodes of the corresponding leaf nodes, and the weights assigned to the associated node connections and, for each of the leaf nodes assigned a respective location, occurrence of the term assigned to the leaf node at the location in the at least one document specified by the respective location assigned to the leaf node.

14. The computer system of claim 13 wherein:

each assigned location is one from a group consisting of;

uniform resource locator, address, content, header and metadata.

15. The computer system of claim 13 wherein:

each assigned operator is one from a group consisting of;

maximum, minimum and add.

16. The computer system of claim 13 wherein the computer hardware is to perform operations comprising:

calculating a relevance value for at least one document for the terms assigned to leaf nodes of the tree structure; and

presenting to a user as results of a search query at least one document resulting from the search query meeting a given relevance threshold value.

17. The computer system of claim 16 wherein the given relevance threshold value comprises at least one of:

a minimum document relevance value; and

a specified number of documents having highest respective relevance values to present to the user as the results of the search query.

18. A computer implemented method for automatically determining document relevance, the method comprising:

accessing a tree structure representing a plurality of terms, the tree data structure comprising internal nodes and leaf nodes interconnected by respective node connections, each of the leaf nodes of the tree data structure being assigned to a respective one of the terms, at least one of the leaf nodes being assigned to a respective location specifying a designated location for the term assigned to the leaf node to appear within a document, a respective operator being assigned to each of the internal nodes of the tree data structure, and a respective weight being assigned to each of the node connections in the tree data structure; and

calculating a respective relevance value for at least one document as a function of occurrence in the at least one document of the terms respectively assigned to the leaf nodes of the tree data structure, the operators assigned to internal nodes of the tree data structure, and the weights assigned to the associated node connections and, for each of the leaf nodes assigned a respective location, occurrence of the term assigned to the leaf node at the location in the at least one document specified by the respective location assigned to the leaf node.