Back to results
US RE44,876 E1Granted
Proximity search methods using tiles to represent geographical zones
AssigneeFacebook, Inc.
InventorsNicholas Galbreath, Yuh-Wen Soung
Life of this patent
Estimating the term…
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.
Claims32
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 more elements
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.
5 more elements
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.
7 more elements
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.
10 more elements
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.
7 more elements
Dependencies are inferred from the claim text.