Method for storing map data in a database using space filling curves and a method of searching the database to find objects in a given area and to find objects nearest to a location
First Claim
1. A storage device for storing data for access by an application program which is executable by a processor, the storage device comprising:
- a database stored in the storage device for use by the application program to identify objects located in an area of a map plane which is divided into segments, the database including;
a main table including rows with each row storing data identifying one of the objects, and an object key assigned by a space filling curve to one of the segments which is intersected by the area of the object identified in the respective row; and
a secondary table including rows with each row storing an object key corresponding to one of the object keys stored in the main table and spatial keys assigned by the space filling curve to segments which are intersected by the area of the object stored in the row of the main table with the corresponding object key, wherein the spatial keys in each row identify only one range of sequential spatial keys assigned by the space filling curve to segments which are intersected by the area of the object identified by the object key of the row, and wherein a plurality of the rows of the secondary table have the same object key identifying the area of a single one of the objects.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for storing map data in a database and a method of searching the database to find objects in a given area and to find objects nearest to a location. To generate the map data, a map plane is divided into a number of squares and the squares are numbered with spatial key numbers according to a space filling curve. Objects identifying places such as restaurants or hotels are placed in a main table of the database along with one of the spatial keys (object keys) intersecting an area of the map occupied by the object. A secondary table of the database is then created with one column including object keys corresponding to the main table, and other columns identifying ranges of spatial keys for objects identified by the object keys. To search the database to find objects in a given area, ranges of spatial keys are calculated for the given area and compared with ranges in the secondary table to identify object keys. The object keys identified are then used to obtain the desired objects from the main table.
177 Citations
14 Claims
-
1. A storage device for storing data for access by an application program which is executable by a processor, the storage device comprising:
a database stored in the storage device for use by the application program to identify objects located in an area of a map plane which is divided into segments, the database including; a main table including rows with each row storing data identifying one of the objects, and an object key assigned by a space filling curve to one of the segments which is intersected by the area of the object identified in the respective row; and a secondary table including rows with each row storing an object key corresponding to one of the object keys stored in the main table and spatial keys assigned by the space filling curve to segments which are intersected by the area of the object stored in the row of the main table with the corresponding object key, wherein the spatial keys in each row identify only one range of sequential spatial keys assigned by the space filling curve to segments which are intersected by the area of the object identified by the object key of the row, and wherein a plurality of the rows of the secondary table have the same object key identifying the area of a single one of the objects. - View Dependent Claims (2)
-
3. A storage device for storing data for access by an application program which is executable by a processor, the storage device comprising:
a database stored in the storage device for use by the application program to identify objects located in an area of a map plane which is divided into segments, the database including; a main table including rows with each row storing data identifying one of the objects, and an object key assigned by a space filling curve to one of the segments which is intersected by the area of the object identified in the respective row; and a secondary table including rows with each row storing an object key corresponding to one of the object keys stored in the main table and spatial keys assigned by the space filling curve to segments which are intersected by the area of the object stored in the row of the main table with the corresponding object key, wherein the spatial keys included in each row of the secondary table include a beginning spatial key and an ending spatial key from a range of sequential spatial keys assigned by the space filling curve to segments which are intersected by the area of the object identified by the object key of the row. - View Dependent Claims (4)
-
5. A method utilized by a computer to locate a desired number of objects in an area of a map plane nearest a particular location on the map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
(a) defining a circular search area having an initial radius; (b) calculating one or more search area ranges of the spatial keys identifying segments of an area of the map plane intersected by the circular search area; (c) selecting a given one of the search area ranges from the circular search area; (d) comparing the given search area range with ranges of spatial keys intersected by areas of objects located on the map to identify one or more particular objects having a range of spatial keys intersecting with the given search area range; (e) determining if a number of the particular objects identified is greater than or equal to the desired number of objects and proceeding to step (f) if not, and proceeding to step (m) if so; (f) determining if all search area ranges in the circular search area have been compared in step (d) and proceeding to step (g) if not and proceeding to step (h) if so; (g) selecting one of the search area ranges from the circular search area which has not been compared in step (d) as the given search area range and proceeding to step (d); (h) redefining the circular search area to have a greater radius and proceeding to step (c); (i) comparing the given search area range with ranges of spatial keys intersected by areas of objects located on the map to enable identifying one or more given objects having a range of spatial keys intersecting with the given search area range; (j) determining if a number of the given objects identified is greater than or equal to the desired number of objects and proceeding to step (k) if not, and proceeding to step (m) if so; (k) determining if all the search area ranges in the circular search area have been compared in step (i) and (d) and if so ending the method with the given objects identifying the desired number of objects, and if not proceeding to step (l); (l) selecting one of the search area ranges from the circular search area which has not been compared in step (i) or step (d) as the given search area range and proceeding to step (i); (m) retaining a number of the given objects equal to the desired number of objects which are located nearest in distance to the particular location; (n) redefining the circular search area to have a radius equal to a distance of a farthest one of the given objects from the particular location; (o) calculating one or more search area ranges of the spatial keys identifying segments of an area of the map plane intersected by the circular search area; and (p) selecting one of the search area ranges from the circular search area which has not been compared in step (i or (d) as the given search area range and proceeding to step (i).
-
-
6. A method utilized by a computer to locate a desired number of objects in an area of a map plane nearest a particular location on the map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
(a) defining a search area having an initial radius; (b) calculating search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; (c) comparing the search ranges with ranges of spatial keys intersected by areas of the objects located on the map to identify particular ones of the objects in the search area; (d) determining if a given number of particular objects are identified which is greater than, equal to, or less than the desired number of objects, and proceeding to step (c) if the given number is less than the desired number, proceeding to step (e) if the given number is greater than the desired number, and retaining the particular objects as the desired objects when the given number equals the desired number; (e) determining a distance of each of the particular objects from the particular location; and (f) retaining a number of the particular objects equal to the desired number of objects which are located nearest in distance to the particular location. - View Dependent Claims (7, 8, 9)
-
-
10. A method utilized by a computer to locate a given object in an area of a map plane nearest a particular location on the map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
(a) defining a search area having an initial radius; (b) calculating search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; (c) comparing the search ranges with ranges of spatial keys intersected by areas of the objects located on the map to identify one or more particular objects in the search area; (d) determining if one or more of the particular objects is identified and proceeding to step (c) if not, proceeding to step (e) if more than one particular object is identified, and retaining the particular object as the given object when only one of the particular objects is identified; (e) determining a distance of each of the particular objects from the particular location; and (f) retaining one of the particular objects which is located nearest in distance to the particular location as the given object.
-
-
11. A method utilized by a computer to locate given objects in an area of a map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
defining a search area; calculating search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; and comparing the search ranges with only one given spatial key in each range of spatial keys identified by at least one spatial key stored in a database identifying areas of the map occupied by objects to identify the given objects within the search area. - View Dependent Claims (12)
-
-
13. A method utilized by a computer to locate a desired number of objects in an area of a map plane nearest a particular location on the map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
(a) defining a search area having an initial radius; (b) calculating search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; (c) selecting a given one of the search ranges from the search area; (d) comparing the given search range with ranges of spatial keys intersected by areas of objects located on the map to identify particular objects in the given search range; (e) determining if a given number of the particular objects are identified which is greater than, equal to, or less than the desired number of objects, and proceeding to step (f) if the given number is less than the desired number, proceeding to step (i) if the given number is greater than the desired number, and retaining the particular objects as the desired objects when the given number equals the desired number; (f) determining if all search ranges in the search area have been compared in step (d) and proceeding to step (g) if not and proceeding to step (h) if so; (g) selecting one of the search ranges from the search area which has not been compared in step (d) as the given search range and proceeding to step (d); and (h) redefining the search area to have a greater radius and proceeding to step (c); (i) retaining a number of the particular objects equal in number to the desired number of objects which are located nearest in distance to the particular location; (j) defining the search area to have a radius equal to a distance of a farthest one of the retained particular objects from the particular location; (k) calculating one or more search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; and (l) selecting one of the search ranges from the search area which has not been compared in step (d) as the given search range and proceeding to step (d).
-
-
14. A method utilized by a computer to locate a given object in an area of a map plane nearest a particular location on the map plane, the map plane being divided into segments with the segments being identified by spatial key numbers assigned using a space filling curve, the method comprising the steps of:
-
(a) defining a search area having an initial radius; (b) calculating search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; (c) selecting a given one of the search ranges from the search area; (d) comparing the given search range with ranges of spatial keys intersected areas of objects located on the map to identify particular objects in the given search range; (e) determining if one or more of the particular objects is identified and proceeding to step (f) if not, proceeding to step (i) if more than one particular object is identified, and retaining the particular object identified as the given object when only one of the particular objects is identified; (f) determining if all search ranges in the search area have been compared in step (d) and proceeding to step (g) if not and proceeding to step (h) if so; (g) selecting one of the search ranges from the search area which has not been compared in step (d) as the given search range and proceeding to step (d); (h) redefining the search area to have a greater radius and proceeding to step (c); (i) retaining one of the particular objects which is located nearest in distance to the particular location; (j) defining the search area to have a radius equal to a distance of the retained particular object from the particular location; (k) calculating one or more search ranges of the spatial keys identifying segments of an area of the map plane intersected by the search area; and (l) selecting one of the search ranges from the search area which has not been compared in step (d) as the given search range and proceeding to step (d).
-
Specification