System and method for proximity searching position information using a proximity parameter

• US 7,783,621 B2
• Filed: 02/17/2006
• Issued: 08/24/2010
• Est. Priority Date: 04/25/2000
• Status: Expired due to Fees

• Current Assignee: Buffalo Patents, LLC
• Original Assignee: Archeron Ltd LLC (Intellectual Ventures LLC)
• Inventors: Cooper, Jeremy S.
• Primary Examiner(s): To; Baoquoc N
• Application Number:
  US11/356,442
• Publication Number:
  US 20070016562A1
• Time in Patent Office: 1,649 Days
• Field of Search: 707/3, 707/10, 707/6, 701/1, 701/2, 701/3
• US Class Current: 707/707
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A computer implemented proximity searcher searches position field information (representing geographical positions) stored in database records, to identify database positions falling within a predetermined search range of a position of interest. The proximity searcher avoids time consuming conventional techniques such as great circle calculations to thereby reduce the computational burden associated with proximity searching, thus achieving time efficient proximity searches to identify candidate geographical positions that are near the position of interest. The proximity searcher identifies the candidate geographical positions within a search range, specified as a proximity parameter, of the position of interest. The proximity parameter and the position field information can have incompatible formats. In one configuration, the proximity searcher resides on a server coupled to a network and responds to user queries provided by, for example, client computers also coupled to the network.

Claims

1. A method for performing a proximity search, comprising:

receiving, at a computing device, data representing a geographical position and data representing a distance;

processing the data using the computing device, including;

determining a first latitude north of the geographical position by an amount of the distance,

determining a second latitude south of the geographical position by the amount of the distance,

determining a first longitude west of the geographical position based on the amount of the distance and a mathematical function of a latitude of the geographical position, and

determining a second longitude east of the geographical position based on the amount of the distance and the mathematical function of the latitude of the geographical position;

determining at the computing device whether a place of interest is proximate to the geographical position based on a determination that a latitude of the place of interest is between the first latitude and the second latitude and a longitude of the place of interest is between the first longitude and the second longitude; and

outputting a result of the proximity determination from the computing device.

2. The method of claim 1, further comprising:

presenting, at an output device, a name of the place of interest if the latitude of the place of interest is between the first latitude and the second latitude and the longitude of the place of interest is between the first longitude and the second longitude.

3. The method of claim 2, further comprising:

presenting, at the output device, additional information associated with the place of interest.

4. The method of claim 1, further comprising:

inputting the data representing the geographical position and the data representing the distance using an input device.

5. The method of claim 1, wherein

said determining the first latitude north of the geographical position comprises determining a sum of a latitude, in radians, of the geographical position added to a first quotient, the first quotient being equal to a first product divided by a measure of a circumference of the Earth, the first product being equal to the distance multiplied by two multiplied by pi,

said determining the first latitude south of the geographical position comprises determining a difference of the first quotient subtracted from the latitude, in radians, of the geographical position,

said determining the first latitude west of the geographical position comprises determining a sum of a longitude, in radians, of the geographical position added to a second quotient, the second quotient being equal to the first product divided by a second product, the second product being equal to a measure of a radius of the Earth multiplied by two multiplied by pi multiplied by a cosine of the latitude of the geographical position, and

said determining the first latitude east of the geographical position comprises determining a difference of the second quotient subtracted from the longitude, in radians, of the geographical position.

6. The method of claim 1, wherein the mathematical function comprises a cosine function of the latitude of the geographical position.

7. The method of claim 1, wherein the mathematical function comprises a non-linear function of the latitude of the geographical position.

8. A system for performing a proximity search, comprising:

a database configured to store data representing a latitude of a place of interest and a longitude of the place of interest; and

a computing device configured to receive data representing a geographical position and data representing a distance and to automatically process the data to;

determine a first latitude north of the geographical position by an amount of the distance,

determine a second latitude south of the geographical position by the amount of the distance,

determine a first longitude west of the geographical position based on the amount of the distance and a mathematical function of a latitude of the geographical position,

determine a second longitude east of the geographical position based on the amount of the distance and the mathematical function of the latitude of the geographical position,

determine whether the place of interest is proximate to the geographical position based on a determination that the latitude of the place of interest is between the first latitude and the second latitude and the longitude of the place of interest is between the first longitude and the second longitude, and

output a result of the proximity determination.

9. The system of claim 8, further comprising:

an output device configured to present a name of the place of interest if the latitude of the place of interest is between the first latitude and the second latitude and the longitude of the place of interest is between the first longitude and the second longitude.

10. The system of claim 9, wherein the output device is further configured to present additional information associated with the place of interest.

11. The system of claim 8, further comprising:

an input device configured to input the data representing the geographical position and the data representing the distance.

12. The system of claim 8, wherein the computing device is configured to determine a first sum, a first difference, a second sum, and a second difference, the first sum is equal to a latitude, in radians, of the geographical position added to a first quotient, the first quotient is equal to a first product divided by a measure of a circumference of the Earth, the first product is equal to the distance multiplied by two multiplied by pi, the first difference is equal to the first quotient subtracted from the latitude, in radians, of the geographical position, the second sum is equal to a longitude, in radians, of the geographical position added to a second quotient, the second quotient is equal to the first product divided by a second product, the second product is equal to a measure of a radius of the Earth multiplied by two multiplied by pi multiplied by a cosine of the latitude of the geographical position, and the second difference is equal to the second quotient subtracted from the longitude, in radians, of the geographical position.

13. The system of claim 8, wherein the mathematical function comprises a cosine function of the latitude of the geographical position.

14. The system of claim 8, wherein the mathematical function comprises a non-linear function of the latitude of the geographical position.

15. A computer-readable medium having stored thereon computer-executable instructions that, if executed by a computing device, cause the computing device to perform a method for performing a proximity search, the method comprising:

receiving data representing a geographical position and data representing a distance;

processing the data, including;

determining a first latitude north of the geographical position by an amount of the distance,

determining a second latitude south of the geographical position by the amount of the distance,

determining a first longitude west of the geographical position based on the amount of the distance and a mathematical function of a latitude of the geographical position,

determining a second longitude east of the geographical position based on the amount of the distance and the mathematical function of the latitude of the geographical position;

determining whether a place of interest is proximate to the geographical position based on a determination that a latitude of the place of interest is between the first latitude and the second latitude and a longitude of the place of interest is between the first longitude and the second longitude; and

outputting a result of the proximity determination.

16. The computer-readable medium of claim 15, wherein said processing the data comprises:

determining a sum of a latitude, in radians, of the geographical position added to a first quotient, the first quotient being equal to a first product divided by a measure of a circumference of the Earth, the first product being equal to the distance multiplied by two multiplied by pi;

determining a difference of the first quotient subtracted from the latitude, in radians, of the geographical position;

determining a sum of a longitude, in radians, of the geographical position added to a second quotient, the second quotient being equal to the first product divided by a second product, the second product being equal to a measure of a radius of the Earth multiplied by two multiplied by pi multiplied by a cosine of the latitude of the geographical position; and

determining a difference of the second quotient subtracted from the longitude, in radians, of the geographical position.

17. The computer-readable medium of claim 15, wherein the mathematical function comprises a cosine function of the latitude of the geographical position.

18. The computer-readable medium of claim 15, wherein the mathematical function comprises a non-linear function of the latitude of the geographical position.

19. A method for performing a proximity search, comprising:

receiving, at a computing device, data representing a geographical position that defines a center of a circle and data representing a distance that defines a radius of the circle;

determining, by the computing device, a polygon within which the circle is inscribed, the polygon being defined by respective sets of latitudes and longitudes corresponding to vertices of the polygon;

determining, by the computing device, whether a place of interest is proximate to the geographical position based on a determination that a latitude and a longitude of a geographical position of the place of interest is within the polygon; and

outputting a result of the proximity determination from the computing device.

20. The method of claim 19, wherein the polygon is a rectangle having a first side with a first length and a second side with a second length, wherein the first length is different from the second length.

21. The method of claim 19, wherein the polygon is a parallelogram having an interior angle that is less than ninety degrees.

22. The method of claim 19, wherein the polygon is a rhombus having an interior angle that is less than ninety degrees.

23. A system for performing a proximity search, comprising:

a database configured to store data representing a geographical position of a place of interest; and

a computing device configured to receive data representing a geographical position that defines a center of a circle and data representing a distance that defines a radius of the circle, to determine a polygon within which the circle is inscribed, wherein the polygon is defined by respective sets of latitudes and longitudes corresponding to vertices of the polygon, to determine whether the place of interest is proximate to the geographical position that defines the center of the circle based on a determination that a latitude and a longitude of the geographical position of the place of interest is within the polygon, and to output a result of the proximity determination.

24. A computer-readable medium having stored thereon computer-executable instructions that, if executed by a computing device, cause the computing device to perform a method for performing a proximity search, the method comprising:

receiving data representing a geographical position that defines a center of a circle and data representing a distance that defines a radius of the circle;

determining a polygon within which the circle is inscribed, the polygon being defined by respective sets of latitudes and longitudes corresponding to vertices of the polygon;

determining whether a place of interest is proximate the geographical position based on a determination that a latitude and longitude of a geographical position of the place of interest are within the polygon; and

outputting a result of the proximity determination.

25. A system for performing a proximity search, comprising:

a database including a plurality of records storing position information, wherein the position information in each of the plurality of records includes a latitude and a longitude associated with a position; and

a proximity searcher configured to;

receive a search radius defining a circular search area centered around a predetermined position,

map the circular search area to a smallest square search area into which the circular search area can fit based on the search radius, the square search area being defined by of a set of latitudes and longitudes of vertices of the square search area, wherein the smallest square search area covers a latitude range and a longitude range corresponding respectively to a height and a width of the smallest square search area, the height and the width corresponding to a distance equal to at least twice the search radius, and

compare the set of latitudes and longitudes to the position information in the plurality of records stored in the database to determine which of the plurality of records include the position information within the smallest square search area.

26. A computer-readable medium having stored thereon computer-executable instructions that, if executed by a computing device, cause the computing device to perform a method comprising:

receiving a search radius defining a circular search area centered around a predetermined position;

mapping the circular search area to a smallest square search area into which the circular search area can fit based on the search radius, the square search area being defined by a set of latitudes and longitudes of vertices of the square search area, wherein the smallest square search area covers a latitude range and a longitude range corresponding respectively to a height and a width of the smallest square search area, the height and the width corresponding to a distance equal to at least twice the search radius; and

comparing the set of latitudes and longitudes to position information in a plurality of records stored in a database to determine which of the plurality of records include the position information within the smallest square search area, wherein the position information in the plurality of records includes a latitude and a longitude associated with a position.

27. A system for performing a proximity search, comprising:

a computing device including memory and at least one processor;

means for receiving data representing a geographical position and data representing a distance;

means for determining a first latitude north of the geographical position by an amount of the distance, for determining a second latitude south of the geographical position by an amount of the distance, for determining a first longitude west of the geographical position based on the amount of the distance and a mathematical function of a latitude of the geographical position, and for determining a second longitude east of the geographical position based on the amount of the distance and the mathematical function of the latitude of the geographical position; and

means for determining whether a place of interest is proximate to the geographical position based on a determination that a latitude of the place of interest is between the first latitude and the second latitude and a longitude of the place of interest is between the first longitude and the second longitude.

28. A system for performing a proximity search, comprising:

a computing device including memory and at least one processor;

means for receiving data representing a geographical position that defines a center of a circle and data representing a distance that defines a radius of the circle;

means for determining a polygon within which the circle is inscribed, the polygon being defined by respective sets of latitudes and longitudes corresponding to vertices of the polygon; and

means for determining whether a place of interest is proximate to the geographical position that defines the center of the circle based on a determination that a latitude and longitude of a geographical position of the place of interest are within the polygon.