System and method for retrieving location-qualified site data
First Claim
1. A method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in said site set is located in a location space, wherein said location space is partitioned into cells so that each site in said site set is associated with exactly one cell, wherein site data pertaining to sites in said site set is contained in a site data repository, wherein said site data comprises a site identifier for each site, and wherein said method comprises the steps of:
- (a) generating at least one linkcell, each linkcell being a cell having at least one site associated therewith, wherein the location of each site in said location space is defined by one or more coordinates, wherein a cell identifier derived from said coordinates is assigned to each linkcell such that each cell identifier uniquely identifies the linkcell with which a site in said site set is associated from the location of the site, and wherein each linkcell is linked to at least one data table for storing site identifiers of sites associated with said linkcell;
(b) receiving a user'"'"'s location;
(c) receiving a user request to retrieve site data pertaining to a specified number of sites closest to said user'"'"'s location;
(d) defining a core cell, wherein said core cell is in a searchable area defined in said location space;
(e) defining a cursor cell, wherein said cursor cell traverses a path of cells in said searchable area starting with said core cell until either said cursor cell has traversed all of said searchable area or said cursor cell has traversed one or more predefined layers of cells containing at least the specified number of sites, and wherein the following substeps are performed;
(1) deriving a cell identifier for each cell in said path traversed by said cursor cell, determining if there exists a linkcell to which the respective derived cell identifier has been assigned, and where so determined, identifying sites associated with that linkcell from the site identifiers stored in one or more data tables linked thereto, and (2) for each site identified in substep (1), determining storing the site identifier therefor and the distance between the user'"'"'s location and the identified site and storing the site identifier therefor and said determined distance in a result table;
(f) determining any additional linkcells in said searchable area that could have sites associated therewith that are closer to the user'"'"'s location than any of the sites identified in step (e);
(g) identifying sites associated with said any additional linkcells;
(h) for each site associated with said any additional linkcells, determining the distance between the user'"'"'s location and said site and storing the site identifier therefor and said determined distance in a said result table;
(i) determining the specified number of sites closest to said user'"'"'s location from the distances stored in said result table;
(j) retrieving site data pertaining to the specified number of sites closest to said user'"'"'s location determined in step (i); and
(k) outputting site data retrieved in step (j)to a user.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention is directed to the use of linkcells in retrieving site data pertaining to one or more sites from a site data repository. The linkcells facilitate the resolution of several types of queries, including queries to determine a specified number of closest sites to a user'"'"'s location and queries to determine sites located with a specified distance of the user'"'"'s location. In one aspect, the present invention relates to a linkcell having a cell perimeter that comprises one or more cell boundary sections, a cell identifier, and a link to a data table, where one or more sites are associated with the linkcell, and where site data pertaining to those sites is stored in the data table. The cell identifier may be a name derived from the coordinates of sites associated with the linkcell. Advantageously, it is not typically necessary to examine data on all sites in the site data repository to resolve queries if linkcells are used.
25 Citations
17 Claims
-
1. A method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in said site set is located in a location space, wherein said location space is partitioned into cells so that each site in said site set is associated with exactly one cell, wherein site data pertaining to sites in said site set is contained in a site data repository, wherein said site data comprises a site identifier for each site, and wherein said method comprises the steps of:
-
(a) generating at least one linkcell, each linkcell being a cell having at least one site associated therewith, wherein the location of each site in said location space is defined by one or more coordinates, wherein a cell identifier derived from said coordinates is assigned to each linkcell such that each cell identifier uniquely identifies the linkcell with which a site in said site set is associated from the location of the site, and wherein each linkcell is linked to at least one data table for storing site identifiers of sites associated with said linkcell;
(b) receiving a user'"'"'s location;
(c) receiving a user request to retrieve site data pertaining to a specified number of sites closest to said user'"'"'s location;
(d) defining a core cell, wherein said core cell is in a searchable area defined in said location space;
(e) defining a cursor cell, wherein said cursor cell traverses a path of cells in said searchable area starting with said core cell until either said cursor cell has traversed all of said searchable area or said cursor cell has traversed one or more predefined layers of cells containing at least the specified number of sites, and wherein the following substeps are performed;
(1) deriving a cell identifier for each cell in said path traversed by said cursor cell, determining if there exists a linkcell to which the respective derived cell identifier has been assigned, and where so determined, identifying sites associated with that linkcell from the site identifiers stored in one or more data tables linked thereto, and (2) for each site identified in substep (1), determining storing the site identifier therefor and the distance between the user'"'"'s location and the identified site and storing the site identifier therefor and said determined distance in a result table;
(f) determining any additional linkcells in said searchable area that could have sites associated therewith that are closer to the user'"'"'s location than any of the sites identified in step (e);
(g) identifying sites associated with said any additional linkcells;
(h) for each site associated with said any additional linkcells, determining the distance between the user'"'"'s location and said site and storing the site identifier therefor and said determined distance in a said result table;
(i) determining the specified number of sites closest to said user'"'"'s location from the distances stored in said result table;
(j) retrieving site data pertaining to the specified number of sites closest to said user'"'"'s location determined in step (i); and
(k) outputting site data retrieved in step (j)to a user. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
(a) a site data repository, wherein site data pertaining to sites in said site set is contained in said site data repository;
(b) a storage means for storing data tables;
(c) a user interface; and
(d) one or more processing modules connected to said site data repository, said storage means, and said user interface, wherein said one or more processing modules are programmed to perform the steps of the method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set as claimed in claim 1.
-
-
15. The method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set as claimed in claim 1, wherein each data table has a name derived from the cell identifier of the linkcell linked thereto.
-
16. The method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set as claimed in claim 1, wherein in determining the distance between the user'"'"'s location and an identified site in step (e), the location of the identified site is retrieved from data stored in the site data repository.
-
17. The method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set as claimed in claim 1, wherein in determining the distance between the user'"'"'s location and an identified site in step (e), the location of the identified site is retrieved from data stored in a data table.
Specification