System and method for retrieving location-qualified site data

• US 20030033273A1
• Filed: 08/13/2001
• Published: 02/13/2003
• Est. Priority Date: 08/13/2001
• Status: Active Grant

• Current Assignee: James E. Wyse
• Original Assignee: Genesis Group Inc.
• Inventors: Wyse, James Edmund
• Granted Patent: US 6,792,421 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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.

Claims

1. A method of generating linkcells for use in 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 site data pertaining to sites in said site set is contained in a site data repository, and wherein said method comprises the steps of:

(a) partitioning said location space into a plurality of cells;

(b) associating each site in said site set with one of said plurality of cells;

(c) defining a plurality of linkcells, wherein said plurality of linkcells is a subset of cells in said plurality of cells, and wherein each of said plurality of linkcells has at least one site associated therewith;

(d) assigning a cell identifier to each of said plurality of linkcells;

(e) linking a data table to each of said plurality of linkcells; and

(f) for each of said plurality of linkcells, storing site data pertaining to all sites associated therewith in the data table linked thereto.

2. The method of generating linkcells as claimed in claim 1, wherein each site in said site set is associated with exactly one of said plurality of cells.

3. The method of generating linkcells as claimed in claim 1, wherein each of said plurality of cells comprises a cell space within said location space, wherein said cell space is defined by a cell perimeter that comprises one or more cell boundary sections, and wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith.

4. The method of generating linkcells as claimed in claim 3, wherein a site in said site set is associated with a specific cell of said plurality of cells only if said site is located in the cell space of said specific cell.

5. The method of generating linkcells as claimed in claim 3, wherein each of said one or more cell boundary sections is associated with the same predefined coordinate interval.

6. The method of generating linkcells as claimed in claim 3, wherein the location of a site is defined by at least two coordinates.

7. The method of generating linkcells as claimed in claim 6, wherein a cell identifier is derived from said at least two coordinates, said at least two coordinates defining the location of a site associated with the linkcell to which said cell identifier is assigned.

8. The method of generating linkcells as claimed in claim 7, wherein the cell identifier assigned to a linkcell is also assigned to the data table linked to said linkcell.

9. The method of generating linkcells as claimed in claim 7, wherein the cell identifier is a name composed of a plurality of components, wherein each component of said plurality of components is associated with a coordinate of said at least two coordinates.

10. The method of generating linkcells as claimed in claim 9, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval.

11. The method of generating linkcells as claimed in claim 9, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval and multiplied by a scaling factor.

12. The method of generating linkcells as claimed in claim 1, wherein site data pertaining to each site in said site set comprises a site identifier and a site category identifier.

13. The method of generating linkcells as claimed in claim 12, wherein site data pertaining to each site associated with the plurality of linkcells must comprise a user-specified site category identifier.

14. The method of generating linkcells as claimed in claim 1, wherein the storing of site data in a data table is effected by saving one or more links to site data contained in said site data repository in said data table.

15. The method of generating linkcells as claimed in claim 1, further comprising the step of creating a plurality of data tables.

16. The method of generating linkcells as claimed in claim 1, wherein upon the addition of a new site to said site set, the following steps are performed:

(i) associating said new site with a selected cell of said plurality of cells;

(ii) if no sites in said site set are associated with said selected cell;

redefining said plurality of linkcells to include said selected cell,

assigning a cell identifier to said selected cell, and

linking a data table to said selected cell;

(iii) storing site data pertaining to said new site in the data table linked to said selected cell; and

(iv) adding said new site to said site set.

17. The method of generating linkcells as claimed in claim 1, wherein upon the addition of a new site to said site set, the following steps are performed:

(i) associating said new site with a selected cell of said plurality of cells;

(ii) if no sites in said site set are associated with said selected cell;

redefining said plurality of linkcells to include said selected cell,

assigning a cell identifier to said selected cell,

creating a new data table, and

linking said new data table to said selected cell;

(iii) storing site data pertaining to said new site in the data table linked to said selected cell; and

(iv) adding said new site to said site set.

