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

• US 7,007,010 B2
• Filed: 04/25/2001
• Issued: 02/28/2006
• Est. Priority Date: 04/25/2000
• Status: Expired due to Term

• Current Assignee: Buffalo Patents, LLC
• Original Assignee: Icplanet Corporation
• Inventors: Cooper, Jeremy S.
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): To, Baoquoc N.
• Application Number:
  US09/840,922
• Publication Number:
  US 20020059226A1
• Time in Patent Office: 1,770 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 701/201
• US Class Current: 707/758
• 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 of performing a proximity search, comprising the steps of:

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

(b) calculating a set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit based on the search radius, 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

(c) comparing the set of latitudes and longitudes to position information in a plurality of records stored in a database to determine which of the position information in the plurality of records is 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.

2. The method of claim 1, further comprising the step of:

(d) determining which of the position information in the plurality of records is within the circular search area based on step (c).

3. The method of claim 1, wherein step (b) further comprises calculating respective latitudes and longitudes of at least first, second, and third corners of the smallest square search area, wherein the latitude range extends between the latitudes of the first and the second corners of the smallest square search area and the longitude range extends between the longitudes of the second and the third corners of the smallest square search area.

4. The method of claim 3, wherein step (b) further comprises calculating the latitudes and the longitudes of at least the first, the second, and the third corners of the smallest square search area, wherein the first and the second corners are at a same longitude but different latitudes and the second and the third corners are at a same latitude but different longitudes.

5. The method of claim 1, wherein step (b) further comprises the steps of:

calculating an angular width of the smallest square search area, the angular width being subtended by at least the width of the smallest square search area; and

calculating an angular height of the smallest square search area, the angular height being subtended by at least the height of the smallest square search area.

6. The method of claim 5, wherein the predetermined position has a predetermined position latitude and a predetermined position longitude, and wherein step (b) further comprises the steps of:

calculating respective latitudes for the first, the second and the third corners using the predetermined position latitude and the angular height of the smallest square search area; and

calculating respective longitudes for the first, the second and the third corners using the predetermined position longitude and the angular width of the smallest square search area.

7. The method of claim 6, wherein step (a) comprises the step of receiving an information request associated with the predetermined position and the search radius.

8. The method of claim 7, further comprising the step of:

(e) sending a search result based on the records associated with the position information determined to be within the smallest square search area at step (c), to fulfill the information request.

9. The method of claim 1, wherein step (b) further comprises calculating the circular and the smallest square search areas using a non-planar geometry.

10. The method of claim 1, wherein step (b) further comprises calculating the circular and the smallest square search areas using a planar geometry.

11. A method of performing a proximity search, comprising the steps of:

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

(b) mapping the circular search area to a smallest square search area into which the circular search area can fit based on the search radius and being defined in terms of a set of latitudes and longitudes, 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

(c) 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.

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

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

a proximity searcher that receives a search radius defining a circular search area centered around a predetermined position,

calculates a set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit based on the search radius, 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

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

13. The system of claim 12, wherein the proximity searcher is adapted to determine which of the plurality of records include the position information within the circular search area based on a comparison between the set of latitudes and longitudes and the position information in the plurality of records.

14. The system of claim 12, wherein the proximity searcher is adapted to compare respective latitudes and longitudes of at least first, second, and third corners of the smallest square search area, wherein the latitude range extends between the latitudes of the first and the second corners of the smallest square search area and the longitude range extends between the longitudes of the second and the third corners of the smallest square search area.

15. The system of claim 14, wherein the proximity searcher is adapted to calculate the latitudes and the longitudes of at least the first, the second, and the third corners of the smallest square search area, wherein the first and the second corners are at a same longitude but different latitudes and the second and the third corners are at a same latitude but different longitudes.

16. The system of claim 12, wherein the proximity searcher is adapted to

calculate an angular width of the smallest square search area, the angular width being subtended by at least the width of the smallest square search area, and

calculate an angular height of the smallest square search area, the angular height being subtended by at least the height of the smallest square search area.

17. The system of claim 16, wherein the predetermined position has a predetermined position latitude and a predetermined position longitude, and wherein the proximity searcher is adapted to

calculate respective latitudes for the first, the second and the third corners using the predetermined position latitude and the angular height of the smallest square search area, and

calculate respective longitudes for the first, the second and the third corners using the predetermined position longitude and the angular width of the smallest square search area.

18. The system of claim 17, wherein the proximity searcher is adapted to receive an information request associated with the predetermined position and the search radius.

19. The system of claim 18, wherein the proximity searcher is adapted to send a search result based on the records associated with the position information determined to be within the smallest square search area, to fulfill the information request.

20. The system of claim 12, wherein the proximity searcher is adapted to calculate the circular and the smallest square search areas using a non-planar geometry.

21. The system of claim 12, wherein the proximity searcher is adapted to calculate the circular and the smallest square search areas using a planar geometry.

22. A computer program product comprising computer usable media having computer readable program code means embodied in the media for causing application programs to execute on a computer processor to perform a proximity search, the computer readable program code means comprising:

a first computer readable program code means for causing the processor to receive a search radius defining a circular search area centered around a predetermined position;

a second computer readable program code means for causing the processor to calculate a set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit based on the search radius, 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

a third computer readable program code means for causing the processor to compare the set of latitudes and longitudes to position information in a plurality of records stored in a database to determine which of the position information in the plurality of records is 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,

to determine which of the position information in the plurality of records is within the smallest square search area.

23. The computer program product of claim 22, further comprising a fourth computer readable program code means for causing the processor to determine which of the position information in the plurality of records is within the circular search area based on a comparison between the set of latitudes and longitudes and the position information in the records.

24. The computer program product of claim 22, wherein the second computer program code means includes computer readable program code for causing the processor to calculate respective latitudes and longitudes of at least first, second, and third corners of the smallest square search area, wherein the latitude range extends between the latitudes of the first and the second corners of the smallest square search area and the longitude range extends between the longitudes of the second and the third corners of the smallest square search area.