Proximity search methods using tiles to represent geographical zones
First Claim
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:
- 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;
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
identifying records having location pointers that are in the set.
8 Assignments
0 Petitions
Accused Products
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.
153 Citations
11 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:
-
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; 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 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.
- (i) receive an input of a searchable record including location information associated with the searchable record;
-
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.
Specification