18. The method of generating linkcells as claimed in claim 1, wherein upon receipt of a request to remove an existing site from a site set, the following steps are performed:

(i) determining a selected linkcell with which said specified existing site is associated;

(ii) if said specified existing site is the only site associated with said selected linkcell;

redefining said plurality of linkcells to exclude said selected linkcell,

removing the assignment of the cell identifier assigned to said selected linkcell, and

removing the link to the data table linked to said selected linkcell;

 

otherwise, if said specified existing site is not the only site associated with said selected linkcell;

removing site data pertaining to said specified existing site from the data table linked to said selected linkcell and from said site data repository; and

(iii) removing said specified existing site from said site set.

19. The method of generating linkcells as claimed in claim 1, wherein upon receipt of a request to remove an existing site from a site set, the following steps are performed:

(i) determining a selected linkcell with which said specified existing site is associated;

(ii) if said specified existing site is the only site associated with said selected linkcell;

redefining said plurality of linkcells to exclude said selected linkcell,

removing the assignment of the cell identifier assigned to said selected linkcell,

removing the link to the data table linked to said selected linkcell, and

deleting said data table linked to said selected linkcell;

 

otherwise, if said specified existing site is not the only site associated with said selected linkcell;

removing site data pertaining to said specified existing site from the data table linked to said selected linkcell and from said site data repository; and

(iii) removing said specified existing site from said site set.

20. The method of generating linkcells as claimed in claim 1, wherein said location space is defined by a plurality of location space boundary sections in a coordinate system.

21. The method of generating linkcells as claimed in claim 20, wherein said location space boundary sections of said location space are modified upon the occurrence of at least one of the following events:

(i) a new site is added to said site set, wherein said new site is located outside of said location space;

(ii) a specified existing site is removed from said site set, wherein said specified existing site is located closer to one of said location space boundary sections than any other site in said site set;

(iii) the location of a selected site in said site set is changed to a new location located outside of said location space; and

(iv) the location of a selected site in said site set is changed to a new location from a location that is closer to one of said location space boundary sections than the location of any other site in said site set.

72. A system for generating linkcells for use in 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, said system comprising:

