Methods and apparatus for providing a location based search

• US 8,364,689 B2
• Filed: 12/22/2006
• Issued: 01/29/2013
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Hao, Jianxiu
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US11/615,519
• Publication Number:
  US 20080154876A1
• Time in Patent Office: 2,230 Days
• Field of Search: 707/758
• US Class Current: 707/758
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods and apparatuses for providing location based searches and other services are provided. Embodiments may include dividing a searchable region into quad regions and populating the search regions with a plurality of listings. The division of quad regions may be dependent on a maximum number of listings per quad region and a minimum size for any one quad region. Embodiments may include assigning unique identifiers to each quad regions and assigning the unique identifiers to each of the listings according to the quad region in which the listings are located as geographical codes. The geographical codes may be used as part a location based search. In some of the embodiments, the listings may be searched by prefixes of the geographical codes rather than the entire geographical codes.

Claims

1. A method comprising:

receiving a search request for one or more listings within an area of interest defined in relation to a point of interest;

identifying a number of geographically indexed reference regions that have at least a partial overlap with the area of interest, each geographically indexed reference region having an associated identifier;

selecting a geographical code matching search precision based on comparing the number of identified geographically indexed reference regions to a threshold number of geographically indexed reference regions overlapping the area of interest, wherein the selecting a geographical code matching search precision comprises;

searching, when the number of identified geographically indexed reference regions is greater than the threshold number of geographically indexed reference regions overlapping the area of interest, for each listing of a plurality of listings having a geographical code sharing at least a prefix of an identifier of at least one of the identified geographically indexed reference regions; and

searching, when the number of identified geographically indexed reference regions is less than or equal to the threshold number of geographically indexed reference regions overlapping the area of interest, for each listing of the plurality of listings having a geographical code equal to the identifier of at least one of the identified geographically indexed reference regions.

2. The method according to claim 1 further comprising providing a unique identifier for each of the one or more geographically indexed reference regions, wherein each unique identifier includes a plurality of digits;

and

assigning each listing of the plurality of listings a geographical code based on the unique identifier of a geographically indexed reference region in which the listing is located.

3. The method according to claim 2 further comprising dividing a searchable region into the one or more geographically indexed reference regions;

and

populating the searchable region with the plurality of listings.

4. The method according to claim 3, wherein the dividing the searchable region into the plurality of geographically indexed reference regions includes further dividing a geographically indexed reference region into additional geographically indexed reference regions when a number of listings within the geographically indexed reference region reaches a maximum number unless dividing the geographically indexed reference region would reduce a size of the geographically indexed reference region below a minimum number.

5. The method according to claim 1 further comprising filtering any listings identified during the searching to exclude any listing that is located outside the area of interest.

6. The method according to claim 5 further comprising responding to the search request with any listings identified by the filtering.

7. The method according to claim 1, wherein the receiving the search request for one or more listings within the area of interest defined by a distance to a point of interest and the searching further include searching for one or more listings within the area of interest and having one or more specified attributes.

22. The method of claim 1, wherein searching when the number of identified geographically indexed reference regions is greater than the threshold further comprises:

determining a length of the prefix.

23. The method of claim 22, wherein determining the length of the prefix further comprises:

repeatedly removing a digit of the identifier of the at least one of the geographically indexed reference regions until the number of identified geographically indexed reference regions is less than or equal to the threshold.

8. A computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion configured to receive a search request for one or more listings within an area of interest defined by a distance to a point of interest;

a second executable portion configured to determine a number and an identity of one or more geographically indexed reference regions that have at least a partial overlap with the area of interest; and

a third executable portion configured to select a geographical code matching search precision based on comparing the number of identified geographically indexed reference regions to a threshold number of geographically indexed reference regions overlapping the area of interest, wherein the third executable portion configured to select a geographical code matching search precision comprises

(i) search for each listing of a plurality of listings having a geographical code sharing at least a prefix of the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is greater than the threshold number of geographically indexed reference regions overlapping the area of interest, and

(ii) search for each listing of the plurality of listings having a geographical code_equal to the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is less than or equal to the threshold number of geographically indexed reference regions overlapping the area of interest.

