Proximity search methods using tiles to represent geographical zones

• US RE44,876 E1
• Filed: 10/19/2011
• Issued: 04/29/2014
• Est. Priority Date: 09/14/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Galbreath, Nicholas, Soung, Yuh-Wen
• Primary Examiner(s): Rivas, Omar Fernandez
• Assistant Examiner(s): LUU, CUONG V
• Application Number:
  US13/277,008
• Time in Patent Office: 923 Days
• Field of Search: 340/988, 340/539.11, 709/220, 709/229, 709/204, 709/230, 701/455, 379/196
• US Class Current: 703/3
• 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 carried out by a computer system of identifying records based on proximity to a reference location in response to a search query, comprising the steps of:

by one or more computing devices, determining location data representative of the reference location;

converting said location data into a reference location pointer that points to one of a plurality of predefined geographic regions, each of the predefined geographic regions having four sides of an equal surface distance and associated with a location pointer having a first index and a second index, the first index and the second index identifying a point on a coordinate system;

by the one or more computing devices, identifying a set of location pointers whose corresponding predefined geographic regions are within a certain distance from the predefined geographic region corresponding to the reference location pointer using an integer number, N, which is obtained by dividing the certain distance by the equal surface distance, wherein each of the location pointers in the set has a first index that differs from the first index of the reference location pointer by no more than N and a second index that differs from a third index by no more than N, wherein the third index is a function of the first index of the reference location pointer and represents the same longitudinal position as the reference location pointer; and

by the one or more computing devices, identifying records having location pointers that are in the set.

2. The method according to claim 1, wherein the search query specifies the certain distance.

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 the plurality of predefined geographic regions.

6. The method according to claim 5, wherein the predefined geographic regions corresponding to the set of location pointers 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 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 a location pointer that corresponds to one of a plurality of predefined geographic regions, each of the predefined geographic regions having four sides of an equal surface distance and associated with a location pointer having a first index and a second index, the first index and the second index identifying a point on a coordinate system; and

a processor programmed to;

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

(ii) generate a reference location pointer having a first index and a second index for the reference location;

(iii) divide the distance value by the equal surface distance to obtain an integer number, N;

(iv) identify a set of location pointers having a first index that differs from the first index of the reference location pointer by no more than N and a second index that differs from a third index by no more than N, wherein the third index is a function of the first index of the reference location pointer and represents the same longitudinal position as the reference location pointer; and

(v) return records having location pointers in the identified set.

9. The system according to claim 8, 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 corresponds to one of the plurality of predefined geographic regions; and

(iii) store the location pointer.

10. The system according to claim 9, wherein the location information comprises a zip code.

11. The system according to claim 9, wherein the location information includes city and country.

12. A method comprising:

by one or more computing devices, receiving a query from a first user of a social-networking system, the social-networking system comprising a graph that comprises a plurality of nodes and edges connecting the nodes, at least one node in the graph corresponding to the first user, the query comprising one or more location data corresponding to a location of the first user;

by the computing devices, identifying one or more second users of the social-networking system that are connected to the first user within the social-networking system, at least one node in the graph corresponding to each of the second users, at least one of the nodes corresponding to the first user and at least one of the nodes corresponding to a second user being connected to each other by one or more edges;

by the computing devices, determining a location of each of one or more of the second users;

by the computing devices, identifying one or more of the second users that are located within a threshold distance of the location of the first user, wherein identifying one or more of the second users that are located within a threshold distance of the location of the first users comprises;

by the computing devices, converting location information associated with each of at least one of the nodes corresponding to the second users to a location pointer that points to one of a plurality of predefined geographic regions, each of the plurality of predefined geographic regions having four sides of an equal surface distance and is associated with a location pointer having a first index and a second index, the first index and the second index identifying a point on a coordinate system;

by the computing devices, converting the one or more location data into a reference location pointer that points to one of the plurality of predefined geographic regions; and

