Data storage and querying

Patent metadata

Field	Value
Publication number	US-12380164-B2
Application number	US-202318400366-A
Country	US
Kind code	B2
Filing date	Dec 29, 2023
Priority date	Oct 8, 2021
Publication date	Aug 5, 2025
Grant date	Aug 5, 2025

Abstract

Computer-implemented methods, apparatus, and systems for data storage and data query are described. During data storage, the number of neighboring graph nodes in each starting graph node in directed graph graph data to be stored is determined, and a data storage mode is determined according to the number of neighboring graph nodes. When the data storage mode is not an ultra-large node data storage, node data, neighbor information, outgoing edge index feature information, and outgoing edge data of the starting graph node are stored in the same data fragment. When the data storage mode is an ultra-large node data storage, node data, neighbor information, outgoing edge index feature range information, and outgoing edge data are stored in a starting graph node data fragment, and the outgoing edge data and outgoing edge data storage address information of the starting graph node are stored in at least two outgoing edge data fragments.

First claim

What is claimed is:

1. A computer-implemented method for data storage, comprising:
determining the number of neighboring graph nodes of each starting graph node in directed graph graph data to be stored;
determining a data storage mode is an ultra-large node data storage mode or not based on the number of neighboring graph nodes of each starting graph node;
for a first starting graph node, when the data storage mode is not the ultra-large node data storage mode,
storing node data, neighbor information, outgoing edge index feature information, and outgoing edge data of the first starting graph node to a first starting graph node data fragment of a first data storage medium, wherein:
the outgoing edge index feature information comprises outgoing edge index feature information of all outgoing edges of the first starting graph node, and
each outgoing edge index feature has a mapping relationship with an outgoing edge data index that is used for indexing corresponding outgoing edge data stored in the first starting graph node data fragment; or

for a second starting graph node, when the data storage mode is the ultra-large node data storage mode,
storing node data, neighbor information, outgoing edge index feature range information, and outgoing edge data fragment index of the second starting graph node in a second starting graph node data fragment in a second data storage medium, wherein the outgoing edge index feature range information comprises multiple outgoing edge index feature ranges having a mapping relationship with the outgoing edge data fragment index, and
storing outgoing edge data and outgoing edge data storage address information of the second starting graph node in at least two outgoing edge data fragments in a third data storage medium, wherein the outgoing edge data storage address information comprises a two-dimensional array that comprises an outgoing edge index feature of the outgoing edge data and a relative storage address of the outgoing edge data in an outgoing edge data fragment.

2. The computer-implemented method according to claim 1 , wherein the data storage mode is determined relative to all starting graph nodes in the directed graph graph data, or the data storage mode is determined respectively relative to each starting graph node in the directed graph graph data.

3. The computer-implemented method according to claim 1 , wherein the node data comprises a node identifier and a node attribute, the neighbor information comprises a node identifier and a neighbor attribute, the neighbor attribute comprise basic information of all outgoing edges, and the outgoing edge data comprises an outgoing edge identifier and an outgoing edge attribute.

4. The computer-implemented method according to claim 3 , wherein basic information of an outgoing edge comprises a terminal graph node identifier of the outgoing edge and an outgoing edge index feature of the outgoing edge, and the outgoing edge identifier comprises a terminal graph node identifier and an outgoing edge index feature.

5. The computer-implemented method according to claim 4 , wherein the basic information of the outgoing edge further comprises at least one of a node type of a terminal graph node of the outgoing edge or an outgoing edge type of the outgoing edge, and the outgoing edge identifier further comprises an outgoing edge type.

6. The computer-implemented method according to claim 3 , wherein the node data further comprises node metadata, and the node metadata comprises at least one of a node index feature or a node type.

7. The computer-implemented method according to claim 1 , wherein an index feature comprises a timestamp, the outgoing edge index feature information comprises outgoing edge timestamps of all outgoing edges after being sorted in descending order, and the outgoing edge index feature range information comprises multiple outgoing edge timestamp ranges after being sorted in descending order.

8. The computer-implemented method according to claim 7 , wherein each of the multiple outgoing edge timestamp ranges stores the largest outgoing edge timestamp and the smallest outgoing edge timestamp of a corresponding outgoing edge data fragment.

9. The computer-implemented method according to claim 1 , wherein the first starting graph node data fragment and the second starting graph node data fragment further store reverse neighbor information, or the outgoing edge data fragment further stores an outgoing edge quantity.

10. The computer-implemented method of claim 1 , wherein when the number of neighbors of each starting graph node exceeds a preset threshold, and the data storage mode is determined to be the ultra-large node data storage mode, the storing the node data, the neighbor information, outgoing edge index feature range information, and outgoing edge data fragment index of the second starting graph node in a second starting graph node data fragment in a second data storage medium comprises:
storing the node data of the second starting graph node data fragment, neighbor index feature range, neighbor data fragment index, the outgoing edge index feature range information, and the outgoing edge data fragment index of the second starting graph node data fragment in the second data storage medium, and
storing the neighbor information to at least two neighbor data fragments of a fourth data storage medium, respectively,
wherein the neighbor index feature range comprises multiple neighbor index feature ranges that have a mapping relationship with the neighbor data fragment index.

11. The computer-implemented method according to claim 1 , wherein the first data storage medium, the second data storage medium, and the third data storage medium respectively comprise one or more data storage media, and a portion of the first data storage medium, the second data storage medium, and the third data storage medium respectively use the same data storage medium to implement.

12. The computer-implemented method according to claim 1 , wherein a non-ultra-large node data storage mode and the ultra-large node data storage mode are implemented by using a key-value pair storage mode.

13. A computer-implemented method for data query, comprising:
in response to receiving a data query request related to directed graph graph data initiated by a user, determining a data fragment index of a target query graph node based on a node identifier of the target query graph node, wherein the directed graph graph data are stored in at least one of a first data storage medium, a second data storage medium, or a third data storage medium;
reading a starting graph node data fragment indexed by the data fragment index from the first data storage medium or the second data storage medium into a memory of a data query device;
parsing the starting graph node data fragment to obtain a parsed starting graph node data fragment;
obtaining, according to the parsed starting graph node data fragment, query data of the data query request from a local parsed data of the data query device or from an outgoing edge data fragment of the third data storage medium; and
providing the query data to the user.

14. The computer-implemented method according to claim 13 , wherein the directed graph graph data comprise node data, neighbor information, and outgoing edge data of a starting graph node, the node data comprise a node identifier and a node attribute, the neighbor information comprises node identifier information and a neighbor attribute, the neighbor attribute comprises basic information of all outgoing edges, and the outgoing edge data comprise an outgoing edge identifier and an outgoing edge at

Assignees

• Alipay Hangzhou Inf Tech Co Ltd

Inventors

• Zhang Songqing
• Jiang Jin
• Fu Zhijun
• Zhu Bingpeng
• Yuan Lin

Classifications

• G06F16/90335

  Query processing · CPC title

• G06F16/9024 Primary

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