System and method for packing spatial data in an R-tree
US6252605A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 1, 1997 |
| Grant date | Jun 26, 2001 |
| Priority date | — |
| Expiry date | Aug 1, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG01C21/3878
- WIPO fieldMeasurement
- WIPO sectorInstruments
Abstract
A system and method for constructing an R-Tree index structure, and packing spatial data in the structure to permit parameters of the R-Tree to be constructed to be selected, within provided ranges, by an operator of the system. The spatial data features to be packed into the R-Tree constructed, are sorted, according to fractal geometry, and placed in a table of records. Each record is individually selected from the table, and data associated with each record is temporarily stored in one of a plurality of buffer storage locations according to a plurality of packing algorithms. The data in a buffer storage location is split, into first and second groups of data, upon the occurrence of one of a plurality of predetermined conditions. Data is selectively removed from the buffer for placement in the R-Tree being packed, such that data representing nearby geographical areas is most optimally clustered together. A portable electronic device such as a navigational aid, has a processor, a display, an input, and a memory, all housed by a housing, wherein the memory has spatial data indexed by an R-Tree index embedded therein.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.