Searching a vertex in a path

• US 9,483,514 B2
• Filed: 03/16/2015
• Issued: 11/01/2016
• Est. Priority Date: 12/13/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yanagisawa, Hiroki
• Primary Examiner(s): TO, BAOQUOC N
• Application Number:
  US14/659,139
• Publication Number:
  US 20150186438A1
• Time in Patent Office: 596 Days
• Field of Search: 707/716, 707/769, 707/E17.014, 707/741, 707/758, 705/6
• 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 by calculating a relationship between known shortest path distances; 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 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.

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

6. 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 by calculating a relationship between known shortest path distances; 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.

7. 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 hardware 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, said lower bound being determined by calculating a relationship between known shortest path distances, 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.

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

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

10. The system of claim 7, 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.

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