SELECTIVE INDEXING TO IMPROVE COMPLEX QUERYING OF ONLINE PROFESSIONAL NETWORK DATA

• US 20160092584A1
• Filed: 10/27/2014
• Published: 03/31/2016
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Nigam, Abhishek
• Granted Patent: US 10,068,032 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

The disclosed embodiments provide a system for processing data. During operation, the system obtains a query containing two or more hops in a graph of online professional network data and one or more predicates containing one or more attributes of the online professional network data. The graph includes nodes representing members and companies, and a set of edges representing relationships between pairs of nodes. The query also includes two or more input nodes, including a first input member and/or an input company, that are used to form a path containing the two or more hops, along with an output that matches the one or more predicates and includes one or more output members. Next, the system executes the query to obtain a subset of the online professional network data matching the query. Finally, the system provides the subset of the online professional network data in response to the query.

Claims

1. A method for processing data, comprising:

obtaining, at a computer system, a query comprising;

two or more hops in a graph of online professional network data, wherein the graph comprises;

a set of nodes comprising members and companies; and

a set of edges representing relationships between pairs of nodes in the set of nodes;

one or more predicates comprising one or more attributes of the online professional network data;

two or more input nodes, including one or more of a first input member and an input company, that are used to form a path comprising the two or more hops; and

an output that matches the one or more predicates and comprises one or more output members;

executing, by the computer system, the query to obtain a subset of the online professional network data matching the query; and

providing the subset of the online professional network data in response to the query.

2. The method of claim 1, further comprising:

indexing the online professional network data by an attribute from the query; and

providing the indexed online professional network data for use in executing the query.

3. The method of claim 2, wherein indexing the online professional network data by the attribute comprises:

identifying the attribute based on a search space of the query;

creating an index of the attribute for a first node with a number of edges that exceeds a threshold to reduce the search space of the query; and

omitting the index for a second node with a number of edges that does not exceed the threshold.

4. The method of claim 1, wherein the one or more predicates comprise:

an employment of the one or more output members at the input company; and

an overlap of employment at a common company between the first input member and the one or more output members.

5. The method of claim 1, wherein the one or more predicates comprise:

an employment of the first input member and the one or more output members at the input company; and

a connection of the first input member to the one or more output members.

6. The method of claim 1, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output comprises members in a four-hop path between the first and second input members; and

the one or more predicates comprise a minimum connection strength of edges in the four-hop path.

7. The method of claim 1, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output further comprises an output school and an output company in a four-hop path between the first and second input members; and

the one or more predicates comprise;

an education of the first input member and the one or more output members at the output school; and

an employment of the second input member and the one or more output members at the output company at the same time.

8. A method for processing data, comprising:

obtaining, at a computer system, a query comprising;

two or more hops in a graph of online professional network data, wherein the graph comprises;

a set of nodes comprising members and companies; and

a set of edges representing relationships between pairs of nodes in the set of nodes;

one or more predicates comprising one or more attributes of the online professional network data;

two or more input nodes, including an input member and an input influencer, that are used to form a path comprising the two or more hops; and

an output that matches the one or more predicates and comprises a set of output members;

executing, by the computer system, the query to obtain a subset of the online professional network data matching the query; and

providing the subset of the online professional network data in response to the query.

9. The method of claim 8, wherein the one or more predicates comprise:

membership of the set of output members in a second-degree network of the input member; and

following of the input influencer by the set of output members.

10. The method of claim 8, further comprising:

indexing the online professional network data by an attribute from the query; and

providing the indexed online professional network data for use in executing the query.

11. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a query comprising;

two or more hops in a graph of online professional network data, wherein the graph comprises;

a set of nodes comprising members and companies; and

a set of edges representing relationships between pairs of nodes in the set of nodes;

one or more predicates comprising one or more attributes of the online professional network data;

two or more input nodes, including one or more of a first input member and an input company, that are used to form a path comprising the two or more hops; and

an output that matches the one or more predicates and comprises one or more output members;

execute the query to obtain a subset of the online professional network data matching the query; and

provide the subset of the online professional network data in response to the query.

12. The apparatus of claim 11, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

index the online professional network data by an attribute from the query; and

provide the indexed online professional network data for use in executing the query.

13. The apparatus of claim 11, wherein the one or more predicates comprise:

an employment of the one or more output members at the input company; and

an overlap of employment at a common company between the first input member and the one or more output members.

14. The apparatus of claim 11, wherein the one or more predicates comprise:

an employment of the first input member and the one or more output members at the input company; and

a connection of the first input member to the one or more output members.

15. The apparatus of claim 11, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output comprises members in a four-hop path between the first and second input members; and

the one or more predicates comprise a minimum connection strength of edges in the four-hop path.

16. The apparatus of claim 11, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output further comprises an output school and an output company in a four-hop path between the first and second input members; and

the one or more predicates comprise;

an education of the first input member and the one or more output members at the output school; and

an employment of the second input member and the one or more output members at the output company at the same time.

17. A system, comprising:

one or more processors;

a query-processing non-transitory computer readable medium comprising instructions that, when executed by the one or more processors, cause the system to;

obtain a query comprising;

two or more hops in a graph of online professional network data, wherein the graph comprises;

a set of nodes comprising members and companies; and

a set of edges representing relationships between pairs of nodes in the set of nodes;

one or more predicates comprising one or more attributes of the online professional network data;

two or more input nodes, including one or more of a first input member and an input company, that are used to form a path comprising the two or more hops; and

an output that matches the one or more predicates and comprises an output member;

execute the query to obtain a subset of the online professional network data matching the query; and

provide the subset of the online professional network data in response to the query; and

an indexing non-transitory computer readable medium comprising instructions that, when executed by the one or more processors, cause the system to;

index the online professional network data by an attribute from the query; and

provide the indexed online professional network data for use in executing the query.

18. The system of claim 17, wherein the one or more predicates comprise:

an employment of the one or more output members at the input company; and

an overlap of employment at a common company between the first input member and the one or more output members.

19. The system of claim 17, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output comprises members in a four-hop path between the first and second input members; and

the one or more predicates comprise a minimum connection strength of edges in the four-hop path.

20. The system of claim 17, wherein:

the two or more input nodes comprise the first input member and a second input member;

the output further comprises an output school and an output company in a four-hop path between the first and second input members; and

the one or more predicates comprise;

an education of the first input member and the one or more output members at the output school; and

an employment of the second input member and the one or more output members at the output company at the same time.