Method and apparatus for an accelerated radius search

• US 6,108,650 A
• Filed: 08/21/1998
• Issued: 08/22/2000
• Est. Priority Date: 08/21/1998
• Status: Expired due to Fees

• Current Assignee: Myway.com Corporation
• Original Assignee: Myway.com Corporation
• Inventors: Chan, Leo, Musk, Elon, Wai, King-Sun
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LE, UYEN T
• Application Number:
  US09/138,185
• Time in Patent Office: 732 Days
• Field of Search: 707/4, 707/1, 707/3, 707/7, 340/825-49, 370/254-258
• US Class Current: 1/1
• CPC Class Codes: G06F 16/909 using geographical or spatial information, e.g. location spatiotemporally dependent retrieval from the web G06F16/9537
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus for performing an accelerated radius search. A search category is built having a density value corresponding to a geographic area. A first search radius is generated based upon the category, and the first search radius is used to perform a first search. If the first search returns an insufficient number of results, a second search radius is generated by using an heuristic to increase the first search radius, and the second search radius is used to perform a second search. The search is repeated until a desired results set is returned.

Claims

1. A computer implemented method for performing an accelerated radius search comprising:

building a category having a density value corresponding to a geographic area;

generating a first search radius based upon the category;

using the first search radius to perform a first search; and

if the first search returns an insufficient number of results,

generating a second search radius by using an heuristic to increase the first search radius; and

using the second search radius to perform a second search.

2. The method of claim 1 wherein building a category further comprises building a search radius for the category.

3. The method of claim 1 wherein using the first search radius to perform a first search further comprises using a geographical location and the first search radius to perform the first search.

4. The method of claim 1 wherein generating a second search radius further comprises expanding the first search radius based upon the density value of the category.

5. The method of claim 1 further comprising defining a minimum search size and a maximum search size.

6. The method of claim 1 further comprising generating the density value by determining a total number of records in a geographical region divided by the region size.

7. The method of claim 1 further comprising ordering the result of either the first or second search according to relevance data.

8. An apparatus for performing an accelerated radius search comprising:

a data receiver for receiving data representing geographic locations;

a processor coupled to the data receiver;

a category builder coupled to the processor to build a category having a density value corresponding to a geographic area;

a search radius generator coupled to the processor to generate a first search radius based upon the category;

a storage device coupled to the processor and having stored therein a routine, which when executing by the processor, causes the processor to at least,

use the first search radius to perform a first search; and

if the first search returns an insufficient number of results,

generate a second search radius by using an heuristic to increase the first search radius; and

use the second search radius to perform a second search.

9. The apparatus of claim 8 wherein the category builder further comprises a radius builder to build a search radius for the category.

10. The apparatus of claim 8 wherein the storage device further causes the processor to use a geographical location and the first search radius to perform the first search.

11. The apparatus of claim 8 wherein the storage device further causes the processor to generate a second search radius by expanding the first search radius based upon the density value of the category.

12. The apparatus of claim 8 wherein the storage device further causes the processor to define a minimum search size and a maximum search size.

13. The apparatus of claim 8 wherein the storage device further causes the processor to generate the density value by determining a total number of records in a geographical region divided by the region size.

14. The apparatus of claim 8 wherein the storage device further causes the processor to order the result of either the first or second search according to relevance data.

15. An article of manufacture for use in a computer system, the article of manufacture comprising a computer usable medium having computer readable program code means embodied in the medium, the program code means including:

computer readable program code means embodied in the computer usable medium for causing a computer to build a category having a density value corresponding to a geographic area;

computer readable program code means embodied in the computer usable medium for causing a computer to generate a first search radius based upon the category;

computer readable program code means embodied in the computer usable medium for causing a computer to use the first search radius to perform a first search; and

computer readable program code means embodied in the computer usable medium for causing a computer to, if the first search returns an insufficient number of results,

generate a second search radius by using an heuristic to increase the first search radius; and

use the second search radius to perform a second search.

16. The article of manufacture of claim 15 wherein the means for causing a computer to build a category further comprises means embodied in the computer usable medium for causing a computer to build a search radius for the category.

17. The article of manufacture of claim 15 wherein the means for causing a computer to use the first search radius to perform a first search further comprises means embodied in the computer usable medium for causing a computer to use a geographical location and the first search radius to perform the first search.

18. The article of manufacture of claim 15 wherein the means for causing a computer to generate a second search radius further comprises means embodied in the computer usable medium for causing a computer to expand the first search radius based upon the density value of the category.

19. The article of manufacture of claim 15 further comprising means embodied in the computer usable medium for causing a computer to define a minimum search size and a maximum search size.

20. The article of manufacture of claim 15 further comprising means embodied in the computer usable medium for causing a computer to generate the density value by determining a total number of records in a geographical region divided by the region size.

21. The article of manufacture of claim 15 further comprising means embodied in the computer usable medium for causing a computer to order the result of either the first or second search according to relevance data.