Importance ranking for a hierarchical collection of objects
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification