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

• US 6,993,538 B2
• Filed: 01/28/2003
• Issued: 01/31/2006
• Est. Priority Date: 01/28/2003
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Microsoft Corporation
• Inventors: Gray, James N.
• Primary Examiner(s): Alam, Shahid
• Application Number:
  US10/354,200
• Publication Number:
  US 20040148277A1
• Time in Patent Office: 1,099 Days
• Field of Search: 707/3, 707/4, 707/10, 707/104.1, 701/201, 701/202, 701/206, 701/212, 701/214, 340/988, 340/990, 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 the following process actions:

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;

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

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

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

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 direction 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 specific range, designating said object or point as a nearby neighbor candidate,

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 difining the extent of the search area in either direction along the width of the strip, designating the candidate object or point as a nearby neighbor of the base point.

2. The process of claim 1, wherein the location of each of said objects and/or points of interest included in the database of geometric data is defined in terms of a 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, and wherein the user-specified base point is defined in terms of spherical coordinates (“

@ra”

, “

@dec”

) and resides within the search area defined by a prescribed radius (“

@r) from the base point, and wherein the process action of dividing the geographic system defined by said geometric data into a plurality of zones comprises an action of dividing said sphere into declination strips, and wherein the process action of assigning an integer zone number to each strip comprises assigning numbers in a bottom to top sequence starting with the south pole of the sphere being designated as zone number 0.

3. The process of claim 2, wherein the process action of 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, comprises an action of determining whether the ra value representing said first coordinate of the object or point under consideration is between the range of @ra−

@r′ and

@ra+@r′

, wherein @ra represents the first coordinate of the base point and @r′

is said distance defining the extent of the search area in either direction along the width of the strip which is equal to @r corrected for right ascension compression corresponding to the dec value of the currently selected object or point.

4. The process of claim 1, wherein the location of each of said objects and/or points of interest included in the database of geometric data is defined in terms of a planar system with planar coordinates comprising the rectangular coordinates (x, y) of the object or point from a prescribed origin of the planar system, and wherein the user-specified base point is defined in terms of rectangular coordinates, and wherein the process action of dividing the geographic system defined by said geometric data into a plurality of zones comprises an action of dividing a plane into lateral strips, and wherein the process action of assigning an integer zone number to each strip comprises assigning numbers in a bottom to top sequence starting with the bottommost part of the plane being designated as zone number 0.

5. The process of claim 4, further comprising the process actions of:

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 and to the x coordinate value of the specified base point if defined in terms of the planar system of the database to produce a corrected x value; and

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 and to the y coordinate value of the specified base point if defined in terms of the planar system of the database to obtain a corrected y value.

6. The process of claim 5, wherein the process action of 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, comprises an action of determining whether the corrected x value representing said first coordinate of the object or point under consideration is between the range of @x−

@r and @x+@r, wherein @x represents the corrected x value of the first coordinate of the base point and @r is said distance defining the extent of the search area in either direction along the width of the strip.

7. The process of claim 5, wherein the process action of determining what zone each object or point in the database resides, comprises the actions of:

dividing the corrected y value of the object or point under consideration by the prescribed zone height; and

rounding down to the nearest integer value.

8. The process of claim 5, wherein the process action of identifying the zone number of every zone intersected by the search area, comprises the actions of:

computing the zone number of the topmost zone intersected by the search area by,

adding @y to @r, wherein @y represents the corrected y value of the base point,

dividing the resulting sum by the prescribed zone height, and

rounding up to the nearest integer value;

computing the zone number of the bottommost zone intersected by the search area by,

subtracting @r from @y,

dividing the resulting difference by the prescribed zone height, and

rounding down to the nearest integer value; and

deeming the zone numbers of the topmost and bottommost zones intersected by the search area, and the zone number of every zone between said topmost and bottommost zones, as the zone numbers of the zones intersected by the search area.

9. The process of claim 5, further comprising, prior to performing the process action of designating the object or point under consideration as a nearby neighbor candidate whenever it is determined that the corrected x value of the object or point under consideration is between the range of @x−

@r and @x+@r, performing an action of eliminating the object or point as a nearby neighbor candidate if its corrected y value is outside the search area, wherein @x represents the corrected x value of the base point.

