Statistics-aware sub-graph query engine

Patent metadata

Field	Value
Publication number	US-11734350-B2
Application number	US-202016763183-A
Country	US
Kind code	B2
Filing date	Apr 29, 2020
Priority date	Apr 29, 2020
Publication date	Aug 22, 2023
Grant date	Aug 22, 2023

Abstract

Methods and systems are presented for retrieving data associated with one or more portions of a graph by a computer system. Multiple graph indices are generated based on the graph. Each of the multiple graph indices stores records of data representing the graph in different formats. Upon receiving a request for accessing a sub-graph of the graph, edge-based attributes of the sub-graph are analyzed. The sub-graph may be divided into a first portion and a second portion of the sub-graph. A first graph index may be selected for retrieving records associated with the first portion of the sub-graph based on the edge-based attributes of the first portion of the sub-graph. A second graph index may be selected for retrieving records associated with the second portion of the sub-graph based on the edge-based attributes of the second portion of the sub-graph.

First claim

What is claimed is:

1. A system, comprising:
a non-transitory memory; and
one or more hardware processors coupled with the non-transitory memory and configured to read instructions from the non-transitory memory to cause the system to perform operations comprising:
receiving, from a device, a query for accessing a sub-graph of a graph, wherein the graph comprises a set of vertices and a plurality of edges connecting the set of vertices;
identifying, from the set of vertices of the graph, a subset of vertices associated with the sub-graph based on the query;
analyzing edge-based attributes associated with the subset of vertices in the sub-graph;
selecting, from a plurality of graph indices that indexes the graph using different formats, a first graph index for processing at least a portion of the query based on the edged-based attributes associated with the subset of vertices;
processing at least the portion of the query using the first graph index;
obtaining data related to the sub-graph based at least in part on the processing; and
transmitting the data to the device.

2. The system of claim 1 , wherein the analyzing the edge-based attributes associated with the subset of vertices comprises:
comparing an edge-based attribute associated with each vertex in the subset of the vertices against an edge-based threshold.

3. The system of claim 2 , wherein the operations further comprise:
analyzing edge-based statistics associated with the graph; and
determining the edge-based threshold based on the analyzing the edge-based statistics.

4. The system of claim 2 , wherein the edge-based threshold represents a threshold number of edges associated with a vertex.

5. The system of claim 1 , wherein the operations further comprise:
dividing the subset of the vertices into a first group of vertices and a second group of vertices;
processing a first portion of the query associated with the first group of vertices using the first graph index; and
obtaining first data associated with a first portion of the sub-graph based on the processing the first portion of the query using the first graph index.

6. The system of claim 5 , wherein the operations further comprise:
processing a second portion of the query associated with the second group of vertices using a second graph index from the plurality of graph indices;
obtaining second data associated with a second portion of the sub-graph based on the processing the second portion of the query using the second graph index; and
combining the first data and the second data.

7. The system of claim 5 , wherein each vertex in the first group of vertices has an edge-based attribute above an edge-based threshold, and wherein each vertex in the second group of vertices has an edge-based attribute below the edge-based threshold.

8. A method, comprising:
receiving, by one or more hardware processors from a device, a request for accessing data associated with a portion of a graph, wherein the graph comprises a set of vertices;
identifying, from the set of vertices of the graph, a subset of vertices associated with the portion of the graph;
analyzing, by the one or more hardware processors, attributes associated with the subset of vertices in the sub-graph;
dividing, by the one or more hardware processors, the subset of vertices into a first group of vertices and a second group of vertices;
obtaining, by the one or more hardware processors, first data associated with the first group of vertices using a first graph index that indexes the graph in a first format;
obtaining, by the one or more hardware processors, second data associated with the second group of vertices using a second graph index that indexes the graph in a second format different from the first format; and
transmitting the first and second data to the device.

9. The method of claim 8 , wherein the first graph index comprises graph data associated with the graph that are arranged according to a first ordering scheme, and wherein the second graph index comprises the graph data that is arranged according to a second ordering scheme different from the first ordering scheme.

10. The method of claim 9 , wherein the first ordering scheme specifies that the graph data is arranged based on a first priority ranking among a set of attributes associated with the graph data, and wherein the second ordering scheme specifies that the graph data is arranged based on a second priority ranking among the set of attributes that is different from the first priority ranking.

11. The method of claim 8 , further comprising:
determining a distribution of degrees across the set of vertices in the graph, wherein the degrees represent, for each vertex in the set of vertices, a number of edges associated with the vertex; and
determining an edge-based threshold based on the distribution, wherein the analyzing the attributes associated with the subset of vertices comprises comparing, for each vertex in the subset of vertices, an edge-based attribute of the vertex against the edge-based threshold.

12. The method of claim 8 , wherein the request is for accessing information associated with edges between vertices in the subset of vertices.

13. The method of claim 8 , wherein the graph represents transactions among a plurality of user accounts, wherein each vertex in the set of vertices represents a user account, and wherein each edge between two vertices represents a transaction between two user accounts corresponding to the two vertices.

14. The method of claim 8 , wherein the graph represents a social network, wherein each vertex in the set of vertices represents a user account, and wherein each edge between two vertices represents an interaction between two user accounts corresponding to the two vertices.

15. A non-transitory machine-readable medium having stored thereon machine-readable instructions executable to cause a machine to perform operations comprising:
receiving, from a device, a request for accessing a sub-graph of a graph, wherein the graph comprises a set of vertices and a plurality of edges connecting the set of vertices;
identifying, from the set of vertices of the graph, a subset of vertices associated with the sub-graph based on the request;
analyzing attributes associated with the subset of vertices in the sub-graph;
selecting, from a plurality of graph indices that indexes the graph using different formats, a first graph index for processing at least a portion of the query based on a comparison between the attributes associated with the subset of vertices and a threshold;
processing at least the portion of the request using the first graph index;
obtaining data related to the sub-graph based at least in part on the processing; and
transmitting the data to the device.

16. The non-transitory machine-readable medium of claim 15 , wherein the operations further comprise:
generating the sub-graph based on the data; and
presenting the sub-graph on the device.

17. The non-transitory machine-readable medium of claim 15 , wherein the operations further comprise:
analyzing characteristics associated with the graph; and
determining the threshold based on the analyzing the characteristics.

18. The non-transitory machine-readable medium of claim 15 , wherein the threshold represents a threshold number of edges associated with a vertex.

19. The non-transitory machine-readable medium of claim 15 , wherein the operations further comprise:
dividing the subset of the vertices into a first group of vertices and a second group of ve

Assignees

• Paypal Inc

Inventors

• Dai Yunjing
• Huang Jie
• Gu Jun
• Qiao Zhenyu

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/90335

  Query processing · CPC title