SEARCHING A VERTEX IN A PATH

• US 20150186438A1
• Filed: 03/16/2015
• Published: 07/02/2015
• Est. Priority Date: 12/13/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yanagisawa, Hiroki
• Granted Patent: US 9,483,514 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models

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.

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.

2. The method of claim 1, further comprising determining whether one of the two endpoints of the path is the vertex.

3. The method of claim 1, wherein said step of determining a lower bound comprises looking up the lower bound in a table.

4. The method of claim 1, wherein said step of determining a lower bound comprises calculating a relationship between known shortest path distances.

5. The method of claim 1, wherein determining whether the lower bounds cover all points in the path comprises determining whether a lower bound associated with one endpoint is farther along the path than a lower bound associated with the other endpoint.

6. The method of claim 1, wherein the search of the uncovered points is a linear search.

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.

9. The system of claim 8, wherein the bound refinement module is further configured to determine whether one of the two endpoints of the path is the vertex.

10. The system of claim 8, wherein the bound index is a lookup table that includes shortest path lower bound values for fewer than all a total number of vertices.

11. The system of claim 8, wherein the bound refinement module is further configured to calculate a relationship between known shortest path distances to determine a lower bound.

12. The system of claim 8, wherein the bound refinement module is further configured to determine whether a lower bound associated with one endpoint is farther along the path than a lower bound associated with the other endpoint to determine whether the lower bounds cover all points in the path.

13. The system of claim 8, wherein the search module is configured to perform a linear search.