(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 generating linkcells as claimed in claim 1.

73. The system for generating linkcells as claimed in claim 72, wherein said storage means comprises at least one of the following:

a memory, a database, a storage device.

22. 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 site data pertaining to sites in said site set is contained in a site data repository, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in said location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, and wherein each linkcell is linked to a data table, and wherein said method comprises the steps of:

(a) receiving a user-specified cell identifier as input;

(b) retrieving site data pertaining to at least one site associated with a linkcell to which said user-specified cell identifier has been assigned; and

(c) outputting site data retrieved in step (c) to a user.

23. 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 22, wherein site data retrieved in step (b) is retrieved from the data table linked to the linkcell to which said user-specified cell identifier has been assigned.

24. 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 22, wherein site data retrieved in step (b) is retrieved from said site data repository using links in the data table linked to the linkcell to which said user-specified cell identifier has been assigned.

25. 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 22, wherein said cell space is defined by a cell perimeter that comprises one or more cell boundary sections, and wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith.

26. 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 25, wherein the location of a site is defined by at least two coordinates.

27. 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 26, wherein a cell identifier is derived from said at least two coordinates, said at least two coordinates defining the location of a site associated with the linkcell to which said cell identifier has been assigned.

28. 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 27, wherein the cell identifier is a name composed of a plurality of components, wherein each component of said plurality of components is associated with a coordinate of said at least two coordinates.

29. 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 28, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval.

30. 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 28, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval and multiplied by a scaling factor.

31. 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 22, wherein site data pertaining to sites in said site set comprises a site identifier and a site category identifier.

32. 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 22, wherein site data pertaining to each site associated with said plurality of linkcells must comprise a user-specified site category identifier.

74. A system for 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, wherein site data pertaining to sites in said site set comprises a site identifier, said system comprising:

(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 22.

75. The system for generating linkcells as claimed in claim 74, wherein said storage means comprises at least one of the following:

a memory, a database, a storage device.

33. 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, wherein site data pertaining to sites in said site set is contained in a site data repository, wherein site data pertaining to sites in said site set comprises a site identifier, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in said location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, and wherein each linkcell is linked to a data table, and wherein said method comprises the steps of:

(a) receiving a user'"'"'s location;

(b) receiving a user request to retrieve site data pertaining to a specified number of sites closest to said user'"'"'s location;

(c) defining a core cell, wherein said core cell is in a searchable area defined in said location space;

(d) 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, such that the following substeps are performed each time said cursor cell is positioned at a linkcell;

(1) identifying sites associated with that linkcell, and

(2) for each site identified in substep (1), storing the site identifier therefor and the distance between the user'"'"'s location and the identified site in a result table;

(e) 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 pre-specified number of sites first-identified in step (d);

(f) identifying sites associated with a subset of said any additional linkcells;

(g) for each site associated with a subset of said any additional linkcells, storing the site identifier therefor and the distance between the user'"'"'s location and said site in a result table;

(h) determining the specified number of sites closest to said user'"'"'s location from the distances stored in said result table;

(i) retrieving site data pertaining to the specified number of sites closest to said user'"'"'s location determined in step (h); and

(j) outputting site data retrieved in step (i) to a user.

34. 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 33, wherein in step (d), said cursor cell traverses a path of cells in one of the following manners:

in a substantially outward-spiraling clockwise direction starting with said core cell;

in a substantially outward-spiraling counterclockwise direction starting with said core cell;

in a predefined manner starting with said core cell.

35. 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 33, wherein in step (d), cells of said path must be located in said searchable area defined in said location space.

36. 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 33, wherein said core cell is defined in step (c) as the cell containing said user'"'"'s location, unless said user'"'"'s location is outside said searchable area, in which case said core cell is defined as the cell in said searchable area that is closest to said user'"'"'s location.

37. 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 33, wherein site data retrieved in step (i) is retrieved from data tables linked to the linkcells that are associated with the specified number of sites closest to said user'"'"'s location determined in step (h).

38. 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 33, wherein site data retrieved in step (i) is retrieved from said site data repository using links in the data tables linked to the linkcells that are associated with the specified number of sites closest to said user'"'"'s location determined in step (h).

39. 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 33, wherein said cell space is defined by a cell perimeter that comprises one or more cell boundary sections, and wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith.

40. 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 39, wherein the location of a site is defined by at least two coordinates.

41. 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 40, wherein a cell identifier is derived from said at least two coordinates, said at least two coordinates defining the location of a site of the sites associated with the linkcell to which said cell identifier has been assigned.

42. 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 41, wherein the cell identifier is a name composed of a plurality of components, wherein each component of said plurality of components is associated with a coordinate of said at least two coordinates.

43. 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 42, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval.

44. 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 43, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval and multiplied by a scaling factor.

45. 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 33, wherein any site identified in steps (d) and (f) must have site data pertaining thereto that comprises a user-specified site category identifier.

76. A system for 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, wherein site data pertaining to sites in said site set comprises a site identifier, said system comprising:

(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 33.

77. The system for generating linkcells as claimed in claim 76, wherein said storage means comprises at least one of the following:

a memory, a database, a storage device.

46. 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, wherein site data pertaining to sites in said site set is contained in a site data repository, wherein site data pertaining to sites in said site set comprises a site identifier, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in said location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, and wherein each linkcell is linked to a data table, and wherein said method comprises the steps of:

(a) receiving a user'"'"'s location;

(b) receiving a user request to retrieve site data pertaining to sites located within a specified distance of said user'"'"'s location;

(c) defining a core cell, wherein said core cell is in a searchable area defined in said location space;

(d) 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 an area covering all points in said searchable area that are within said specified distance of said user'"'"'s location, such that the following substeps are performed each time when said cursor cell is positioned at a linkcell;

(1) identifying sites associated with that linkcell, and

(2) for each site identified in substep (1), storing the site identifier therefor and the distance between the user'"'"'s location and the identified site in a result table;

(e) determining the sites within a specified distance to said user'"'"'s location from the distances stored in said result table;

(f) retrieving site data pertaining to the sites within a specified distance to said user'"'"'s location determined in step (e); and

(g) outputting site data retrieved in step (f) to a user.

47. 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 46, wherein in step (d), said cursor cell traverses a path of cells in one of the following manners:

in a substantially outward-spiraling clockwise direction starting with said core cell;

in a substantially outward-spiraling counterclockwise direction starting with said core cell;

in a predefined manner starting with said core cell.

48. 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 46, wherein in step (d), cells of said path must be located in said searchable area defined in said location space.

49. 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 46, wherein said core cell is defined in step (c) as the cell containing said user'"'"'s location, unless said user'"'"'s location is outside said searchable area, in which case said core cell is defined as the cell in said searchable area that is closest to said user'"'"'s location.

50. 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 46, wherein site data retrieved in step (f)is retrieved from the data tables linked to the linkcells that are associated with sites within a user-specified distance to said user'"'"'s location determined in step (e).

51. 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 46, wherein site data retrieved in step (f) is retrieved from said site data repository using links in the data tables that are linked to the linkcells that are associated with sites within a user-specified distance to said user'"'"'s location determined in step (e).

52. 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 46, wherein said cell space is defined by a cell perimeter that comprises one or more cell boundary sections, and wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith.

53. 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 52, wherein the location of a site is defined by at least two coordinates.

54. 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 53, wherein a cell identifier is derived from said at least two coordinates, said at least two coordinates defining the location of a site of the sites associated with the linkcell to which said cell identifier has been assigned.

55. 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 54, wherein the cell identifier is a name composed of a plurality of components, wherein each component of said plurality of components is associated with a coordinate of said at least two coordinates.

56. 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 55, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval.

57. 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 56, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval and multiplied by a scaling factor.

58. 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 46, wherein any site identified in step (d) must have site data pertaining thereto that comprises a user-specified site category identifier.

78. A system for 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, wherein site data pertaining to sites in said site set comprises a site identifier, said system comprising:

(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 46.

79. The system for generating linkcells as claimed in claim 78, wherein said storage means comprises at least one of the following:

a memory, a database, a storage device.

59. A linkcell for use in 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 site data pertaining to sites in said site set is contained in a site data repository, and wherein said linkcell comprises:

(a) a cell perimeter that comprises one or more cell boundary sections, wherein said one or more cell boundary sections define a cell space for the linkcell within said location space, wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith;

(b) a cell identifier; and

(c) a link to a data table;

wherein at least one site of said site set is associated with said linkcell, and wherein site data pertaining to said at least one site is stored in said data table.

60. The linkcell as claimed in claim 59, wherein each site in said site set is associated with exactly one linkcell.

61. The linkcell as claimed in claim 59, wherein a site in said site set is to be associated with a specific linkcell only if said site is located within the cell space defined for said specific linkcell.

62. The linkcell as claimed in claim 59, wherein each of said one or more cell boundary sections is associated with the same predefined coordinate interval.

63. The linkcell as claimed in claim 59, wherein the location of each of said at least one site is defined by at least two coordinates.

64. The linkcell as claimed in claim 63, wherein the cell identifier is derived from said at least two coordinates.

65. The linkcell as claimed in claim 63, wherein said cell identifier is assigned to said data table.

66. The linkcell as claimed in claim 64, wherein the cell identifier is a name that composed of a plurality of components, wherein each component of said plurality of components is associated with a coordinate of said at least two coordinates.

67. The linkcell as claimed in claim 66, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval.

68. The linkcell as claimed in claim 66, wherein each component is equal to the value of the coordinate associated therewith truncated to a nearest predefined coordinate interval and multiplied by a scaling factor.

69. The linkcell as claimed in claim 59, wherein site data pertaining to each site in said site set comprises a site identifier and a site category identifier.

70. The linkcell as claimed in claim 60, wherein site data pertaining to each site associated with said linkcell must comprise a user-specified site category identifier.

71. The linkcell as claimed in claim 59, wherein the storing of site data in a data table is effected by saving one or more links to site data contained in said site data repository in said data table.