SEARCHING A VERTEX IN A PATH
First Claim
Patent Images
1. A method for searching a path for a vertex, comprising:
- iteratively removing from consideration points in a path, until a number of remaining points is below a path size threshold, by;
determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex; and
removing from consideration points closer to each respective endpoint than the respective lower bound to produce a shortened path; and
searching the shortened path with a processor to determine whether the vertex is in the shortened path.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods and systems for searching a path for a vertex include iteratively removing from consideration points in a path, until a number of remaining points is below a path size threshold. The iterative removal includes determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex and removing from consideration points closer to each respective endpoint than the respective lower bound to produce a shortened path. The shortened path is searched with a processor to determine whether the vertex is in the shortened path.
-
Citations
13 Claims
-
1. A method for searching a path for a vertex, comprising:
-
iteratively removing from consideration points in a path, until a number of remaining points is below a path size threshold, by; determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex; and removing from consideration points closer to each respective endpoint than the respective lower bound to produce a shortened path; and searching the shortened path with a processor to determine whether the vertex is in the shortened path. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A non-transitory computer readable storage medium comprising a computer readable program for searching a path for a vertex, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
-
iteratively removing from consideration points in a path, until a number of remaining points is below a path size threshold, by; determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex; and removing from consideration points closer to the respective endpoints than the respective endpoints to produce a shortened path; and searching the shortened path with a processor to determine whether the vertex is in the shortened path.
-
-
8. A system for searching a path for a vertex, comprising:
-
a bound index configured to provide lower bound information for a shortest path between two vertices; a bound refinement module comprising a processor configured to iteratively remove from consideration points in the path until a number of remaining points is below a size threshold, by determining, for each of two endpoints in a path, a lower bound for a shortest path distance from each respective endpoint to a target vertex using the bound index and removing from consideration points closer to each respective endpoint than the respective lower bound to produce a shortened path; and a search module configured to search points on the shortened path for a vertex. - View Dependent Claims (9, 10, 11, 12, 13)
-
Specification