10. The process of claim 9, wherein the process action of eliminating the object or point as a nearby neighbor candidate if its corrected y value is outside the search area, comprises the actions of:

determining if the object or point has a corrected y value that falls between @y−

@r and @y+@r, wherein @y represents the corrected y value of the base point; and

eliminating the object or point as a nearby neighbor candidate if its corrected y value falls outside the search area as defined by @y−

@r and @y+@r.

11. The process of claim 1, wherein the process actions involving processing of each object or point in the database, or each object or point associated with each zone number identified as intersected by the search area, comprises performing said actions in parallel on a prescribed number of objects and/or points, wherein each object or point processed in parallel is processed by a different processor.

12. The process of claim 1, wherein the process actions are implemented as set-oriented operators which facilitate straightforward and automatic execution of process actions in parallel using multiple processors, said operators comprising SQL relational operators.

13. A system 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(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 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 general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

divide 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;

determine what zone each object or point in the database resides and assigning that zone number to the object or point;

identify 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,

determine 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′

, designate said object or point as a nearby neighbor candidate,

determine 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, designate the candidate object or point as a nearby neighbor of the base point.

14. The system of claim 13, wherein the program module for determining what zone each object or point in the database resides, comprises the sub-modules 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

rounding down to the nearest integer value.

15. The system of claim 13, wherein the program module for identifying the zone number of every zone intersected by the search area, comprises sub-modules 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;

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

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.

16. The system of claim 13, wherein the program module for determining whether the ra value of the object or point under consideration is between the range of @ra−

@r′ and

@ra+@r′

, comprises a sub-module for computing @r′

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

)), where ε

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

17. The system of claim 13, further comprising, prior to executing the program module for designating the object or point under consideration as a nearby neighbor candidate 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′

, executing a program module for eliminating the object or point as a nearby neighbor candidate if its dec value is outside a declination range of the search area.

18. The system of claim 17, wherein the program module for eliminating the object or point as a nearby neighbor candidate if its dec value is outside a declination range of the search area, comprises sub-modules for:

determining if the object or point has a dec value that falls between @dec−

@r and @dec+@r; and

eliminating the object or point as a nearby neighbor candidate if its dec value falls outside the declination range of the search area as defined by @dec−

@r and @dec+@r.

19. The system of claim 13, wherein the location of the base point is known in terms of the J2000 coordinate system as @cx, @cy, @cz, and the location of each object or point in the database is known in terms of the J2000 coordinate system as cx, cy, cz, and wherein the program module for computing the actual distance between the base point and the candidate object or point, comprises a sub-module for computing the distance θ

in degrees between the base point and the candidate object or point under consideration as $2\times <br><br>\arcsin <br><br>\sqrt{\frac{{\left(\mathrm{cx}-@\mathrm{cx}\right)}^2+{\left(\mathrm{cy}-@\mathrm{cy}\right)}^2+{\left(\mathrm{cz}-@\mathrm{cz}\right)}^2}{2}}.$

20. The system of claim 13, further comprising, prior to executing the program module for determining whether the ra value of the object or point under consideration is between the range of @ra−

@r′ and

@ra+@r′

, executing a program module 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.

21. The system of claim 20, wherein the program module for creating a zone table, further comprises a sub-module for establishing primary keys for the identity, ra value and zone number entries to facilitate fast searches.

22. The system of claim 20, further comprising program modules 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

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.

23. The system of claim 22, wherein the prescribed margin range employed for each object or point considered is set equal to the prescribed radius of the search area corrected for the right ascension compression by dividing the radius by cos(abs(dec′

))+ε

, wherein dec′

is the dec value of the object or point under consideration.

24. A computer-readable medium having computer-executable instructions 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, said computer-executable instructions comprising;

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;

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

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,

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

x and @ra+x, wherein x is equal to @r corrected for right ascension compression corresponding to the dec value of the object or point under consideration whenever that object or point is in the same zone as the base point, and wherein x is equal 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 ra value of the object or point under consideration is between the range of @ra−

x and @ra+x, designating said object or point as a nearby neighbor candidate,

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, designating the candidate object or point as a nearby neighbor of the base point.

25. A computer-readable medium having computer-executable instructions 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, said computer-executable instructions comprising:

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;

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

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,

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,

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,

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, designating said object or point as a nearby neighbor candidate,

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, designating the candidate object or point as a nearby neighbor of the base point.

26. A computer-implemented process for identifying nearby neighbor objects and/or points of interest for each object or point of interest located in a plurality of zones of a sphere from 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 spherical system with spherical coordinates comprising the declination (dec) and right ascension (ra) of the object or point from the center of said sphere which represents the spherical system, said process comprising using a computer to perform the following process actions:

dividing the sphere into said plurality of zones each forming a consecutive 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 southernmost zone being designated as zone number 0;

determining what objects and/or points in the database reside in said plurality of zones and assigning that zone number to the object or point; and

for each of said plurality of zones,

(i) designating the zone under consideration as the base zone,

(ii) selecting a previously unselected object or point residing in the currently designated base zone,

(iii) identifying those zones of said plurality of zones that are located to the north of the currently designated base zone and which are at least partially traversed by a line (@r) of a prescribed length extending northward from the northern border of the currently designated base zone, if any, and identify those zones of said plurality of zones that are located to the south of the currently designated base zone and which are at least partially traversed by @r extending southward from the southern border of the currently designated base zone, if any,

(iv) designating the identified northern and southern zones, as well as the currently designated base zone as neighbor zones;

(v) selecting a previously unselected neighbor zone,

(vi) selecting a previously unselected object or point residing within the currently selected neighbor zone,

(vii) determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′ and

the ra value of the selected base zone object or point+@r′

, where @r′

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

(viii) whenever it is determined that the ra value of the selected neighbor zone object or point falls within said ra range, designating the selected neighbor zone object or point as a nearby neighbor candidate,

(ix) determining if the candidate object or point is in a circular area centered on the selected base zone object or point and having a radius equal to @r by computing the actual distance between the selected base zone object or point and the candidate object or point, and ascertaining if said actual distance is equal to or less than @r,

(x) whenever it is ascertained that said actual distance is equal to or less than @r, designating the candidate object or point as a nearby neighbor of the selected base zone object or point,

(xi) repeating actions (vi) through (x) until no previously unselected objects and/or points residing within the currently selected neighbor zone remain,

(xii) repeating actions (v) through(xi) until no previously unselected neighbor zones remain, and

(xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain.

27. The process of claim 26, wherein @r is equal to said prescribed zone height, and wherein the process action of identifying those zones of said plurality of zones that are located to the north and south of the currently designated base zone comprises identifying just the zone immediately to the north and the zone immediately to the south of the currently designated base zone.

28. The process of claim 26, further comprising, prior to performing the process action of designating the selected neighbor zone object or point as a nearby neighbor candidate whenever it is determined that the ra value of the selected neighbor zone object or point falls within the ra range, performing an action of eliminating the selected neighbor zone object or point as a nearby neighbor candidate if its dec value is outside a dec range.

29. The process of claim 28, wherein the process action of eliminating the selected neighbor zone object or point as a nearby neighbor candidate if its dec value is outside the dec range, comprises the actions of:

determining if the selected neighbor zone object or point has a dec value that falls within the dec range defined by the dec value of the selected base zone object or point minus @r and the dec value of the selected base zone object plus @r; and

eliminating the selected neighbor zone object or point as a nearby neighbor candidate if its dec value falls outside the dec range.

30. The process of claim 26, wherein the location of each object or point in the database is known in terms of the J2000 coordinate system as cx, cy, cz, and wherein the process action of computing the actual distance between the selected base zone object or point and a candidate object or point, comprises an action of computing the distance θ

in degrees between the selected base zone object or point and the candidate object or point under consideration as $\mathrm{ <br><br>}<br><br>\mathrm{\theta <br><br>}=2\times <br><br>\arcsin <br><br>\sqrt{\frac{\begin{array}{c}{\left(\mathrm{o1}.\mathrm{cx}-\mathrm{o2}.\mathrm{cx}\right)}^2+{\left(\mathrm{o1}.\mathrm{cy}-\mathrm{o2}.\mathrm{cy}\right)}^2+\\ {\left(\mathrm{o1}.\mathrm{cz}-\mathrm{o2}.\mathrm{cz}\right)}^2\end{array}}{2}},$

where (o1.cx, o1.cy, o1.cz) represents the coordinates of the selected base zone object or point and (o2.cx, o2.cy, o2.cz) represents the coordinates of the candidate object or point under consideration.

31. The process of claim 26, further comprising, prior to performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′

and the ra value of the selected base zone object or point +@r′

, a process action of 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.

32. The process of claim 31, wherein the process action of creating a zone table, further comprises an action of establishing primary keys for the identity, ra value and zone number entries to facilitate fast searches.

33. The process of claim 31, further comprising the process actions of:

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

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.

34. The process of claim 33, wherein the prescribed margin range employed for each object or point considered is set equal to the prescribed radius of the search area corrected for the right ascension compression by dividing the radius by cos(abs(dec′

))+ε

, wherein dec′

is the dec value of the object or point under consideration.

35. The process of claim 26, further comprising, prior to performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′

and the ra value of the selected base zone object or point+@r′

, the process actions of;

determining whether the value of the currently selected base zone object or point is greater than or equal to 0° and

less than 360°

, or the value of the currently selected neighbor zone object or point is greater than or equal to 0° and

less than 360°

, and

performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′ and

the ra value of the selected base zone object or point+@r′

, only when it is determined that the value of the currently selected base zone object or point is greater than or equal to 0° and

less than 360°

, or the value of the currently selected neighbor zone object or point is greater than or equal to 0° and

less than 360°

.

36. The process of claim 26, further comprising, prior to performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′

and the ra value of the selected base zone object or point+@r′

, the process actions of;

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′ and

the ra value of the selected base zone object or point +@r′

; and

subsequent to performing the process action of designating the candidate object or point as a nearby neighbor of the selected base zone object or point, designating the selected base zone object or point as a nearby neighbor of the candidate object or point.

37. The process of claim 36, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

38. The process of claim 26, further comprising a process action of creating a nearby neighbors table comprising, for each base zone object or point selected, entries specifying an identity of the base zone object or point and the identity of each object or point designated to be a nearby neighbor of the base zone or point.

39. The process of claim 38, wherein the process action of creating the nearby neighbors table, further comprises including entries comprising the ra value, dec value and zone number of each object or point entered into the table.

40. The process of claim 39, wherein the process action of creating the nearby neighbors table, further comprises an action of establishing primary keys for the identity, ra value and zone number entries of each object or point entered into the table to facilitate fast searches.

41. The process of claim 38, further comprising, prior to performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′

and the ra value of the selected base zone object or point +@r′

, the process actions of;

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the ra value of the selected neighbor zone object or point falls within a ra range between the ra value of the selected base zone object or point minus @r′ and

the ra value of the selected base zone object or point +@r′

; and

subsequent to performing process action (xiii), for every object or point designated as a nearby neighbor of another object or point, designating said other object or point as a nearby neighbor of the object or point under consideration.

42. The process of claim 41, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

43. The process of claim 38, wherein the process action of eliminating the selected neighbor zone object or point as a candidate object or point if its corrected y value is outside a height range, comprises the actions of:

determining if the selected neighbor zone object or point has a corrected y value that falls between @y−

@r and @y+@r, wherein @y represents the corrected y value of the currently selected base zone object or point; and

eliminating the object or point as a nearby neighbor candidate if its corrected y value falls outside the height range defined by @y−

@r and @y+@r.

44. A computer-implemented process for identifying nearby neighbor objects and/or points of interest for each object or point of interest located in a plurality of zones of a plane from 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) of the object or point from a prescribed origin of said plane which represents the planar system, said process comprising using a computer to perform the following process actions:

dividing the plane into said plurality of zones each forming a consecutive 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;

determining what objects and/or points in the database reside in said plurality of zones and assigning that zone number to the object or point; and

for each of said plurality of zones,

(i) designating the zone under consideration as the base zone,

(ii) selecting a previously unselected object or point residing in the currently designated base zone,

(iii) identifying those zones of said plurality of zones that are located above of the currently designated base zone and which are at least partially traversed by a line (@r) of a prescribed length extending upward from the top border of the currently designated base zone, if any, and identify those zones of said plurality of zones that are located below of the currently designated base zone and which are at least partially traversed by @r extending downward from the bottom border of the currently designated base zone, if any,