by the computing devices, identifying a set of location pointers whose corresponding predefined geographic regions are within the distance from the predefined geographic region corresponding to the reference location pointer using an integer number, N, which is obtained by dividing the distance by the equal surface distance, wherein each location pointer from the set of location pointers has a first index that differs from the first index of the reference location pointer by no more than N and a second index that differs from a third index by no more than N, wherein the third index is a function of the first index of the reference location pointer and represents the same longitudinal position as the reference location pointer; and

by the computing devices, providing, as a response to the query, information associated with each of one or more of the second users that are located within the threshold distance of the location of the first user.

13. The method of claim 12, further comprising sending the response to the first user.

14. The method of claim 12, wherein the query comprises the threshold distance.

15. The method of claim 12, wherein:

the query comprises one or more keywords;

each of one or more nodes in the graph corresponding to each of one or more second users is associated with one or more keywords;

the method further comprises, by the computing devices, identifying among the second users that are located within the threshold distance of the location of the first user one or more second users that correspond to nodes associated with keywords matching the keywords of the query; and

information associated with a second user is provided as a response to the query only if the node corresponding to the second is associated with keywords matching the keywords in the query.

16. The method of claim 12, wherein:

the query comprises a gender;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a gender of the second user;

the method further comprises, by the computing devices, identifying among the second users that are located within the threshold distance of the location of the first user one or more second users that match the gender in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the gender in the query.

17. The method of claim 12, wherein:

the query comprises a marital status;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a marital status of the second user;

the method further comprises, by the computing devices, identifying among the second users that are located within the threshold distance of the location of the first user one or more second users that match the marital status in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the marital status in the query.

18. The method of claim 12 wherein identifying one or more of the second users that are located within a threshold distance of the location of the first users comprises:

mapping location information associated with each of at least one of the nodes corresponding to the second users to one of a plurality of geographic regions; and

mapping the location data to a first geographic region of the plurality of geographic regions.

19. A system comprising:

a memory comprising instructions executable by one or more processors; and

the processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

receive a query from a first user of a social-networking system, the social-networking system comprising a graph that comprises a plurality of nodes and edges connecting the nodes, at least one node in the graph corresponding to the first user, the query comprising one or more location data corresponding to a location of the first user;

identify one or more second users of the social-networking system that are connected to the first user within the social-networking system, at least one node in the graph corresponding to each of the second users, at least one of the nodes corresponding to the first user and at least one of the nodes corresponding to a second user being connected to each other by one or more edges;

determine a location of each of one or more of the second users;

identify one or more of the second users that are located within a threshold distance of the location of the first user, wherein to identify one or more of the second users that are located within a threshold distance of the location of the first users, the one or more processors are operable when executing the instructions to;

convert location information associated with each of at least one of the nodes corresponding to the second users to a location pointer that points to one of a plurality of predefined geographic regions, each of the plurality of predefined geographic regions having four sides of an equal surface distance and is associated with a location pointer having a first index and a second index, the first index and the second index identifying a point on a coordinate system;

convert the one or more location data into a reference location pointer that points to one of the plurality of predefined geographic regions; and

identify a set of location pointers whose corresponding predefined geographic regions are within the distance from the predefined geographic region corresponding to the reference location pointer using an integer number, N, which is obtained by dividing the distance by the equal surface distance, wherein each location pointer from the set of location pointers has a first index that differs from the first index of the reference location pointer by no more than N and a second index that differs from a third index by no more than N, wherein the third index is a function of the first index of the reference location pointer and represents the same longitudinal position as the reference location pointer; and

provide as a response to the query information associated with each of one or more of the second users that are located within the threshold distance of the location of the first user.

20. The system of claim 19, wherein the processors are further operable when executing the instructions to send the response to the first user.

21. The system of claim 19, wherein the query comprises the threshold distance.

22. The system of claim 19, wherein:

the query comprises one or more keywords;