9. The computer program product according to claim 8 further comprising a fourth executable portion configured to provide a unique identifier for each of the one or more geographically indexed reference regions, wherein each unique identifier number includes a plurality of digits;

and

a fifth executable portion configured to assign each listing of the plurality of listings a geographical code based on the unique identifier of a geographically indexed reference region in which the listing is located.

10. The computer program product according to claim 9 further comprising a sixth executable portion configured to divide a searchable region into the plurality of geographically indexed reference regions;

and a seventh executable portion configured to populate the searchable region with the plurality of listings.

11. The computer program product according to claim 10, wherein the sixth executable portion is further configured to divide a geographically indexed reference region into additional geographically indexed reference regions when a number of listings within the geographically indexed reference region reaches a maximum number unless dividing the geographically indexed reference region would reduce a size of the geographically indexed reference region below a minimum number.

12. The computer program product according to claim 8 further comprising a fourth executable portion configured to filter any listings identified during the searching of the third executable portion to exclude any listing of the plurality of listings that is located outside the area of interest.

13. The computer program product according to claim 12 further comprising a fifth executable portion for responding to the search request with any listings identified by the filtering of the fourth executable portion.

14. The computer program product according to claim 8, wherein the first executable portion is further configured to receive the search request for one or more listings within an area of interest that have one or more specified attributes and the third executable portion ifs further configured to either

(i) search for one or more listings having the one or more specific attributes and a geographical code sharing at least a prefix of the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is greater than a threshold number, or

(ii) search for each listing of the plurality of listings having the one or more specific attributes and a geographical code equal to the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is less than or equal to the threshold number.

15. An apparatus comprising:

a memory; and

a processor configured to receive a search request for one or more listings within an area of interest defined by a distance to a point of interest;

the processor configured to determine a number and an identity of one or more geographically indexed reference regions that have at least a partial overlap with the area of interest; and

the processor configured to select a geographical code matching search precision based on comparing the number of identified geographically indexed reference regions to a threshold number of geographically indexed reference regions overlapping the area of interest, wherein the configured to select a geographical code matching search precision comprises;

(i) search for each listing of a plurality of listings having a geographical code sharing at least a prefix of the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is greater than a threshold number of geographically indexed reference regions overlapping the area of interest, and

(ii) search for each listing of the plurality of listings having a geographical code equal to the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is less than or equal to the threshold number of geographically indexed reference regions overlapping the area of interest.

16. The apparatus according to claim 15, wherein the processor is further configured to provide a unique identifier for each of the one or more geographically indexed reference regions, wherein each unique identifier number includes a plurality of digits;

and

to assign each listing of the plurality of listings a geographical code based on the unique identifier of a geographically indexed reference region in which the listing is located.

17. The apparatus according to claim 16, wherein the processor is further configured to divide a searchable region into the plurality of geographically indexed reference regions;

and to populate the searchable region with the plurality of listings.

18. The apparatus according to claim 17, wherein the processor is further configured to divide a geographically indexed reference region into additional geographically indexed reference regions when a number of listings within the geographically indexed reference region reaches a maximum number unless dividing the geographically indexed reference region would reduce a size of the geographically indexed reference region below a minimum number.

19. The apparatus according to claim 15, wherein the processor is further configured to filter any listings identified during the searching to exclude an listing of the plurality of listings that is located outside the area of interest.

20. The apparatus according to claim 19, wherein the processor is further configured to respond to the search request with any listings identified by the filtering.

21. The apparatus of claim 15, wherein the processor is further configured to receive the search request for one or more listings within an area of interest that have one or more specified attributes and to either

(i) search for one or more listings having the one or more specific attributes and a geographical code sharing at least a prefix of the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is greater than a threshold number, or

(ii) search for each listing of the plurality of listings having the one or more specific attributes and a geographical code equal to the identifier of at least one of the one or more geographically indexed reference regions that has at least a partial overlap with the area of interest when the number of the one or more geographically indexed reference regions that have at least a partial overlap with the area of interest is less than or equal to the threshold number.