PARCELIZED GEOGRAPHIC DATA MEDIUM WITH INTERNAL SPATIAL INDICES AND METHOD AND SYSTEM FOR USE AND FORMATION THEREOF
First Claim
1. A method for producing a database that represents a road network in a geographic region for comprising the steps of:
- spatially parcelizing a plurality of data entities into a plurality of parcels wherein each parcel said plurality of parcels contains a separate subset of said plurality of data entities;
with respect to each of said parcels, determining a plurality of sub-areas each of which encompasses some of the geographic features represented by the data entities contained in said parcel; and
storing a first index identifying with respect to each of the data entities contained in said parcel each of said sub-areas intersected by the geographic feature represented thereby.
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.
89 Citations
22 Claims
-
1. A method for producing a database that represents a road network in a geographic region for comprising the steps of:
-
spatially parcelizing a plurality of data entities into a plurality of parcels wherein each parcel said plurality of parcels contains a separate subset of said plurality of data entities;
with respect to each of said parcels, determining a plurality of sub-areas each of which encompasses some of the geographic features represented by the data entities contained in said parcel; and
storing a first index identifying with respect to each of the data entities contained in said parcel each of said sub-areas intersected by the geographic feature represented thereby. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method of using a navigable map database with a navigation system comprising the steps of:
-
identifying a search area in a geographic region;
identifying at least one parcel of data in the navigable map database, wherein the at least one parcel of data contains data entities that represent features encompassed within a first rectangular area within the geographic region, wherein the first rectangular area intersects said search area;
using a first index associated with said at least one parcel of data to identify each of a plurality of sub-rectangles of said first rectangular area that intersect said search area; and
using a second index associated with said at least one parcel of data to identify which of said data entities contained in said parcel intersect each of the plurality of sub-rectangles identified by using said first index.
-
-
12. A method of using a navigable map database with a navigation system, wherein the navigable map database is comprised of a plurality of parcels, wherein each of said parcel contains data entities that represent features encompassed within a separate rectangular area within a geographic region, wherein the rectangular area associated with each parcel is distinct from the rectangular area associated with each other parcel of the plurality of parcels, comprising the steps of:
-
identifying a search area in a geographic region;
identifying each of said parcels whose data entities are encompassed by a rectangular area that intersects said search area;
using a first index associated with each of said parcels to identify each sub-rectangle of a plural of sub-rectangles that intersects said search area, wherein said plurality of sub-rectangles are of the rectangular area that encompasses the features represented by the data entities of the parcel; and
using a second index associated with each of said parcels to identify which of said data entities contained in each of said parcels intersects each sub-rectangle of the plurality of sub-rectangles identified by using the first index associated with the parcel. - View Dependent Claims (13, 14, 15)
-
-
16. In a map database for use in a navigation system, wherein the map database is comprised of a plurality of data records each of which represents a physical geographic feature in a geographic region,
wherein the data records are spatially parcelized into a plurality of parcels, wherein each parcel plurality of said parcels comprises a separate portion of said plurality of data records, wherein the portion of said plurality of data records in each parcel represents geographic features encompassed together in an area of said geographic region and wherein the area that encompasses the geographic features represented by one parcel is separate from the areas that encompass the geographic features represented by the rest of the parcels of a given level and of a given type, 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, 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 organize the plurality of data records in the parcel spatially. - View Dependent Claims (17)
-
-
18. A geographic database stored on a computer readable 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 a subset of said plurality of data entities wherein the subset of data entities in each parcel represent geographic features in said geographic region encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in all the parcels in the entire geographic region;
wherein each of said plurality of parcels is associated with an index, wherein the index associated with each parcel relates each of the data entities in the subset of said plurality of data entities associated with said parcel with at least one grouping of a plurality of groupings of said subset of data entities associated with said parcel. - View Dependent Claims (19, 20, 21)
-
-
22. A computer usable medium having computer readable program data structure means embodied therein for use in a map database, wherein the map database includes a plurality of data records representing segments of roads in a geographic region, said computer readable program data structure means adapted to provide for identifying which of said plurality of data records included in each of a plurality of parcels of spatially parcelized data meets a spatial search criterion, said computer readable program data structure comprising:
-
a plurality of first indices, each of which is associated with a respective one of each of said plurality of parcels, wherein each of said plurality of first indices determines a plurality of sub-areas formed of an area that encompasses the geographic features represent by the data records in the respective parcel; and
a plurality of second indices, each of which is associated with a respective one of each of said plurality of parcels, wherein each of said plurality of second indices associates each of the plurality of data records in its respective parcel to at least one of the plurality of sub-areas determined by the one of the plurality of first indices associated with the respective parcel.
-
Specification