Nearest-neighbor geographic search

• US 7,882,102 B2
• Filed: 09/10/2007
• Issued: 02/01/2011
• Est. Priority Date: 09/10/2007
• Status: Active Grant

• Current Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Original Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Inventors: Vechersky, Alexander
• Primary Examiner(s): Lu; Kuen S
• Assistant Examiner(s): HO, BINH VAN
• Application Number:
  US11/852,973
• Publication Number:
  US 20090070293A1
• Time in Patent Office: 1,240 Days
• Field of Search: 707/3, 707/716
• US Class Current: 707/716
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Disclosed herein is a method and apparatus for use in searching a geographic database to retrieve geographic objects one cell from a neighborhood of cells at a time. A cell neighborhood can be defined using a grid of cells and an initial, or center, point. A first neighborhood is identified based on its proximity to the initial search point, and corresponds to a first geographic area defined using the initial point and a distance from the initial search point in a number of directions. In a case that more than one cell neighborhood is used, each subsequent cell neighborhood is defined so that it excludes cells belonging to a previously-searched cell neighborhood. A subsequent neighborhood corresponds to a geographic area that is a distance from the initial point greater than the distance associated with a previously-searched neighborhood.

Claims

1. A computer-implemented method for accessing information from a geographic database, said method comprising:

receiving a search request, said search request identifying search criteria including an initial point;

identifying, using said initial point, a neighborhood of cells from a grid of cells associated with a geographic database;

searching said geographic database one cell at a time from said neighborhood to retrieve a number of points of interest (POIs) from a plurality of POIs identified in said geographic database, each POI retrieved having a corresponding location determined to be in a cell of said neighborhood, wherein searching said geographic database one cell at a time is performed until a predetermined number of POIs are retrieved or until all cells in said neighborhood have been searched to retrieve a number of POIs of said plurality, wherein after all cells of said neighborhood have been searched, said neighborhood is referred to as a previous neighborhood;

identifying a new neighborhood of cells from the grid of cells, the new neighborhood of cells comprising cells other than the cells in said previous neighborhood; and

searching said geographic database one cell at a time from said new neighborhood to retrieve a number of POIs of said plurality, each POI retrieved having a corresponding location determined to be in a cell of said new neighborhood;

wherein said new neighborhood of cells corresponds a new geographic area, the new geographic area defined using said initial point and a distance from said initial point, the distance being larger than a distance used to define a geographic area corresponding to said previously-searched neighborhood of cells.

2. The method of claim 1, wherein said searching said geographic database further comprises:

identifying a current cell of said neighborhood of cells;

performing a search of said geographic database to retrieve a number of POIs of said plurality, each of the retrieved POIs having a corresponding location in said current cell; and

filtering POIs of said plurality retrieved for said current cell using said search criteria, to generate a result set of POIs for said current cell.

3. The method of claim 1, wherein said identifying a neighborhood of cells further comprises:

identifying a geographic area using said initial point and a distance from said initial point;

identifying said neighborhood of cells from said grid of cells, said neighborhood corresponding to at least a portion of said identified geographic area.

4. The method of claim 1, wherein said searching said geographic database further comprises searching said geographic database one cell at a time from said new neighborhood until a predetermined number of POIs are retrieved.

5. The method of claim 1, wherein said searching said geographic database further comprises searching said geographic database one cell at a time from said new neighborhood until all cells in said new neighborhood have been searched to retrieve a number of POIs of said plurality.

6. The method of claim 1, said identifying a new neighborhood of cells further comprising:

identifying a new geographic area using said initial point and a distance from said initial point;

identifying said new neighborhood of cells from said grid of cells, said new neighborhood corresponding to at least a portion of said identified geographic area.

7. The method of claim 6, wherein said distance from said initial point is greater than a distance from said initial point used to identify a geographic area corresponding to a previously-searched neighborhood of cells.