Proximity search methods using tiles to represent geographical zones

• US 20060058958A1
• Filed: 09/14/2004
• Published: 03/16/2006
• Est. Priority Date: 09/14/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Friendster Incorporated (Mol.com Bhd.)
• Inventors: Galbreath, Nicholas, Soung, Yuh-Wen
• Granted Patent: US 7,606,687 B2
• Time in Patent Office: Days
• US Class Current: 701/214
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A proximity search engine for carrying out a proximity search with respect to a reference location uses as a reference frame the earth divided into tiles, which are predefined geographic regions of substantially equal areas. Records that are searched based on proximity to a reference location include location pointers, each of which identifies a particular tile that encompasses the physical location indicated by the corresponding record. When the proximity search is carried out, the tiles that are within a specified distance from the reference location are obtained and records having location pointers corresponding to such tiles are selected for inclusion in the search results.

Claims

1. A method of identifying records based on proximity to a reference location, comprising the steps of:

determining location data representative of the reference location;

converting said location data into a location pointer that points to one of a plurality of predefined geographic regions of substantially equal areas;

identifying predefined geographic regions of substantially equal areas whose distance from the reference location is within a certain distance; and

identifying records having location pointers that point to any of the identified predefined geographic regions.

2. The method according to claim 1, further comprising the step of receiving a search query in which said certain distance is specified.

3. The method according to claim 2, wherein the reference location is the location from which the search query is received.

4. The method according to claim 2, wherein the reference location is the location specified in a record corresponding to the user who submitted the search query.

5. The method according to claim 1, further comprising the step of maintaining a plurality of records in a database, each of the plurality of records including a location pointer to one of a plurality of predefined geographic regions of substantially equal areas.

6. The method according to claim 5, wherein the identified predefined geographic regions comprises a subset of the plurality of predefined geographic regions.

7. The method according to claim 1, wherein said location data comprises latitude and longitude values.

8. A method of managing records to be used in performing searches based on proximity to a reference location, said method comprising the steps of:

receiving an input of a record including location information;

converting the location information into a location pointer that identifies one of a plurality of predefined geographic regions of substantially equal areas; and

storing the location pointer in a memory device.

9. The method according to claim 8, wherein the location information comprises a zip code.

10. The method according to claim 9, wherein the step of converting includes the steps of retrieving a latitude value and a longitude value corresponding to the zip code and deriving the location pointer based on the latitude value and the longitude value.

11. The method according to claim 8, wherein the location information includes city and country.

12. The method according to claim 11, wherein the step of converting includes the steps of retrieving a latitude value and a longitude value corresponding to the city and the country and deriving the location pointer based on the latitude and the longitude.

13. The method according to claim 8, wherein each of the predefined geographical regions has a common upper latitude boundary and a common lower latitude boundary.

14. The method according to claim 13, wherein a distance from the upper latitude boundary and the lower latitude boundary is the same for all predefined geographical regions.

15. A record management system for performing searches based on proximity to a reference location, comprising:

a memory device containing a plurality of searchable records, each searchable record including location pointer that identifies one of a plurality of predefined geographic regions of substantially equal areas; and

a processor programmed to;

(i) receive a search query including the reference location and a distance value; and

(ii) determine all location pointers that identify predefined geographic regions whose distance from the reference location is within the distance value.

16. The system according to claim 15, wherein the processor is further programmed to:

(i) receive an input of a searchable record including location information associated with the searchable record;

(ii) convert the location information into a location pointer that identifies one of the plurality of predefined geographic regions; and

(iii) store the location pointer.

17. The system according to claim 16, wherein the location information comprises a zip code.

18. The system according to claim 16, wherein the location information includes city and country.

19. The system according to claim 15, wherein the predefined geographical regions define a two-dimensional map and each location pointer pinpoints a position on the two-dimensional map.

20. The system according to claim 19, wherein each location pointer includes first and second values, each corresponding to one of the two coordinates of the two-dimensional map.