Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-10-29
2004-03-02
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06700574
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to data indexing and retrieval. More specifically, the present invention relates to a method of indexing spatial object data and a method of searching the indexed data.
2. Problems in the Art
A map is composed of a large volume of geographical features, such as roads, rivers, parks, geo-political regions, etc. A vector map is a digitized form of a descriptive map where all geographical features are digitized and stored in some digitally retrievable media. A vector map or database containing digitized map data can be purchased from Navigation Technologies Corp. in Rosemont, Ill. or Etak, Inc. in Menlo Park, Calif. A digitized feature may be recorded with its spatial information in coordinates (longitude and latitude) in addition to its other non-spatial attributes, e.g., the feature's name. The digitization of a map creates a large quantity of data. Therefore, to search through all this data requires a substantial amount of CPU power and processing time. To search through this spatial object data more efficiently, it would be desirable to index the data to allow for a search through the index.
Spatial object data is not only capable of characterizing two-dimensional space, such as in vector maps, or three dimensional space, such as in planetary or galactic maps, but also may characterize other multi-dimensional space, comprising four or more dimensions. A defined space is a space, of desired dimensions, bounded as indicated by the search to be performed or the data to be stored or indexed.
There are two common methods for indexing spatial object data. The first method of indexing data is by storing it in an indexed array (or list). A search through an indexed array to find a desired object requires all of the objects within the array to be searched, requiring a large amount of CPU time.
The second method commonly used to index spatial object data is to impose a grid system upon the space that contains spatial objects, wherein all grids are of the same size. In this gridding method, it is difficult to determine the proper grid size. If the grids are too large, they will encompass many objects, not saving much search time over the indexed array method. If the grids are too small, then more computer memory will be needed to support the grid structure and there will be more spatial objects that cross boundaries. The prior art gridding method does not give any consideration to the variation in object density within the space of interest. For example, a prior art grid cell that covered a rural area may contain many fewer objects than the same grid cell that encompasses an urban area. There is a need in the art for a method of indexing data which allows the indexed data to be searched in a faster manner.
Therefore, a primary objective of the present invention is to provide a method of indexing spatial object data which overcomes problems and deficiencies in the art.
A further object of the present invention is a method that divides space as characterized by the data based on the clustering of spatial object distribution.
A further object of the present invention is a method that divides space based on a hierarchy of quadtrees.
A further object of the present invention is to provide a search method which may be used with the spatial object indexing method of the present invention.
These, as well as other objects, advantages and features of the present invention, will be apparent from the following detailed specification and claims in conjunction with the accompanying drawings.
SUMMARY OF INVENTION
The present invention includes a method of indexing spatial object data comprising utilizing spatial object data which characterizes objects in a defined space, and dividing the space based on the clustering of the objects within the space.
The present invention can also include a method of searching spatial object data that includes utilizing spatial object data that has been gridded based upon clustering of the spatial objects. The grids are then recursively checked to see if they cover a range of interest. If the grids overlap the range of interest, objects within the grids are checked to see if they satisfy a search criterion.
The present invention can also include a computer readable medium containing computer executable instructions. The instructions cause the computer to divide a space, as characterized by data, containing spatial objects, based on clustering of the objects within the space.
REFERENCES:
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 6081803 (2000-06-01), Ashby et al.
patent: 0838663 (1998-04-01), None
patent: 0280795 (1998-09-01), None
Foley (Computer Graphics: Principles and Practice Second Edition in C: section 12.6.3: Octrees—p. 552).*
International Search Report, dated Mar. 10, 2003.
Jankus Almis R.
Siemens Transportation Systems, Inc.
LandOfFree
Spatial data object indexing engine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spatial data object indexing engine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial data object indexing engine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240744