Efficient computation of top-k aggregation over graph and network data

A computer-implemented method of determining a list of k nodes of a graph that have top-k highest aggregate scores over neighboring nodes within h-hops of said k nodes by using backward processing steps with a partial distribution and forward processing steps, said method comprising:

• a computer system obtaining a next node u of said graph for said partial distribution on a subset of nodes of said graph for which ƒ(u)≧γ, wherein said ƒ(u) is an initial score of said u, and wherein said γ is a predefined partial distribution threshold;
• for each node v within h-hops of said u, a processor of said computer system performing said backward processing steps that include determining an upper bound of an aggregate score of said v;
• said computer system repeating said obtaining said next node and said performing said backward processing until every node of said graph for which ƒ(u)≧γ is obtained as said next node by said obtaining;
• and
• subsequently, said computer system performing said forward processing steps that include:
• determining an aggregate score of said u by performing an aggregation operation that includes adding an initial score of said u to initial scores of neighboring nodes within h-hops of said u;
• and
• if said aggregate score of said u is greater than a lower bound of aggregate scores of said k nodes, then adding said u to said list of k nodes and updating said lower bound of said aggregate scores of said k nodes.

A computer-implemented method of determining a list of k nodes of a graph that have top-k highest aggregate scores over neighboring nodes within h-hops of said k nodes by using backward processing steps with a partial distribution, a first set of forward processing steps, and a second set of forward processing steps, said method comprising:

• a computer system obtaining in a first loop a next node u of said graph for said partial distribution on a subset of nodes of said graph for which ƒ(u)≧γ, wherein said ƒ(u) is an initial score of said u, and wherein said y is a predefined partial distribution threshold;
• for each node v within h-hops of said u, a processor of said computer system performing said backward processing steps that include determining an upper bound of an aggregate score of said v;
• subsequent to said performing said backward processing steps, said computer system performing said first set of forward processing steps that include:
• determining an aggregate score of said u by performing an aggregation operation that includes adding an initial score of said u to initial scores of neighboring nodes within h-hops of said u;
• if said aggregate score of said u is greater than a lower bound of aggregate scores of said k nodes, then adding said u to said list of k nodes and updating said lower bound of said aggregate scores of said k nodes;
• pruning one or more neighboring nodes within h-hops of said u, wherein said pruning said one or more neighboring nodes is based, in part, on a differential index between a neighboring node of said one or more neighboring nodes and said u and based, in part, on an upper bound of an aggregate score of said neighboring node;
• and
• adding said one or more neighboring nodes to said list of pruned nodes;
• repeating said obtaining in said first loop, said performing said backward processing and said performing said first set of forward processing steps until every node of said graph for which ƒ(u)≧γ is obtained as said next node u by said obtaining in said first loop;
• said computer system obtaining in a second loop a next top node u of said graph from a priority queue Q after determining said ƒ(u)<γ, said next top node u is not in said list of pruned nodes, and an upper bound of said aggregate score of said next top node u is greater than said lower bound of said aggregate scores of said k nodes;
• in response to determining said next top node u is not in said list of pruned nodes, said computer system performing said second set of forward processing steps of:
• determining said aggregate score of said next top node u;
• if said aggregate score of said next top node u is greater than a lower bound of said aggregate scores of said k nodes, then adding said next top node u to said list of k nodes and updating said lower bound of said aggregate scores of said k nodes;
• pruning a second one or more neighboring nodes within h-hops of said next top node u, wherein said pruning said second one or more neighboring nodes is based, in part, on a differential index between a second neighboring node of said second one or more neighboring nodes and said next top node u and based, in part, on an upper bound of an aggregate score of said second neighboring node;
• and
• adding said second one or more neighboring nodes to said list of pruned nodes;
• and
• repeating said obtaining said next top node and said performing said second set of forward processing until every node of said graph is processed by said obtaining said next top node.