Method for sharing landmarks for fast processing of top k cheapest path queries
Herein are techniques to accelerate finding a top few shortest paths between two vertices of a graph. In an embodiment, a computer calculates, for a graph that contains vertices that include landmark vertices, distances between each vertex and each landmark vertex. Based on the distances from each vertex to each landmark vertex, a top few shortest paths from a source vertex to a target vertex are calculated. In an embodiment, triangulation establishes a lower bound on a distance from a neighbor vertex of a current vertex to a target vertex of a query. In an embodiment, distance predictions based on the distance lower bounds are used to accelerate a K-A star search for the top few shortest paths.
1 . A method comprising:
storing, in a graph database, a graph that contains a plurality of graph vertices that include a plurality of landmark vertices;
calculating, for the graph, a plurality of distances between each vertex of the plurality of graph vertices and each vertex of the plurality of landmark vertices, including respective distances between a particular landmark vertex and each vertex of the plurality of graph vertices;
performing, after said calculating and storing, a first K-A star search that is based on the plurality of distances from each vertex of the plurality of graph vertices to each vertex of the plurality of landmark vertices, wherein the first K-A star search detects a first plurality of paths of shortest distance from a first source vertex of the plurality of graph vertices to a first target vertex of the plurality of graph vertices; and
performing after said performing said first K-A star search:
including an additional vertex of the plurality of graph vertices into the plurality of landmark vertices, and
executing, based on the plurality of distances from each vertex of the plurality of graph vertices to each vertex of the plurality of landmark vertices, including the additional vertex, a path query on the graph in the graph database to detect a second plurality of paths of shortest distance from a second source vertex of the plurality of graph vertices to a second target vertex of the plurality of graph vertices;
wherein:
a count of the first plurality of paths of shortest distance and a count of the second plurality of paths of shortest distance do not exceed a threshold;
the method is performed by one or more computers.
2 . The method of claim 1 wherein said storing the plurality of distances from each vertex of the plurality of graph vertices to each vertex of the plurality of landmark vertices comprises storing distances of the plurality of distances that originate or terminate at the vertex of the plurality of graph vertices as property(s) of the vertex.
3 . The method of claim 1 further comprising executing, based on said plurality of distances between each vertex of the plurality of graph vertices and each vertex of the plurality of landmark vertices, a plurality of queries of same said graph.
4 . The method of claim 3 wherein:
the plurality of queries of same said graph include a first query and a second query;
at least one selected from the group consisting of:
the first query has a different source vertex than the second query, and
the first query has a different target vertex than the second query.
5 . The method of claim 1 further comprising at least one of:
selecting the plurality of landmark vertices from a particular region of the graph, and
increasing the plurality of landmark vertices based on latency of query(s) of the graph.
6 . The method of claim 1 further comprising:
adding, to a subset of said plurality of graph vertices that is initially empty, a vertex from said plurality of graph vertices;
iteratively selecting said plurality of landmark vertices from said plurality of graph vertices by adding, to said subset of said plurality of graph vertices and to said plurality of landmark vertices, a vertex of said plurality of graph vertices that is furthest from said subset of said plurality of graph vertices.
7 . The method of claim 1 wherein:
the plurality of landmark vertices consists of: a) a first landmark vertex that is furthest from a seed vertex of said plurality of graph vertices, b) a second landmark vertex that is furthest from the first landmark vertex and the seed vertex, and c) a subset of said plurality of landmark vertices without the first landmark vertex and the second landmark vertex;
the method further comprises iteratively selecting said subset of the plurality of landmark vertices from said plurality of graph vertices by adding, to said subset of the plurality of landmark vertices, a vertex of said plurality of graph vertices that maximizes an arithmetic difference between: a) a sum of distances between all pairs of landmark vertices of the plurality of landmark vertices along paths that include said vertex, and b) a sum of distances between all pairs of landmark vertices of the plurality of landmark vertices.
8 . The method of claim 1 wherein a size of the plurality of landmark vertices is based on a logarithm of a size of the plurality of graph vertices.
9 . The method of claim 1 wherein said first K-A star search comprises triangulation based on said plurality of landmark vertices.
10 . The method of claim 9 wherein:
the method further comprises receiving a query that specifies said first source vertex and said first target vertex;
said triangulation based on said plurality of landmark vertices occurs either:
before said first K-A star search, or
after receiving said query that specifies said first source vertex and said first target vertex.
11 . The method of claim 9 wherein the first K-A star search comprises costing a partial path from said first source vertex to an intermediate vertex based on a distance from the intermediate vertex to said first target vertex through a landmark vertex of the plurality of landmark vertices.
12 . The method of claim 1 further comprises:
operating a queue that contains a plurality of intermediate paths of the graph;
generating a new path that contains an intermediate path of the plurality of intermediate paths;
before the queue becomes empty, detecting that a last vertex of said intermediate path was expanded a threshold amount of times.
13 . The method of claim 1 further comprising detecting financial fraud based on said first plurality of paths of shortest distance from the first source vertex of the plurality of graph vertices to the first target vertex of the plurality of graph vertices.
14 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
storing, in a graph database, a graph that contains a plurality of graph vertices that include a plurality of landmark vertices;
calculating, for the graph, a plurality of distances between each vertex of the plurality of graph vertices and each vertex of the plurality of landmark vertices, including respective distances between a particular landmark vertex and each vertex of the plurality of graph vertices;
performing, after said calculating and storing, a first K-A star search that is based on the plurality of distances from each vertex of the plurality of graph vertices to each vertex of the plurality of landmark vertices, wherein the first K-A star search detects a first plurality of paths of shortest distance from a first source vertex of the plurality of graph vertices to a first target vertex of the plurality of graph vertices; and
performing after said performing said first K-A star search:
including an additional vertex of the plurality of graph vertices into the plurality of landmark vertices, and
executing, based on the plurality of distances from each vertex of the plurality of graph vertices to each vertex of the plurality of landmark vertices, including the additional vertex, a path query on the graph in the graph database to detect a second plurality of paths of shortest distance from a second source vertex of the plurality of graph vertices to a second target vertex of the plurality of graph vertices;
wherein a count of the first plurality of paths of shortest distance and a count of the second plurality of paths of shortest distance do not exceed a threshold.
15 . The one or more non-transitory computer-readable media of claim 14 wherein the instructions further cause at least one of:
selecting the plurality of landmark vertices from a particular region of the graph, and
increasing the plurality of landmark vertices based on latency of query(s) of the graph.
16 . The one or more non-transitory computer-readable media of claim 14 wherein the instructions further cause:
adding, to a subset of said plurality of graph vertices that is initially empty, a vertex from said plurality of graph vertices;
iteratively selecting said plurality of landmark vertices from said plurality of graph vertices by adding, to said subset of said plurality of graph vertices and to said plurality of landmark vertices, a vertex of said plurality of graph vertices that is furthest from said subset of said plurality of graph vertices.
17 . The one or more non-transitory computer-readable media of claim 14 wherein:
the plurality of landmark vertices consists of: a) a first landmark vertex that is furthest from a seed vertex of said plurality of graph vertices, b) a second landmark vertex that is furthest from the first landmark vertex and the seed vertex, and c) a subset of said plurality of landmark vertices without the first landmark vertex and the second landmark vertex;
the instructions further cause iteratively selecting said subset of the plurality of landmark vertices from said plurality of graph vertices by adding, to said subset of the plurality of landmark vertices, a vertex of said plurality of graph vertices that maximizes an arithmetic difference between: a) a sum of distances between all pairs of landmark vertices of the plurality of landmark vertices along paths that include said vertex, and b) a sum of distances between all pairs of landmark vertices of the plurality of landmark vertices.
18 . The one or more non-transitory computer-readable media of claim 14 wherein said first K-A star search comprises triangulation based on said plurality of landmark vertices.
19 . The one or more non-transitory computer-readable media of claim 18 . wherein:
the instructions further cause receiving a query that specifies said first source vertex and said first target vertex;
said triangulation based on said plurality of landmark vertices occurs either:
before said first K-A star search, or
after receiving said query that specifies said first source vertex and said first target vertex.
20 . The one or more non-transitory computer-readable media of claim 14 . wherein the instructions further cause:
operating a queue that contains a plurality of intermediate paths of the graph;
generating a new path that contains an intermediate path of the plurality of intermediate paths;
before the queue becomes empty, detecting that a last vertex of said intermediate path was expanded a threshold amount of times.
21 . The one or more non-transitory computer-readable media of claim 18 . wherein the first K-A star search comprises costing a partial path from said first source vertex to an intermediate vertex based on a distance from the intermediate vertex to said first target vertex through a landmark vertex of the plurality of landmark vertices.