Method and system for forming and using geographic data

Details Method and system for forming and using geographic data Method and system for forming and using geographic data

1997-09-05

1999-09-14

Lintz, Paul R.

Data processing: database and file management or data structures

Database design

Data structure types

707104, 707 2, 701200, 701201, 701208, 701209, G06F 1730

Patent

active

059537221

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.

REFERENCES:
patent: 4630209 (1986-12-01), Saito et al.
patent: 4888698 (1989-12-01), Driessen et al.
patent: 4937572 (1990-06-01), Yamada et al.
patent: 5036471 (1991-07-01), Tamura et al.
patent: 5168452 (1992-12-01), Yamada et al.
patent: 5170353 (1992-12-01), Verstraete
patent: 5285391 (1994-02-01), Smith, Jr. et al.
patent: 5406493 (1995-04-01), Goto et al.
patent: 5592665 (1997-01-01), Lahaije
Matsuyama et al., "A File Organization for Geographic Information Systems Based on Spatial Proximity", Computer Vision, Graphics, and Image Processing, vol. 26, No. 3, Jun. 26, 1984, 0. 303-318.
Frosh, Randy, "A Method of Accessing Large Spatial Databases", Nov. 26-30, 1989, GIS/LIS '89 Conference, Orlando, Florida.
Samet, Hanan, "Strategies for Optimizing the Use of Redundancy in Spatial Databases", Chapter 2.4, The Design and Analysis of Spatial Data Structure, ISBN 0-201-50255-0; (before 1996).
Bentley, Jon L, "Multidimensional Binary Search Trees in Data Applications", IEEE Transactions on Software Engineering, vol. SE-5, No. 4, Jul. 1979, pp. 333-340.

Affiliated with

Also associated with

Rating

Method and system for forming and using geographic data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for forming and using geographic data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for forming and using geographic data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1520694