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

• US 20020059226A1
• Filed: 04/25/2001
• Published: 05/16/2002
• Est. Priority Date: 04/25/2000
• Status: Active Grant

• Current Assignee: Buffalo Patents, LLC
• Original Assignee: Icplanet Corporation
• Inventors: Cooper, Jeremy S.
• Granted Patent: US 7,007,010 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• 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 proximity parameter defining a search area encompassing a predetermined position;

(b) calculating a set of latitudes and longitudes approximating the search area based on the proximity parameter; and

(c) comparing the set of latitudes and longitudes to position field information in a plurality of records stored in a database.

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

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

3. The method of claim 1, wherein the proximity parameter is a search radius defining a circular search area centered around the predetermined position, and wherein step (b) further comprises the step of calculating the set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit.

4. The method of claim 3, wherein the position information in each of the plurality of records includes a latitude and a longitude associated with a position, and

wherein the smallest square search area covers a latitude range and a longitude range corresponding respectively to a height and a width of the square each corresponding to a distance equal to at least twice the proximity parameter, and

wherein step (c) comprises respectively comparing the latitude and longitude associated with each of the plurality of records to the latitude and longitude ranges covered by the smallest square search area to determine which of the plurality of records include position information within the square search area.

5. The method of claim 4, wherein step (b) further comprises calculating respective latitudes and longitudes of at least first, second, and third comers of the square area, wherein the latitude range extends between the latitudes of the first and second comers and the longitude range extends between the longitudes of the second and third comers of the square area.

6. The method of claim 5, wherein step (b) further comprises calculating latitudes and longitudes of at least the first, second, and third comers of the square area, wherein the first and second comers are at the same longitude but different latitudes and the second and third comers are at the same latitude but different longitudes.

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

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

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

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

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

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

9. The method of claim 8, wherein step (a) comprises the step of receiving an information request associated with the predetermined position and the proximity parameter.

10. The method of claim 9, further comprising the step of:

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

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

12. The method of claim 4, wherein step (b) further comprises calculating the circular and the square search areas using planar geometry.

14. The method of claim 13, wherein the proximity parameter is a search radius defining a circular search area centered around the predetermined position, and wherein step (b) comprises mapping the circular search area to a smallest square search area into which the circular search area can fit.

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

17. The system of claim 15, wherein the proximity parameter is a search radius defining a circular search area centered around the predetermined position, and wherein the proximity searcher is adapted to calculate the set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit.

18. The system of claim 17, wherein the position information in each of the plurality of records includes a latitude and a longitude associated with a position, and

wherein the smallest square search area covers a latitude range and a longitude range corresponding respectively to a height and a width of the square each corresponding to a distance equal to at least twice the proximity parameter, and

wherein the proximity searcher is adapted to respectively compare the latitude and longitude associated with each of the plurality of records to the latitude and longitude ranges covered by the smallest square search area to determine which of the plurality of records include position information within the square search area.

19. The system of claim 18, wherein the proximity searcher is adapted to compare respective latitudes and longitudes of at least first, second, and third comers of the square area, wherein the latitude range extends between the latitudes of the first and second comers and the longitude range extends between the longitudes of the second and third comers of the square area.

20. The system of claim 19, wherein the proximity searcher is adapted to calculate latitudes and longitudes of at least the first, second, and third comers of the square area, wherein the first and second comers are at the same longitude but different latitudes and the second and third comers are at the same latitude but different longitudes.

21. The system of claim 18, wherein the proximity searcher is adapted to

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

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

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

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

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

23. The system of claim 22, wherein the proximity searcher is adapted to receive an information request associated with the predetermined position and the proximity parameter.

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

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

26. The system of claim 18, wherein the proximity searcher is adapted to calculate the circular and the square search areas using planar geometry.

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

29. The computer program product of claim 27, wherein the proximity parameter is a search radius defining a circular search area centered around the predetermined position, and wherein the second program code means includes computer readable program code means for causing the processor to calculate the set of latitudes and longitudes to define a smallest square search area into which the circular search area can fit.

30. The computer program product of claim 29, wherein the position information in each of the plurality of records includes a latitude and a longitude associated with the record, and

wherein the smallest square search area covers a latitude range and a longitude range corresponding respectively to a height and a width of the square each corresponding to a distance equal to at least twice the proximity parameter, and

wherein the third program code means includes computer readable program code means for causing the processor to respectively compare the latitude and longitude associated with each of the plurality of records to the latitude and longitude ranges covered by the smallest square search area to determine which of the plurality of records include position information within the square search area.

31. The computer program product of claim 30, 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 comers of the square area, wherein the latitude range extends between the latitudes of the first and second comers and the longitude range extends between the longitudes of the second and third comers of the square area.

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

(a) receiving a proximity parameter defining a first search area encompassing a predetermined position;

(b) mapping the first search area to a second search area positioned to encompass the first search area based on the proximity parameter and being defined in terms of a set of latitudes and longitudes; 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 position information within the second search area.

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

a database including a plurality of records for storing position field information; and

a proximity searcher that receives a proximity parameter defining a search area encompassing a predetermined position,

calculates a set of latitudes and longitudes approximating the search area based on the proximity parameter, and

compares the set of latitudes and longitudes to position field information in a plurality of records stored in a database.

27. A computer program product comprising computer usable media having computer readable program code means embodied in the media for causing application programs to execute o n 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 proximity parameter defining a search area encompassing a predetermined position;

a second computer readable program code means for causing the processor to calculate a set of latitudes and longitudes approximating the search area based on the proximity parameter; and

a third computer readable program code means for causing the processor to compare the set of latitudes and longitudes to position field information in a plurality of records stored in a database.