Graph Data Search Method and Apparatus

Patent metadata

Field	Value
Publication number	US-2017286484-A1
Application number	US-201715618587-A
Country	US
Kind code	A1
Filing date	Jun 9, 2017
Priority date	Dec 9, 2014
Publication date	Oct 5, 2017
Grant date	—

Abstract

A graph data search method and apparatus, where the method includes obtaining a query request including a query condition that carries a start graph node, the query request queries a first to-be-queried graph node matching the query condition from a graph data set, and the graph data set includes the start graph node, a plurality of to-be-queried graph nodes, an association relationship between the start graph node and the plurality of graph nodes, and an association relationship between each to-be-queried graph node and another graph node, filtering out, according to the query condition and a preset available resource condition, a second to-be-queried graph node that does not meet the query condition and an association relationship in the graph data set that includes the second to-be-queried graph node, and performing a query in the reduction subgraph using the query condition.

First claim

What is claimed is:

1 . A graph data search method, comprising:
obtaining a query request, wherein the query request comprises a query condition that carries a start graph node, wherein the query request queries a first to-be-queried graph node in a graph data set matching the query condition, and wherein the graph data set comprises the start graph node, a plurality of to-be-queried graph nodes, an association relationship between the start graph node and the plurality of to-be-queried graph nodes, and an association relationship between each to-be-queried graph node and another to-be-queried graph node in the plurality of to-be-queried graph nodes; filtering out, according to the query condition and a preset available resource condition, a second to-be-queried graph node in the graph data set that does not meet the query condition and an association relationship in the graph data set comprising the second to-be-queried graph node in order to obtain a reduction subgraph, wherein the reduction subgraph comprises the start graph node, the first to-be-queried graph node matching the query condition, and an association relationship between the start graph node and the first to-be-queried graph node; and performing a query in the reduction subgraph using the query condition to obtain the first to-be-queried graph node.

2 . The method according to claim 1 , wherein filtering out the second to-be-queried graph node in the graph data set and a corresponding association relationship to obtain the reduction subgraph comprises:
generating a query topology structure according to the query condition, wherein the query topology structure comprises a plurality of query nodes and a query topology relationship between each query node and another query node in the plurality of query nodes; and filtering out, according to the query topology relationship between the query nodes in the query topology structure, a preset first access cost of accessing the first to-be-queried graph node, and the preset available resource condition, the second to-be-queried graph node in the graph data set whose access cost exceeds the preset first access cost and the association relationship in the graph data set comprising the second to-be-queried graph node in order to obtain the reduction subgraph, wherein a resource occupied by the reduction subgraph does not exceed the preset available resource condition.

3 . The method according to claim 2 , wherein filtering out the second to-be-queried graph node in the graph data set and the association relationship in the graph data set comprising the second to-be-queried graph node in order to obtain the reduction subgraph comprises:
reading a query node and a graph node matching the query node stored in storage space, wherein a query node in the query topology structure and a graph node matching the query node are stored in the storage space, wherein the query node comprises a start query node, wherein the graph node comprises the start graph node, and wherein the start graph node matches the start query node; determining whether the reduction subgraph comprises the read graph node; adding the read graph node to the reduction subgraph when the reduction subgraph does not comprise the read graph node; determining that the resource occupied by the reduction subgraph does not exceed the available resource condition; calculating an access cost of a to-be-queried graph node adjacent to the read graph node, and filtering out the second to-be-queried graph node whose access cost exceeds the first access cost and the association relationship comprising the second to-be-queried graph node whose access cost exceeds the first access cost, according to the query topology relationship between the query nodes in the query topology structure; and outputting, according to a preset dynamic reduction parameter, an access sequence that is to be stored into the storage space, wherein an access cost of a to-be-queried graph node in the access sequence does not exceed the first access cost, and wherein the preset dynamic reduction parameter controls a quantity of to-be-queried graph nodes in the access sequence.

4 . The method according to claim 2 , wherein filtering out the second to-be-queried graph node in the graph data set and the association relationship in the graph data set comprising the second to-be-queried graph node in order to obtain the reduction subgraph comprises:
reading a query node and a graph node matching the query node stored in storage space, wherein a query node in the query topology structure and a graph node matching the query node are stored in the storage space, wherein the query node comprises a start query node, wherein the graph node comprises the to-be-queried graph node, and wherein the start graph node matches the start query node; determining whether the reduction subgraph comprises the read graph node; adding the read graph node to the reduction subgraph when the reduction subgraph does not comprise the read graph node; determining that the resource occupied by the reduction subgraph does not exceed the available resource condition; calculating an access cost of a to-be-queried graph node adjacent to the read graph node, and filtering out the second to-be-queried graph node whose access cost exceeds the first access cost and the association relationship comprising the second to-be-queried graph node whose access cost exceeds the first access cost, according to the query topology relationship between the query nodes in the query topology structure; and outputting, according to a preset dynamic reduction parameter, an access sequence that is to be stored into the storage space, wherein an access cost of a to-be-queried graph node in the access sequence does not exceed the first access cost, and wherein the preset dynamic reduction parameter controls a quantity of to-be-queried graph nodes in the access sequence.

5 . The method according to claim 2 , wherein filtering out the second to-be-queried graph node and the association relationship comprising the second to-be-queried graph node in order to obtain the reduction subgraph comprises the following steps:
step A: setting a quantity of graph nodes in the reduction subgraph to 0, setting a quantity of query nodes and a quantity of graph nodes matching the query nodes to 0, wherein a query node and a graph node matching the query node are stored in storage space, and setting a dynamic reduction parameter to a first preset value; step B: storing a start query node in the query topology structure and the start graph node into the storage space, wherein the start graph node matches the start query node; step C: reading the query node and the graph node matching the query node stored in the storage space; step D: determining whether the reduction subgraph comprises the read graph node, wherein the read graph node comprises the start graph node or the to-be-queried graph node; step E: adding the read graph node to the reduction subgraph when the reduction subgraph does not comprise the read graph node, and determining that the resource occupied by the reduction subgraph does not exceed the preset available resource condition; step F: calculating an access cost of a to-be-queried graph node adjacent to the read graph node, and filtering out the second to-be-queried graph node whose access cost exceeds the preset first access cost and the association relationship comprising the second to-be-queried graph node whose access cost exceeds the preset first access cost, according to the query topology relationship between the query nodes in the query topology structure, and outputting, according to the dynamic reduction parameter, an access sequence that is to be stored into the storage space, wherein an access cost of a to-be-queried graph

Assignees

• Huawei Tech Co Ltd

Inventors

• Fan Wenfei
• Wang Xin
• Wu Yinghui

Classifications

• G06F17/30958

  Physics · mapped topic

• G06F17/30979

  Physics · mapped topic

• G06F17/30454 Primary

  Physics · mapped topic

• G06F16/9024 Primary

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

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title