Query networks evaluation system and method

• US 9,607,052 B2
• Filed: 12/29/2009
• Issued: 03/28/2017
• Est. Priority Date: 12/29/2008
• Status: Active Grant

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Inventors: Shmueli, Oded, Ronen, Royi
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): BROMELL, ALEXANDRIA Y
• Application Number:
  US12/648,546
• Publication Number:
  US 20100306271A1
• Time in Patent Office: 2,646 Days
• Field of Search: 707/798, 707/773, 706/45, 705/319
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A query network is disclosed, comprising sets of nodes and edges connecting pairs of nodes. The nodes of the query network are associated with edge-defining queries. A method is taught for fully evaluating such a query network. A language is further disclosed for constructing queries. The query network may be used to model a social network, a professional network or the like.

Claims

1. A system which uses a query-network to represent social connections in a social network comprising:

a database apparatus of an online social network which is connected to a network and comprises;

an interface; and

a memory storing code; and

a processor coupled to the interface and the memory which executes the code, the code comprising;

code instructions for updating a plurality of nodes of a query-network representation of a plurality of social connections between a plurality of participants of a social network by performing the following for each one of said plurality of participants;

code instructions for using said interface for communicating with a respective said participant over said network to acquire a policy for establishing social connections between said respective participant and other participants of said plurality of participants;

code instructions for specifying an edge-defining query and an edge-accepting rule according to said policy;

code instructions for associating said edge-defining query and said edge-accepting rule with one of a plurality of nodes in said query-network representation;

code instructions for defining said plurality of social connections by automatically and recursively adding or subtracting a plurality of edges each connecting between a pair of said plurality of nodes until said edge-defining query and said edge-accepting rule of said plurality of nodes are complied with;

wherein each one of said plurality of edges represents a social connection that is complied with a respective said edge-accepting rule of one of said plurality of nodes and a respective said edge-defining query of another of said plurality of nodes.

2. The system of claim 1, wherein said edge-defining query defines a set of generated-edges to be added to said query-network representation.

3. The system of claim 2, wherein said set of generated-edges connects the node associated with said edge-defining query with another node selected from said plurality of nodes.

4. The system of claim 2, wherein said query-network representation further comprises a plurality of additional nodes specifying at least one of an additional edge-defining query and an additional edge-accepting rule.

5. The system of claim 4, wherein said edge-accepting rule defines a subset of generated-edges to be actually added to said set of edges.

6. The system of claim 1 wherein said edge-accepting rule comprises a datalog rule.

7. The system of claim 1 comprising a plurality of storage units, each containing a portion of said plurality of nodes and edges, connected to form said query-network representation.

8. The system of claim 1 wherein said plurality of nodes contains data pertaining to at least one of a group consisting of:

a social network, a professional network, an academic network, and an item network.

9. The system of claim 1, wherein said plurality of edges includes a set of directed edges.

10. The system of claim 1, wherein said plurality of edges includes a set of undirected edges.

11. The system of claim 1, wherein said plurality of edges comprises automatically and recursively subtracting edges.

12. The system of claim 1, wherein each said node is associated with a distinct edge-defining query that is defined according to a distinct policy from a plurality of policies.

13. A method of managing a query-network representing social connections in a social network using a processor, comprising:

using a database apparatus of an online social network which is connected to a network and having at least one hardware processor for updating a plurality of nodes of a query-network representation of a plurality of social connections between a plurality of participants of a social network by performing the following for each one of said plurality of participants;

using an interface of the database apparatus for communicating with a respective said participant over the network to acquire a policy for establishing social connections between said respective participant and other participants of said plurality of participants;

using said at least one hardware processor for specifying an edge-defining query and an edge-accepting rule according to said policy;

using said at least one hardware processor associating said edge-defining query and said edge-accepting rule with one of a plurality of nodes in said query-network representation;

using said at least one hardware processor for defining said plurality of social connections by automatically and recursively adding or subtracting a plurality of edges each connecting between a pair of said plurality of nodes until said edge-defining query and said edge-accepting rule of said plurality of nodes are complied with;

wherein each one of said plurality of edges represents a social connection that is complied with a respective said edge-acceptance rule of one of said plurality of nodes and a respective said edge-defining query of another of said plurality of nodes.

14. The method of claim 13, wherein said recursively adding or subtracting comprises:

selecting a node from said plurality of nodes;

evaluating the selected node according to the edge-defining query associated therewith;

selecting another node from said plurality of nodes and repeating said evaluating; and

terminating said recursively adding or subtracting when all members of said plurality of nodes have been evaluated.

15. The method of claim 14 wherein said evaluating, comprising:

adding to said plurality of edges the members of a set of generated-edges defined by at least one edge-defining query associated with said selected node;

repeating said adding when said set of generated-edges is not an empty set; and

selecting said another node from said nodes and repeating said evaluating when said set of generated-edges is an empty set.

16. The method of claim 14 wherein said selecting comprises:

generating a subset of nodes which are connected to the previously selected node via a path containing less edges than the radius of the query-network representation; and

selecting a member of said subset.

17. The method of claim 14, wherein said plurality of nodes are evaluated according to an edge-defining query associated with a selected node.

18. The method of claim 14, wherein said plurality of edges are used in an evaluation of an edge-defining query associated with a selected node.

19. The method of claim 13, further comprising:

partitioning said social network into a plurality of sub-networks;

fully evaluating each said sub-network such that all edges defined by said edge-defining query become members of said set of edges; and

merging said evaluated sub-networks.

20. The method of claim 19, wherein said merging is performed according to a Backward-Radius Triggering (BRT) evaluation algorithm.