Method and apparatus for querying shortest path of graph, and storage medium

Patent metadata

Field	Value
Publication number	US-11657091-B2
Application number	US-202016986120-A
Country	US
Kind code	B2
Filing date	Aug 5, 2020
Priority date	Sep 24, 2019
Publication date	May 23, 2023
Grant date	May 23, 2023

Abstract

The present disclosure provides a method and an apparatus for querying the shortest path of a graph, and a storage medium. The method includes: performing a breadth-first search in a distributed graph database with a start entity to be searched and an end entity to be searched as root nodes respectively, and obtaining a layer of new entities for each search; performing an intersection checking on the new entities and entities of the highest layer from a search set on an opposite side, so as to determine whether an intersection between the new entities and the entities of the highest layer exists; and when the intersection exists, determining intersection points, and performing path backtracking through the intersection points to find the shortest path from the start entity to the end entity.

First claim

What is claimed is:

1. A method for querying the shortest path of a graph, comprising:
performing a breadth-first search in a distributed graph database with a start entity to be searched and an end entity to be searched as root nodes respectively, and obtaining a layer of new entities for each breadth-first search;
performing an intersection checking on the new entities and entities of the highest layer from a search set on an opposite side; and
in response to determining that an intersection between the new entities and entities of the highest layer exists, determining the shortest path from the start entity to the end entity by performing path backtracking through intersection points included in the intersection;
wherein performing the breadth-first search in the distributed graph database with the start entity to be searched and the end entity to be searched as the root nodes respectively comprising:
creating a main thread and a thread pool;
determining entity requests of performing a breadth-first search on a current layer of entities in the distributed graph database with the start entity or the end entity as a root node;
dividing by the main thread, the entity requests into a plurality of batches of processing requests, and executing by each thread in the thread pool, each batch of the processing requests;
setting multi-threaded barriers on the main thread, and in response to search entities for each batch of processing requests being returned by each thread through the multi-threaded barriers, determining that the search for the current layer is completed.

2. The method according to claim 1 , performing the breadth-first search in the distributed graph database with the start entity to be searched and the end entity to be searched as the root nodes respectively comprising:
performing the breadth-first search in the distributed graph database alternatively with the start entity to be searched and the end entity to be searched as the root nodes respectively.

3. The method according to claim 1 , performing the breadth-first search in the distributed graph database with the start entity to be searched and the end entity to be searched as the root nodes respectively comprising:
with the start entity and the end entity as the root nodes respectively, performing the breadth-first search in the distributed graph database based on a thread blocking message queue and a greedy algorithm.

4. The method according to claim 3 , with the start entity and the end entity as the root nodes respectively, performing the breadth-first search in the distributed graph database based on a thread blocking message queue and a greedy algorithm further comprising:
determining a first entity request of performing a breadth-first search on a current layer of entities in the distributed graph database with the start entity as a root node, and determining a second entity request of performing a breadth-first search on a current layer of entities in the distributed graph database with the end entity as a root node;
allocating by the main thread, the first entity request to a first thread pool, and the second entity request to a second thread pool;
in response to the first thread pool completing execution of the first entity request earlier than the second thread pool, or in response to the second thread pool completing execution of the second entity request earlier than the first thread pool, obtaining a new layer of entities; and
reading by the main thread, the new layer of entities by applying a blocking message queue.

5. The method according to claim 1 , determining the shortest path from the start entity to the end entity by performing path backtracking through the intersection points, comprising:
determining paths from the start entity to the intersection points and paths from the intersection points to the end entity by performing two-way backtracking on the intersection points with a depth-first search; and
determining the shortest path from the start entity to the end entity by performing enumerated matching on the paths from the start entity to the intersection points and the paths from the intersection points to the end entity.

6. An apparatus for querying the shortest path of a graph, comprising:
one or more processors;
a memory storing instructions executable by the one or more processors;
wherein the one or more processors are configured to:
perform a breadth-first search in a distributed graph database with a start entity to be searched and an end entity to be searched as root nodes respectively, and obtaining a layer of new entities for each breadth-first search;
perform an intersection checking on the new entities and entities of the highest layer from a search set on an opposite side; and
in response to determining that an intersection between the new entities and entities of the highest layer exists, determine the shortest path from the start entity to the end entity by performing path backtracking through intersection points included in the intersection;
wherein the one or more processors are configured to:
create a main thread and a thread pool;
determine entity requests of performing a breadth-first search on a current layer of entities in the distributed graph database with the start entity or the end entity as a root node;
divide by the main thread, the entity requests into a plurality of batches of processing requests, and execute by each thread in the thread pool, each batch of the processing requests;
set multi-threaded barriers on the main thread, and in response to search entities for each of the batch processing requests being returned by each thread through the multi-threaded barriers, determine that the search for the current layer is completed.

7. The apparatus according to claim 6 , wherein the one or more processors are configured to:
perform the breadth-first search in the distributed graph database alternatively with the start entity to be searched and the end entity to be searched as the root nodes respectively.

8. The apparatus according to claim 6 , wherein the one or more processors are configured to:
with the start entity and the end entity as the root nodes respectively, perform the breadth-first search in the distributed graph database based on a thread blocking message queue and a greedy algorithm.

9. The apparatus according to claim 8 , wherein the one or more processors are configured to:
determine a first entity request of performing a breadth-first search a current layer of entities in the distributed graph database with the start entity as a root node, and determine a second entity request of performing a breadth-first search on a current layer of entities in the distributed graph database with the end entity as a root node;
allocate by the main thread, the first entity request to a first thread pool first, and the second entity request to a second thread pool;
in response to the first thread pool completing execution of the first entity request earlier than the second thread pool, or in response to the second thread pool completing execution of the second entity request earlier than the first thread pool, obtain a new layer of entities; and
read by the main thread, the new layer of entities by applying a blocking message queue.

10. The apparatus according to claim 6 , wherein the one or more processors are configured to:
determine paths from the start entity to the intersection points and paths from the intersection points to the end entity by performing two-way backtracking on the intersection points with a depth-first search; and
determine the shortest path from the start entity to the end entity by performing enumerated matching on the paths from

Assignees

• Beijing Baidu Netcom Sci & Tech Co Ltd

Inventors

• Deng Le
• Chen Kunbin
• Fang Jun

Classifications

• G06F16/9024 Primary

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

• G06F16/24

  Querying · CPC title

• G06F16/24558

  Binary matching operations · CPC title

• G06F16/288

  Entity relationship models · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title