(iv) designating the identified zones above and below the currently designated base zone, as well as the currently designated base zone itself, as neighbor zones,

(v) selecting a previously unselected neighbor zone,

(vi) selecting a previously unselected object or point residing within the currently selected neighbor zone,

(vii) determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r,

(viii) whenever it is determined that the x value of the selected neighbor zone object or point falls within said lateral range, designating the selected neighbor zone object or point as a nearby neighbor candidate,

(ix) determining if the candidate object or point is in a region centered on the selected base zone object or point by computing the actual distance between the selected base zone object or point and the candidate object or point,

(x) whenever it is ascertained that said actual distance is in the region centered on the selected base zone object or point, designating the candidate object or point as a nearby neighbor of the selected base zone object or point,

(xi) repeating actions (vi) through (x) until no previously unselected objects and/or points residing within the currently selected neighbor zone remain,

(xii) repeating actions (v) through(xi) until no previously unselected neighbor zones remain, and

(xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain.

45. The process of claim 44, wherein said region centered on the selected base zone object or point is circular having a radius equal to @r.

46. The process of claim 44, wherein said region centered on the selected base zone object or point is square having a width equal to 2@r.

47. The process of claim 44, wherein the origin of the planar system is not located at the lower left hand corner of said plane, and wherein the process further comprising the process actions of:

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 obtain a corrected x value; and

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 obtain a corrected y value; and

wherein

the process action of determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r, comprises using the corrected x values in place of the x values taken from the database.

48. The process of claim 47, wherein the process action of determining what objects and/or points in the database reside in said plurality of zones, comprises the actions of:

dividing the corrected y value of the object or point under consideration by the prescribed zone height;

rounding down to the nearest integer value to obtain the zone number of the zone in which the object or point resides; and

determining if the zone number of the zone in which the object or point resides corresponds to one of said plurality of zones.

49. The process of claim 47, further comprising, prior to performing the process action of designating the selected neighbor zone object or point as a candidate object or point, performing an action of eliminating the selected neighbor zone object or point as a candidate object or point if its corrected y value is outside a height range.

50. The process of claim 44, further comprising, prior to performing the action of determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r, the process actions of:

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r; and

subsequent to performing the process action of designating the candidate object or point as a nearby neighbor of the selected base zone object or point, designating the selected base zone object or point as a nearby neighbor of the candidate object or point.

51. The process of claim 50, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

52. The process of claim 44, further comprising a process action of creating a nearby neighbors table comprising, for each base zone object or point selected, entries specifying an identity of the base zone object or point and the identity of each object or point designated to be a nearby neighbor of the base zone or point.

53. The process of claim 52, further comprising, prior to performing the action of determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r, the process actions of:

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the x value of the selected neighbor zone object or point falls within a lateral range between the x value of the selected base zone object or point minus @r and the x value of the selected base zone object or point +@r; and

subsequent to performing process action (xiii), for every object or point designated as a nearby neighbor of another object or point, designating said other object or point as a nearby neighbor of the object or point under consideration.

54. The process of claim 53, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

55. A computer-implemented process for identifying nearby neighbor objects and/or points for objects and/or points in a database which includes a set of parameters for each object and point, said process comprising the following process actions:

identifying a range of a pre-selected one of said set of parameters into which that parameter of each of the objects and/or points in the database falls and dividing the database into a plurality of zones each forming an equal sized sub-range of the identified range;

assigning an integer zone number to each sub-range in a bottom to top sequence starting with the bottommost zone, which is the sub-range having the smallest values for the pre-selected parameter, being designated as zone number 0;

determining what zone each object or point in the database is associated with and assigning the zone number of that zone to the object or point;

for each of said plurality of zones,

(i) designating the zone under consideration as the base zone,

(ii) selecting a previously unselected object or point associated with the currently designated base zone,

(iii) identifying those zones of said plurality of zones that correspond to a sub-range having values of the pre-selected parameter that are larger than those of the currently designated base zone and which are equal to or less than a prescribed upper limit of said pre-selected parameter, and identifying those zones of said plurality of zones that correspond to a sub-range having values of the pre-selected parameter that are smaller than those of the currently designated base zone and which are equal to or greater than a prescribed lower limit of said pre-selected parameter,

(iv) designating the identified zones above and below the currently designated base zone, as well as the currently designated base zone itself, as neighbor zones,

(v) selecting a previously unselected neighbor zone,

(vi) selecting a previously unselected object or point associated with the currently selected neighbor zone,

(vii) determining whether a second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value,

(viii) whenever it is determined that the second parameter of the selected neighbor zone object or point is within the specified second parameter range, designating said object or point as a nearby neighbor candidate,

(ix) determining if the candidate object or point within a prescribed degree of similarity between it and the selected base zone object or point by computing the actual divergence between them in regard to their first and second parameters,

(x) whenever it is ascertained that said actual divergence is within the prescribed degree of similarity, designating the candidate object or point as a nearby neighbor of the selected base zone object or point,

(xi) repeating actions (vi) through (x) until no previously unselected objects and/or points associated with the currently selected neighbor zone remain,

(xii) repeating actions (v) through (xi) until no previously unselected neighbor zones remain, and

(xiii) repeating actions (ii) through (xii) until no previously unselected objects and/or points residing within the currently selected base zone remain.

56. The process of claim 55, further comprising, prior to performing the process action of designating the selected neighbor zone object or point as a candidate object or point, performing an action of eliminating the selected neighbor zone object or point as a candidate if its said first parameter falls outside a range defined by the first parameter of the selected base zone object or point less a prescribed value and the first parameter of the selected base zone object or point plus the prescribed value.

57. The process of claim 55, further comprising, prior to performing the action of determining whether the second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value, the process actions of:

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value; and

subsequent to performing the process action of designating the candidate object or point as a nearby neighbor of the selected base zone object or point, designating the selected base zone object or point as a nearby neighbor of the candidate object or point.

58. The process of claim 57, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

59. The process of claim 55, further comprising a process action of creating a nearby neighbors table comprising, for each base zone object or point selected, entries specifying an identity of the base zone object or point and the identity of each object or point designated to be a nearby neighbor of the base zone object or point.

60. The process of claim 59, further comprising, prior to performing the action of determining whether the second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value, the process actions of:

determining whether an identity number assigned to the selected base zone object or point has a prescribed hierarchical relationship to an identity number assigned to the selected neighbor zone object or point;

only when the identity number assigned to the selected base zone object or point has the prescribed hierarchical relationship to the identity number assigned to the selected neighbor zone object or point, performing the action of determining whether the second one of said set of parameters of the objects and/or points of the selected neighbor zone falls within a range defined by the second parameter of the selected base zone object or point less a prescribed value and the second parameter of the selected base zone object or point plus the prescribed value; and

subsequent to performing process action (xiii), for every object or point designated as a nearby neighbor of another object or point, designating said other object or point as a nearby neighbor of the object or point under consideration.

61. The process of claim 60, wherein the prescribed hierarchical relationship between the identity number assigned to the selected base zone object or point and the identity number assigned to the selected neighbor zone object or point, is one of (i) that the identity number assigned to the selected base zone object or point is less than the identity number assigned to the selected neighbor zone object or point, and (ii) that the identity number assigned to the selected base zone object or point is greater than the identity number assigned to the selected neighbor zone object or point.

62. The process of claim 55, wherein the process actions involving processing of each object or point in the database, or performed subsequent to selecting a previously unselected object or point associated with the currently selected neighbor zone, comprises performing said actions in parallel on a prescribed number of objects and/or points, wherein each object or point processed in parallel is processed by a different processor.

63. The process of claim 55, wherein the process actions are implemented as set-oriented operators which facilitate straightforward and automatic execution of process actions in parallel using multiple processors, said operators comprising SQL relational operators.

64. The process of claim 55, wherein the database comprises geometric data is defined in terms of a spherical system in which said set of parameters comprises spherical coordinates comprising the declination (dec) and right ascension (ra) as the first and second parameters of the object or point, respectively.

65. The process of claim 55, wherein the database comprises geometric data is defined in terms of a planar system in which said set of parameters comprises rectangular coordinates comprising a lateral coordinate and a height coordinate as the first and second parameters of the object or point, respectively.

66. The process of claim 55, wherein the database comprises geometric data is defined in terms of a cylindrical system in which said set of parameters comprises cylindrical coordinates comprising the first and second parameters of the object or point, respectively.

67. The process of claim 55, wherein the database comprises geometric data is defined in terms of a conical system in which said set of parameters comprises conical coordinates comprising the first and second parameters of the object or point, respectively.

68. The process of claim 55, wherein the database comprises geometric data is defined in terms of a hyperbolic system in which said set of parameters comprises hyperbolic coordinates comprising the first and second parameters of the object or point, respectively.

69. The process of claim 55, wherein the database comprises non-spatial object or point data defined in terms of at least two parameters comprising the first and second parameters of the object or point, respectively.

70. A computer-implemented process for identifying all nearby neighbor objects and/or points in relation to a user-specified base point based on information accessed from a database which includes a set of parameters for each object and point, said process comprising the following process actions:

identifying a range of a first pre-selected one of said set of parameters into which that parameter of each of the objects and/or points in the database falls and dividing the database into a plurality of zones each forming an equal sized sub-range of the identified range;

assigning an integer zone number to each sub-range in a bottom to top sequence starting with the bottommost zone, which is the sub-range having the smallest values for the pre-selected parameter, being designated as zone number 0;

determining what zone each object or point in the database is associated with and assigning the zone number of that zone to the object or point;

identifying the zone number of every zone intersected by a search area defined by at least a prescribed search range of said first pre-selected parameter centered on the value of the first parameter of the base point and a prescribed search range of a second pre-selected one of said set of parameters centered on the value of the second parameter of the base point; and

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

determining whether the second parameter of the object or point under consideration falls within a range defined by the second parameter of the base point less a prescribed value and the second parameter of the base point plus the prescribed value,

whenever it is determined that second parameter of the object or point under consideration falls within the specified range, designating said object or point as a nearby neighbor candidate,

determining if the candidate object or point is in the search area by computing the actual divergence between the base point and the candidate object or point in regard to their first and second parameters and ascertaining if said actual divergence places that the candidate object or point within the bounds of the search area, and

whenever it is ascertained that said actual divergence places that the candidate object or point within the bounds of the search area, designating the candidate object or point as a nearby neighbor of the base point.

71. The process of claim 70, further comprising, prior to performing the process action of designating an object or point as a nearby neighbor candidate, performing an action of eliminating the object or point as a candidate if its said first parameter falls outside a range defined by the first parameter of the selected base point less a prescribed value and the first parameter of the selected base point plus the prescribed value.

72. The process of claim 70, wherein the process actions involving processing of each object or point in the database, or each object or point associated with each zone number identified as intersected by the search area, comprises performing said actions in parallel on a prescribed number of objects and/or points, wherein each object or point processed in parallel is processed by a different processor.

73. The process of claim 70, wherein the process actions are implemented as set-oriented operators which facilitate straightforward and automatic execution of process actions in parallel using multiple processors, said operators comprising SQL relational operators.

74. The process of claim 70, wherein the database comprises geometric data is defined in terms of a spherical system in which said set of parameters comprises spherical coordinates comprising the declination (dec) and right ascension (ra) as the first and second parameters of the object or point, respectively.

75. The process of claim 70, wherein the database comprises geometric data is defined in terms of a planar system in which said set of parameters comprises rectangular coordinates comprising a lateral coordinate and a height coordinate as the first and second parameters of the object or point, respectively.

76. The process of claim 70, wherein the database comprises geometric data is defined in terms of a cylindrical system in which said set of parameters comprises cylindrical coordinates comprising the first and second parameters of the object or point, respectively.

77. The process of claim 70, wherein the database comprises geometric data is defined in terms of a conical system in which said set of parameters comprises conical coordinates comprising the first and second parameters of the object or point, respectively.

78. The process of claim 70, wherein the database comprises geometric data is defined in terms of a hyperbolic system in which said set of parameters comprises hyperbolic coordinates comprising the first and second parameters of the object or point, respectively.

79. The process of claim 70, wherein the database comprises non-spatial object or point data defined in terms of at least two parameters comprising the first and second parameters of the object or point, respectively.