System and method for packing spatial data in an R-tree

• US 6,252,605 B1
• Filed: 08/01/1997
• Issued: 06/26/2001
• Est. Priority Date: 08/01/1997
• Status: Expired due to Term

• Current Assignee: Garmin Corporation (Garmin Limited)
• Original Assignee: Garmin Corporation (Garmin Limited)
• Inventors: Beesley, Darin J., Walters, Thomas H., Robinson, Stephen C.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/905,297
• Time in Patent Office: 1,425 Days
• Field of Search: 345/441, 345/442, 345/440, 345/433, 345/419, 345/117, 345/121
• US Class Current: 345/441
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G06F 16/9027 Trees

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.

Claims

1. A method for packing spatial data features into nodes of an R-Tree, said method comprising:

(a) providing a buffer having a plurality of storage locations;

(b) calculating a minimum bounding rectangle of each said spatial data feature to be packed;

(c) sorting said spatial data features to be packed into a table of records;

(d) until a predetermined condition exists, individually selecting records from said table of records and temporarily storing the spatial data associated with each said selected record in one of said storage locations of said buffer;

(e) upon an occurrence of said predetermined condition, splitting the data associated with said selected records into first and second portions, and temporarily storing the spatial data associated with said first portion of said selected records in one storage location of said buffer and temporarily storing the spatial data associated with said second portion of said selected records in another one of said storage locations of said buffer;

(f) repeating steps (d) and (e) until no storage locations of said buffer remain available for storing data;

(g) then removing from said buffer the spatial data in a determined one of said buffer locations, said removed data being committed to the R-Tree being packed.

2. The method as set forth in claim 1, wherein said step of sorting said spatial data features to be packed into a table of records comprises:

applying fractal geometry to the said spatial data to be packed.

3. The method as set forth in claim 2, wherein said step of applying fractal geometry to the said spatial data to be packed comprises:

applying the Hilbert Space-Filling Curve to a selected location of each said calculated minimum bounding rectangle.

4. The method as set forth in claim 1 wherein, after an occurrence of said predetermined condition and after said splitting of the data selected records into first and second portions, the step of temporarily storing data associated with a next record, selected from said table, further comprises:

selecting a one of said buffer storage locations, already having spatial data stored therein, for storage of the data associated with said next selected records, said stored spatial data in each buffer storage location having a minimum bounding rectangle with a perimeter, said step of selecting one of said buffer storage locations comprising;

determining which said perimeter will increase the least upon addition of the data associated with said next selected record.

5. The method as set forth in claim 1 wherein, after an occurrence of said predetermined condition and after said splitting of the data of selected records into first and second portions, the step of temporarily storing data associated with a next record, selected from said table, further comprises;

selecting a one of said buffer storage locations, already having spatial data stored therein, for storage of the data associated with said next selected record, said stored spatial data in each buffer storage location having a minimum bounding rectangle with an area, said step of selecting one of said buffer storage locations comprising;

determining which said area will increase the least upon addition of the data associated with said next selected record.

6. The method as set forth in claim 1 wherein, after an occurrence of said predetermined condition and after said splitting of the data of selected records into first and second portions, the step of temporarily storing data associated with a next record, selected from said table, further comprises:

selecting a one of said buffer storage locations, already having spatial data stored therein, for storage of the data associated with said next selected record, said stored spatial data in each buffer storage location having a minimum bounding rectangle, said step of selecting one of said buffer storage locations comprising;

determining which said storage location will have the least overlap of minimum bounding rectangles upon inclusion of the data associated with the next selected record.

7. The method as set forth in claim 1, wherein said step of splitting comprises:

applying a quadratic split to the data associated with the selected records.

8. The method as set forth in claim 1, wherein said step of splitting comprises:

determining when a preexisting condition exists, said preexisting condition being when an estimate of a data storage requirement for the data to be stored in one of said buffer storage locations exceeds a selected upper threshold.

9. The method as set forth in claim 1, wherein said step of splitting comprises:

determining when a preexisting condition exists, said preexisting condition being when the number of records associated with a buffer storage location exceed a selected upper threshold.

10. The method as set forth in claim 1, wherein said spatial data represents geography, wherein said step of splitting comprises:

determining when a preexisting condition exists, said preexisting condition being when the geography represented by the spatial data to be stored in one of said buffer storage locations exceeds a selected upper threshold.

11. The method as set forth in claim 1, wherein said spatial data represents geographic area, said step of removing comprising:

selecting that data, stored in one of said buffer storage locations, which most likely corresponds to a geographic area furthest from the geographic area corresponding to the data associated with a next record selected from said table.

12. The method as set forth in claim 11, said step of removing further comprising:

applying fractal geometry for selecting the data to be removed from said buffer.