Method and system for forming and using geographic data
First Claim
1. A method of making a geographic database for a geographic region comprising:
- separating a plurality of data entities of a first type into a plurality of parcels wherein each parcel includes a subset of said plurality of data entities of said first type, and wherein the subset of said plurality of data entities of said first type in each parcel represents features in a geographic area encompassed within a separate rectangle of a plurality of rectangles which together encompass all the features in the entire geographic region represented by said plurality of data entities of said first type; and
assigning each of the plurality of data entities of said first type a data entity ID, such that all the data entities of said first type in each parcel have entity ID'"'"'s that are either greater than or less than all the data entity ID'"'"'s in all the other parcels containing data entities of said first type,wherein all of the rectangles encompassing features represented by data entities which are assigned data entity ID'"'"'s greater than the data entity ID'"'"'s in any one rectangle are located on the same side of either an east-west boundary of said one rectangle or a north-south boundary of said one rectangle.
5 Assignments
0 Petitions
Accused Products
Abstract
A system and method for making and using a geographic database. The geographic database represents a geographic region and is used with a navigation application program. The geographic database includes a plurality of data entities each of which represents a physical feature in the geographic region. The plurality of data entities are separated into a plurality of parcels each of which contains a grouping of data entities that represent features in the geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the features in the entire geographic region represented by all of the plurality of data entities. Each of the plurality of data entities has a data entity ID. The data entities contained in each of the plurality of parcels define an associated range of data entity ID'"'"'s associated with their respective parcel such that the range of data entity ID'"'"'s associated with each parcel does not overlap the range of data entity ID'"'"'s associated with any another of the plurality of parcels. Associated with the geographic database is a searchable kd-tree structure whose nodes represent divisions of the geographic region into the rectangles from which the parcels are formed. The kd-tree structure permits spatial searching for a parcel based upon geographic coordinates. The kd-tree also includes data at certain of its nodes that identify the ranges of data entity ID'"'"'s included in parcels formed from rectangles resulting from the divisions thereby enabling the kd-tree to be used as a binary tree for performing searches using the data entity ID'"'"'s. Navigation application program functions can search for data by utilizing the kd-tree to conduct either a spatial search using geographic coordinates or a binary search using a data entity ID.
241 Citations
23 Claims
-
1. A method of making a geographic database for a geographic region comprising:
-
separating a plurality of data entities of a first type into a plurality of parcels wherein each parcel includes a subset of said plurality of data entities of said first type, and wherein the subset of said plurality of data entities of said first type in each parcel represents features in a geographic area encompassed within a separate rectangle of a plurality of rectangles which together encompass all the features in the entire geographic region represented by said plurality of data entities of said first type; and assigning each of the plurality of data entities of said first type a data entity ID, such that all the data entities of said first type in each parcel have entity ID'"'"'s that are either greater than or less than all the data entity ID'"'"'s in all the other parcels containing data entities of said first type, wherein all of the rectangles encompassing features represented by data entities which are assigned data entity ID'"'"'s greater than the data entity ID'"'"'s in any one rectangle are located on the same side of either an east-west boundary of said one rectangle or a north-south boundary of said one rectangle. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A geographic database stored on a storage medium, said geographic database for use with a navigation application program and representing a geographic region, said geographic database comprising:
-
a plurality of data entities each of which represents a physical feature in the geographic region, wherein said plurality of data entities are separated into a plurality of parcels each of which contains data entities that represent features in a geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in the entire geographic region; wherein each of said plurality of data entities has a data entity ID; wherein each of said plurality of parcels contains a disjoint range of data entity ID'"'"'s associated with data entities in their respective parcel; and wherein each of the rectangles encompassing features represented by data entities which are assigned data entity ID'"'"'s greater than the data entity ID'"'"'s in any one rectangle are located on the same side of either an east-west boundary of said one rectangle or a north-south boundary of said at least rectangle. - View Dependent Claims (15)
-
-
16. A search tree for parcels of geographic data embodied on a computer readable medium, wherein said geographic data corresponds to a geographic region wherein each parcel includes data represented by a range of entity identifications, comprising:
-
kd-tree structure having a root node, internal nodes, and leaf nodes, wherein each node except for said leaf nodes thereof correspond to a division in said geographic region; and wherein each node of the kd-tree structure that represents a division in said geographic region resulting in formation of an area that encompasses features represented by data corresponding to a parcel also includes information identifying a range of data entity identifications included in the parcel. - View Dependent Claims (17)
-
-
18. A geographic database stored on a computer-readable medium comprising:
-
a plurality of data entities representing physical features in a geographic region, wherein each of said plurality of data entities represents a feature in said geographic region and each of said plurality of data entities has associated therewith attributes identifying a position of the feature represented thereby; wherein said plurality of data entities are arranged into a plurality of parcels wherein each parcel includes a portion of said plurality of data entities and each parcel corresponds to an amount of data that can be read in a disk access of said medium; and wherein each of said plurality of data entities has an associated entity identification, such that the data entities in each parcel define a range of data entity identifications associated with the parcel; and
wherein the range of entity identifications in each of said parcels does not overlap with the range of entity identifications in any other of said parcels.
-
-
19. A search tree for a plurality of parcels of geographic data embodied on a computer readable medium, wherein said geographic data corresponds to a geographic region wherein each parcel of said plurality of parcels includes data represented by a range of entity identifications, the search tree comprising:
-
kd-tree having a root nodes, internal nodes and leaf nodes, wherein each kd-tree node except for said leaf nodes thereof correspond to a division in said geographic region; and a binary tree for said entity identifications, said binary tree having a plurality of binary tree nodes, wherein each binary tree node represents a separate range of entity identifications; and wherein said binary tree is embedded within said kd-tree such that each binary tree node corresponds in position to the kd-tree node that represents the division that forms the parcel containing the range of entity identifications included in said parcel.
-
-
20. A method of searching for geographic data in a geographic database using a computer program, wherein the computer program performs the steps comprising of:
-
using a data entity ID to search nodes of a kd-tree for data indicating ranges of data entity ID'"'"'s associated with divisions represented by nodes of said kd-tree; and obtaining data identifying a location in said geographic database at which desired geographic data are located by reference to one of said kd-tree nodes representing a division from which a parcel containing the data represented by said data entity ID was formed.
-
-
21. A geographic database structure embodied on a computer-readable medium, wherein geographic data are organized in a kd-tree searchable structure, and wherein each node of said kd-tree structure includes an entity identification indicative of a division of entities identifications so that said kd-tree can be used as a binary search tree using said entity identification divisions.
-
22. A method of making a geographic database for a geographic region comprising:
-
separating a plurality of data entities into a plurality of parcels wherein each of said data entities represents a physical feature in the geographic region and each parcel includes a subset of said plurality of data entities, and wherein the data entities in each parcel represent features in a geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in the entire geographic region, assigning each of the plurality of data entities a data entity ID, such that all the data entities in each parcel have data entity ID'"'"'s that are either greater than or less than all the data entity ID'"'"'s in all the other parcels, and wherein within each parcel, data entity ID'"'"'s are assigned so that at least one straight line division of the rectangular area encompassing the data entities in said parcel can be made which divides said data entities into two further rectangular areas which encompass data entities having data entity ID'"'"'s which do not overlap each other.
-
-
23. A method of making a geographic database for a geographic region comprising:
-
separating a plurality of data entities of a first type into a plurality of parcels wherein each parcel includes a subset of said plurality of data entities of said first type, and wherein the subset of said plurality of data entities of said first type in each parcel represent features in a geographic area encompassed within a separate one of a plurality of rectangles each of which is formed by a set of rectangle boundary segments, such that all the features in the entire geographic region represented by said plurality of data entities of said first type are encompassed by said plurality of rectangles; and assigning each of the plurality of data entities of said first type a data entity ID, such that there exists a first set of horizontal and vertical line segments such that each of said rectangle boundary segments is contained in one of a first set of horizontal and vertical line segments, and further wherein all data entities of said first type which represent features due north of a horizontal line segment of said first set have data entity ID'"'"'s which are greater than those of any data entities of said first type which represent features due south of said horizontal line segment of said first set and all data entities of said first type which represent features due east of a vertical line segment of said first set have data entity ID'"'"'s which are greater that those of any data entities of said first type which represent features due west of said vertical line segment of said first set, wherein a feature is due north of a horizontal line segment of the first set if the latitude of the feature is greater than the common latitude of the end points of the horizontal line segment of the first set and the longitude of the feature lies between the longitudes of the end points of the horizontal line segment of the first set, wherein a feature is due south of a horizontal line segment of the first set if the latitude of the feature is less than the common latitude of the end points of the horizontal lines segment of the first set and the longitude of the feature lies between the longitudes of the end points of the horizontal line segment of the first set, wherein a feature is due west of a vertical line segment of the first set if the longitude of the feature is greater than the common longitude of the end points of the vertical line segment of the first set and the latitude of the feature lies between the latitudes of the end points of the vertical line segment of the first set, and wherein a feature is due east of a vertical line segment of the first set if the longitude of the feature is less than the common longitude of the end points of the vertical line segment of the first set and the latitude of the feature lies between the longitudes of the end points of the vertical line segment of the first set.
-
Specification