System and process for identifying objects and/or points nearby a given object or point

• US 7,305,417 B2
• Filed: 10/21/2005
• Issued: 12/04/2007
• Est. Priority Date: 01/28/2003
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Microsoft Corporation
• Inventors: Gray, James
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US11/256,376
• Publication Number:
  US 20060036629A1
• Time in Patent Office: 774 Days
• Field of Search: 707/3, 707/4, 707/10, 707/104.1, 701/201, 701/202, 701/206, 701/212, 701/214, 702/5, 340/988, 340/990, 340/991, 340/992, 340/993, 340/995.1, 340/995.14
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and process is presented that identifies nearby objects and/or points in relation to a base object or point. An object or point is nearby if it resides within a prescribed area around the base point. The identification is based on information accessed from a database of geometric data. The identification of nearby neighbors begins by dividing the geographic system defined by said geometric data into a plurality of zones. The zone in which each object or point resides and the zones intersected by the prescribed area are determined. The nearby objects and/or points of interest are then identified by initially considering only those that are identified as residing in the zones intersected by the prescribed area. The search for nearby neighbors can be further refined by limiting the objects and/or points considered to those with locations within the lateral extent and/or within the height of the prescribed area.

Claims

1. A computer-implemented process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point which reside within a search area around the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest, said process comprising:

a dividing step for dividing the geographic system defined by said geometric data into a plurality of zones each forming a strip of the same prescribed zone height and assigning an integer zone number to each strip;

an assigning step for determining what zone each object or point in the database resides and assigning that zone number to the object or point;

an identifying step for identifying the zone number of every zone intersected by the search area; and

for each object or point associated with each zone number identified as intersected by the search area,

a first determining step for determining whether a first coordinate of the object or point under consideration defining its location along the width of the strip in which it resides is within the range of the first coordinate of the base point less a distance defining the extent of the search area in a first direction along the width of the strip in which the base point resides and the first coordinate of the base point plus the same distance defining the extent of the search area in the opposite direction along the width of the strip in which the base point resides,

whenever it is determined that the first coordinate of the object or point under consideration is within the specified range, a first designating step for designating said object or point as a nearby neighbor candidate,

a second determining step for determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than said distance defining the extent of the search area in either direction along the width of the strip, and

whenever it is ascertained that said actual distance is equal to or less than said distance defining the extent of the search area in either direction along the width of the strip, a second designating step for designating the candidate object or point as a nearby neighbor of the base point.

2. A process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point having the spherical coordinates (“

@ra”

, “

@dec”

) which resides within a search area of a prescribed radius (“

@r) from the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of spherical system with spherical coordinates comprising the declination (dec) and right ascension (ra) of the object or point from the center of a sphere representing the spherical system, comprising;

a dividing step for dividing the sphere into a plurality of zones each forming a declination strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the south pole being designated as zone number 0;

a first determining step for determining what zone each object or point in the database resides and assigning that zone number to the object or point;

an identifying step for identifying the zone number of every zone intersected by the search area; and

for each object or point associated with each zone number identified as intersected by the search area,

a second determining step for determining whether the ra value of the object or point under consideration is between the range of @ra−

@r′ and

@ra+@r′

, where @r′

is @r corrected for right ascension compression corresponding to the dec value of the base point,

whenever it is determined that the ra value of the object or point under consideration is between the range of @ra−

@r′ and

@ra+@r′

, a first designating step for designating said object or point as a nearby neighbor candidate,

a third determining step for determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than @r, and

whenever it is ascertained that said actual distance is equal to or less than @r, a second designating step for designating the candidate object or point as a nearby neighbor of the base point.

3. The process of claim 2, wherein the first determining step, comprises:

a declination sum dividing step for dividing the sum of the declination (“

dec”

) of the object or point under consideration in degrees and 90 degrees by the prescribed zone height; and

a rounding step for rounding down to the nearest integer value.

4. The process of claim 2, wherein the identifying step, comprises:

a first computing step for computing the zone number of the northernmost zone intersected by the search area by,