each of one or more nodes in the graph corresponding to each of one or more second users is associated with one or more keywords;

the processors are further operable when executing the instructions to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that correspond to nodes associated with keywords matching the keywords of the query; and

information associated with a second user is provided as a response to the query only if the node corresponding to the second is associated with keywords matching the keywords in the query.

23. The system of claim 19, wherein:

the query comprises a gender;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a gender of the second user;

the processors are further operable when executing the instructions to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that match the gender in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the gender in the query.

24. The system of claim 19, wherein:

the query comprises a marital status;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a marital status of the second user;

the processors are further operable when executing the instructions to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that match the marital status in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the marital status in the query.

25. The system of claim 19, wherein, to identify one or more of the second users that are located within a threshold distance of the location of the first users, the processors are operable when executing the instructions to:

map location information associated with each of at least one of the nodes corresponding to the second users to one of a plurality of geographic regions; and

map the location data to a first geographic region of the plurality of geographic regions.

26. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

receive a query from a first user of a social-networking system, the social-networking system comprising a graph that comprises a plurality of nodes and edges connecting the nodes, at least one node in the graph corresponding to the first user, the query comprising one or more location data corresponding to a location of the first user;

identify one or more second users of the social-networking system that are connected to the first user within the social-networking system, at least one node in the graph corresponding to each of the second users, at least one of the nodes corresponding to the first user and at least one of the nodes corresponding to a second user being connected to each other by one or more edges;

determine a location of each of one or more of the second users;

identify one or more of the second users that are located within a threshold distance of the location of the first user, wherein, to identify one or more of the second users that are located within a threshold distance of the location of the first users, the software is further operable when executed to;

convert location information associated with each of at least one of the nodes corresponding to the second users to a location pointer that points to one of a plurality of predefined geographic regions, each of the plurality of predefined geographic regions having four sides of an equal surface distance and is associated with a location pointer having a first index and a second index, the first index and the second index identifying a point on a coordinate system;

convert the one or more location data into a reference location pointer that points to one of the plurality of predefined geographic regions; and

identify a set of location pointers whose corresponding predefined geographic regions are within the distance from the predefined geographic region corresponding to the reference location pointer using an integer number, N, which is obtained by dividing the distance by the equal surface distance, wherein each location pointer from the set of location pointers has a first index that differs from the first index of the reference location pointer by no more than N and a second index that differs from a third index by no more than N, wherein the third index is a function of the first index of the reference location pointer and represents the same longitudinal position as the reference location pointer; and

provide as a response to the query information associated with each of one or more of the second users that are located within the threshold distance of the location of the first user.

27. The media of claim 26, wherein the software is further operable when executed to send the response to the first user.

28. The media of claim 26, wherein the query comprises the threshold distance.

29. The media of claim 26, wherein:

each of one or more nodes in the graph corresponding to each of one or more second users is associated with one or more keywords;

the software is further operable when executed to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that correspond to nodes associated with keywords matching the keywords of the query; and

information associated with a second user is provided as a response to the query only if the node corresponding to the second is associated with keywords matching the keywords in the query.

30. The media of claim 26, wherein:

the query comprises a gender;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a gender of the second user;

the software is further operable when executed to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that match the gender in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the gender in the query.

31. The media of claim 26, wherein:

the query comprises a marital status;

each of one or more nodes in the graph corresponding to each of one or more second users indicates a marital status of the second user;

the software is further operable when executed to identify among the second users that are located within the threshold distance of the location of the first user one or more second users that match the marital status in the query; and

information associated with a second user is provided as a response to the query only if the second user matches the marital status in the query.

32. The media of claim 26, wherein, to identify one or more of the second users that are located within a threshold distance of the location of the first users, the software is further operable when executed to:

map location information associated with each of at least one of the nodes corresponding to the second users to one of a plurality of geographic regions; and

map the location data to a first geographic region of the plurality of geographic regions.