Parcelized geographic data medium with internal spatial indices and method and system for use and formation thereof
First Claim
1. A computer-implemented method for producing a database that represents geographic features in a geographic region comprising the steps of:
- separating a plurality of data entities that represent the geographic features into a plurality of parcels, wherein each parcel of said plurality of parcels contains a separate subset of said plurality of data entities, and wherein the subset of said plurality of data entities contained in each parcel represents the geographic features located in a separate one of a plurality of areas into which the geographic region is divided;
wherein an improvement comprises;
for each parcel of said plurality of parcels, dividing the area associated therewith into a plurality of sub-areas; and
storing a first index that identifies, for each of the data entities contained in the parcel, each of the sub-areas intersected by the geographic feature represented thereby, whereby each sub-area in which a geographic feature is located can be determined by using the first index.
6 Assignments
0 Petitions
Accused Products
Abstract
A navigable map database, stored on a computer-readable medium and used with a navigation application program, includes data which are spatially parcelized into a plurality of parcels. Associated with each of the plurality of parcels is a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area. Also associated with each of the parcels is a second index associating each of the data in the parcel with at least one of the sub-areas. Further disclosed is a method for producing a navigable map database which is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. Also further disclosed are a program and method for finding data in one or more parcels that match a spatial search criterion using a navigable map database that is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. The program and method use the first and second indices to identify which of the data in at least one of the plurality of parcels satisfy the spatial search criterion.
-
Citations
21 Claims
-
1. A computer-implemented method for producing a database that represents geographic features in a geographic region comprising the steps of:
-
separating a plurality of data entities that represent the geographic features into a plurality of parcels, wherein each parcel of said plurality of parcels contains a separate subset of said plurality of data entities, and wherein the subset of said plurality of data entities contained in each parcel represents the geographic features located in a separate one of a plurality of areas into which the geographic region is divided;
wherein an improvement comprises;
for each parcel of said plurality of parcels, dividing the area associated therewith into a plurality of sub-areas; and
storing a first index that identifies, for each of the data entities contained in the parcel, each of the sub-areas intersected by the geographic feature represented thereby, whereby each sub-area in which a geographic feature is located can be determined by using the first index. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer-implemented method of using a geographic database comprising the steps of:
-
accepting specification of a search area in a geographic region represented by the geographic database;
identifying a parcel of data in the geographic database, wherein the parcel contains data entities that represent geographic features encompassed within a first rectangular area located within the geographic region, wherein the first rectangular area intersects said search area;
wherein an improvement comprises;
using a first index associated with the parcel to identify which of a plurality of rectangular sub-areas into which the first rectangular area is divided intersect the search area; and
using a second index associated with the parcel to identify the data entities contained in the parcel that intersect each of the plurality of rectangular sub-areas identified as intersecting the search area, wherein in the case that the search area intersects more than one of said plurality of rectangular sub-areas and a geographic feature represented by a single data entity intersects each of said more than one of said plurality of rectangular sub-areas, the second index identifies said single data entity, whereby the data entities that represent the geographic features located within the search area are determined.
-
-
12. A computer-implemented method of using a geographic database to identify geographic features located within a search area, wherein the geographic database contains data entities that represent geographic features located in a geographic region, and wherein the geographic database is organized into parcels, each of which contains a subset of all the data entities in the geographic database, and wherein the subset of data entities in each parcel represent the geographic features encompassed within a separate respective one of a plurality of rectangular areas into which the geographic region is divided, wherein the method comprises the steps of:
-
(a) identifying each parcel that is associated with a rectangular area that intersects the search area;
wherein an improvement comprises;
(b) for each parcel identified in step (a), using a first index associated with the parcel to identify each rectangular sub-area formed of the rectangular area associated with the parcel that intersects the search area; and
(c) for each parcel identified in step (a), using a second index associated with the parcel to identify each of the data entities contained therein that represents a geographic feature that intersects each of the sub-areas identified in step (b), wherein in the case that the search area intersects more than one of said plurality of rectangular sub-areas and a geographic feature represented by a single data entity intersects each of said more than one of said plurality of rectangular sub-areas, the second index identifies said single data entity, whereby the data entities identified in step (c) represent geographic features located in the search area. - View Dependent Claims (13, 14, 15)
-
-
16. In a geographic database comprised of data records and stored on a computer-readable medium, wherein each data record represents a physical geographic feature in a geographic region,
wherein the data records are separated into a plurality of parcels, wherein each parcel contains a separate portion of the data records, such that the portion of data records contained in each parcel represents those geographic features encompassed together in a separate respective one of a plurality of areas formed by dividing the geographic region, wherein the improvement comprises: -
a plurality of index tables of a first type, each of which is associated with a separate one of said plurality of parcels and wherein each of said index tables of the first type comprises;
a separate reference to each data record in the parcel to which said index table is associated; and
a reference to at least one of a plurality of groupings of the plurality of data records in the parcel, wherein the plurality of groupings are based upon a division of the area associated with the parcel into a plurality of smaller sub-areas. - View Dependent Claims (17, 18, 19)
-
-
20. A computer usable medium having computer readable data structure means embodied thereon, wherein the computer readable data structure means is used for a database for geographic data comprised of data records that represent segments of roads located in a geographic region, said computer readable data structure comprising:
-
a plurality of parcels, each of which contains a separate portion of the data records, such that each parcel contains the data records that represent the segments of roads located in a separate one of a plurality of areas into which the geographic region is divided;
wherein an improvement comprises;
a plurality of first indexes, each of which is associated with a respective one of the plurality of parcels, wherein each first index defines a plurality of sub-areas formed of the area associated with the parcel associated therewith; and
a plurality of second indexes, each of which is associated with a respective one of the plurality of parcels, wherein each second index associates each of the data records in the parcel associated therewith to at least one of the plurality of sub-areas defined by the first index associated with the parcel, wherein in the case where a geographic feature represented by a single data entity intersects more than one of said plurality of rectangular sub-areas, the second index identifies said single data entity, whereby the computer readable data structure means identifies which of the data records represent segments of roads located in any specified sub-area of any specified area. - View Dependent Claims (21)
-
Specification