adding @dec plus 90 degrees plus @r,

dividing the resulting sum by the prescribed zone height, and

rounding up to the nearest integer value;

a second computing step for computing the zone number of the southernmost zone intersected by the search area by,

adding @dec and 90 degrees;

subtracting @r from the resulting sum,

dividing the resulting difference by the prescribed zone height, and

rounding down to the nearest integer value; and

a deeming step for deeming the zone numbers of the northernmost and southernmost zones intersected by the search area, and the zone number of every zone between said northernmost and southernmost zones, as the zone numbers of the zones intersected by the search area.

5. The process of claim 2, wherein the second determining step, comprises a computing step for computing @r′

as equal to @r/(cos(abs(dec))+ε

)), where E is an arbitrary small number intended to prevent division by zero should the (cos(abs(dec))term equal zero.

6. The process of claim 2, further comprising, prior to performing the first designating step, an elimination step for eliminating the object or point as a nearby neighbor candidate if its dec value is outside a declination range of the search area.

7. The process of claim 2, further comprising, prior to performing the second determining step, a creating step for creating a zone table comprising entries specifying an identity, ra value, dec value and zone number of each object or point in the database, wherein the zone table is used to obtain an object'"'"'s or point'"'"'s identity, ra value, dec value and zone number, rather than obtaining these items from the database.

8. The process of claim 7, wherein the creating step comprises an establishing step for establishing primary keys for the identity, ra value and zone number entries to facilitate fast searches.

9. The process of claim 7, further comprising:

a first adding step for adding objects having ra values with in a prescribed range ending with 360°

into the as a left margin by subtracting 360 from the ra value and assigning the result, which will be a negative number, as the ra value for the margin object or point; and

a second adding step for adding 360 to the ra values of objects and points having ra values within a prescribed range starting with 0° and

assigning the result, which will be a number greater than or equal to 360°

as the ra value for the margin object or point.

10. A process for identifying all nearby neighbor objects and/or points of interest in relation to a user-specified base point having rectangular coordinates which reside within a search area of a prescribed radius (@r) from the base point based on information accessed from a database of geometric data which includes the location of said objects and/or points of interest defined in terms of a planar system with rectangular coordinates (x,y) from a prescribed origin of a plane representing the planar system, comprising:

a dividing step for dividing the plane into a plurality of zones each forming a lateral strip of the same prescribed zone height and assigning an integer zone number to each strip in a bottom to top sequence starting with the bottommost zone being designated as zone number 0;

an assigning step for determining what zone each object or point in the database resides and assigning that zone number to the object or point;

an identifying step for identifying the zone number of every zone intersected by the search area; and

for each object or point associated with each zone number identified as intersected by the search area,

a first adding step for adding a number equal to the absolute value of the maximum negative x coordinate value associated with the planar system of the database of geometric data to x coordinate values of any object or point taken from the database to produce a corrected x value,

a second adding step for adding a number equal to the absolute value of the maximum negative y coordinate value associated with the planar system of the database of geometric data to y coordinate values of any object or point taken from the database to produce a corrected y value,

a first determining step for determining whether the corrected x value of the object or point under consideration is between the range of @x−

a and @x+a, wherein @x is the x value of the base point corrected by adding a number equal to the absolute value of the maximum negative x coordinate value associated with the planar system of the database of geometric data if the x value of the base point is defined in terms of the planar system of the database, and wherein a is equal to @r whenever the object or point under consideration is in the same zone as the base point and to one half the width of the widest portion of the search area that intersects the zone containing the object or point under consideration whenever that object or point is not in the same zone as the base point,

whenever it is determined that the corrected x value of the object or point under consideration is between the range of @x−

a and @x+a, a first designating step for designating said object or point as a nearby neighbor candidate,

a second determining step for determining if the candidate object or point is in the search area by computing the actual distance between the base point and the candidate object or point and ascertaining if said actual distance is equal to or less than @r, and

whenever it is ascertained that said actual distance is equal to or less than @r, a second designating step for designating the candidate object or point as a nearby neighbor of the base point.