Importance ranking for a hierarchical collection of objects

• US 7,809,736 B2
• Filed: 05/02/2006
• Issued: 10/05/2010
• Est. Priority Date: 05/02/2005
• Status: Expired due to Fees

• Current Assignee: Brown University
• Original Assignee: Brown University
• Inventors: Wicks, John R., Greenwald, Amy
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US11/919,262
• Publication Number:
  US 20090319565A1
• Time in Patent Office: 1,617 Days
• Field of Search: 707/723, 707/736, 707/748, 707/754, 707/755, 707/795, 707/797, 707/803
• US Class Current: 707/755
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

A system and method of obtaining an importance ranking for a hierarchical collection of objects. The hierarchical collection of objects is represented as a tree containing a plurality of nodes, and each node to be ranked is represented as a respective leaf node of the tree. To obtain the ranking of the respective leaf nodes, the system and method locally ranks nodes contained in one or more sub-trees of the tree, in which each sub-tree has a depth equal to one. Next, the local rankings are effectively propagated up the tree, and the local rankings are aggregated at each level of the hierarchy, until a final importance ranking for the leaf nodes is obtained.

Claims

1. A method executed by a processor to obtain an importance ranking for a plurality of objects in a referential database, comprising the steps of:

representing said plurality of objects as a plurality of leaf nodes of a tree, wherein each of the plurality of leaf nodes of said tree has an associated initial ranking and an associated initial set of non-local references to at least another one of the plurality of leaf nodes of said tree;

partitioning said tree into at least one subtree having a root node and a plurality of leaf nodes directly connected to the root node, said at least one subtree including at least one subtree having at least one leaf node corresponding to at least one of the plurality of leaf nodes of said tree;

in a first generating step, for each leaf node included in said at least one subtree, generating a set of local references to at least one leaf node within said subtree, and generating a set of non-local references to at least one leaf node of said tree outside of said subtree;

in a second generating step, generating a local ranking for the plurality of leaf nodes within said subtree based upon the sets of local references generated in the first generating step;

in a third generating step, generating a set of non-local references to at least one leaf node of said tree outside of said subtree based upon the sets of non-local references generated in the first generating step;

scaling said rankings associated with said plurality of leaf nodes included in said subtree by the local ranking generated in the second generating step to obtain a scaled ranking for the plurality of leaf nodes within said subtree;

deleting said plurality of leaf nodes included in said subtree from said tree;

in the event said tree has at least one remaining leaf node, repeating said partitioning step, said first, second, and third generating steps, said scaling step, and said deleting step;

otherwise, outputting the scaled ranking as the importance ranking for said plurality of objects.

2. The method of claim 1 further including the step of expressing each of said initial ranking, said local ranking, said scaled ranking, and said importance ranking as a probability distribution.

3. The method of claim 2 wherein said initial ranking associated with each of the plurality of leaf nodes of said tree is the probability distribution [1].

4. The method of claim 1 wherein said second generating step includes expressing each of the sets of local references generated in the first generating step as a vector, constructing a matrix of local references by concatenating the vectors of local references, and applying a base ranking technique to the matrix of local references to obtain said local ranking.

5. The method of claim 4 wherein said base ranking technique is a non-hierarchical ranking technique.

6. The method of claim 4 wherein said third generating step includes expressing each of the sets of non-local references generated in the first generating step as a vector, constructing a matrix of non-local references by concatenating the vectors of non-local references, and multiplying the matrix of non-local references by said local ranking to generate the set of non-local references to at least one leaf node of said tree outside of said subtree.

7. The method of claim 1 wherein said outputting step includes outputting said importance ranking for said plurality of objects to a computer display.

8. A system for obtaining an importance ranking for a plurality of objects in a referential database, comprising:

at least one processor operative to execute at least one program out of at least one memory for processing data corresponding to said plurality of objects in said referential database; and

at least one computer display,

said program being operative;

to represent said plurality of objects as a plurality of leaf nodes of a tree, wherein each of the plurality of leaf nodes of said tree has an associated initial ranking and an associated initial set of non-local references to at least another one of the plurality of leaf nodes of said tree;

to partition said tree into at least one subtree having a root node and a plurality of leaf nodes directly connected to the root node, said at least one subtree including at least one subtree having at least one leaf node corresponding to at least one of the plurality of leaf nodes of said tree;

for each leaf node included in said at least one subtree, to generate a set of local references to at least one leaf node within said subtree, and to generate a set of non-local references to at least one leaf node of said tree outside of said subtree;

to generate a local ranking for the plurality of leaf nodes within said subtree based upon the sets of local references;

to generate a set of non-local references to at least one leaf node of said tree outside of said subtree based upon the sets of non-local references;

to scale said rankings associated with said plurality of leaf nodes included in said subtree by the local ranking to obtain a scaled ranking for the plurality of leaf nodes within said subtree;

to delete said plurality of leaf nodes included in said subtree from said tree;

in the event said tree has at least one remaining leaf node, to repeat said partitioning of said tree into at least one subtree, said generation of the set of local references and the set of non-local references for each leaf node of said subtree, said generation of said local ranking for the plurality of leaf nodes within said subtree, said generation of said set of non-local references based upon the sets of non-local references for each leaf node of said subtree, said scaling of said rankings associated with the plurality of leaf nodes within said subtree, and said deletion of the plurality of leaf nodes included in said subtree from said tree; and

otherwise, to output the scaled ranking to the computer display as the importance ranking for said plurality of objects.

9. The system of claim 8 wherein said program is operative to express each of said initial ranking, said local ranking, said scaled ranking, and said importance ranking as a probability distribution.

10. The system of claim 9 wherein said program is operative to express said initial ranking associated with each of the plurality of leaf nodes of said tree as the probability distribution [1].

11. The system of claim 8 wherein said program is operative to express each of the sets of local references as a vector, to construct a matrix of local references by concatenating the vectors of local references, and to apply a base ranking technique to the matrix of local references to obtain said local ranking.

12. The system of claim 11 wherein said base ranking technique is a non-hierarchical ranking technique.

13. The system of claim 11 wherein said program is operative to express each of the sets of non-local references as a vector, to construct a matrix of non-local references by concatenating the vectors of non-local references, and to multiply the matrix of non-local references by said local ranking to generate the set of non-local references to at least one leaf node of said tree outside of said subtree.

14. The system of claim 8 further including at least one host computer, at least one server computer, and at least one network, said at least one host computer and said at least one server computer being connected to said network, and wherein said at least one processor is included in said server computer.

15. The system of claim 14 wherein said computer display is included in said host computer.

16. The system of claim 8 further including at least one host computer, at least one server computer, and at least one network, said at least one host computer and said at least one server computer being connected to said network, and wherein said at least one processor is included in said host computer.

17. The system of claim 8 wherein said referential database comprises a linked database.

18. The system of claim 17 wherein said linked database comprises the world wide web.

19. The system of claim 8 wherein said referential database comprises a database of documents with citations.

20. The system of claim 8 wherein said referential database comprises an e-mail database.