Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1997-08-01
2001-06-26
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06252605
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is generally directed to a method and system for packing spatial data, such as cartographic data, into a database. More particularly, the invention relates to a method and system for packing cartographic data in a range-tree (R-Tree) to achieve flexible and efficient data storage. The invention further relates to a portable electronic device having cartographic data, and an associated R-Tree index structure, embedded therein.
2. Description of the Related Art
Many electronic products, such as mapping systems, computer aided design systems, and global positioning systems, require database storage of spatial data. Due to cost considerations, many of these products have tight restrictions on processor performance, and on available on-board memory for mass data base storage. Hardware restrictions of this nature are particularly troublesome for portable products, such as global positioning devices, involving embedded systems, because such systems require access to spatial (e.g., geographic/cartographic) data for mapping or navigation purposes. The volume of such data is quite large, and the available memory is limited by cost and physical size considerations.
One known and useful method of storing spatial data, in PC applications, utilizes an R-Tree index structure. R-Tree index structures allow the data to be accessed more efficiently than if randomly stored.
An R-Tree is a collection of nodes branched together in a meaningful or desired fashion. Conventional R-Trees are characterized by a root node representing at least the boundary of the entire spatial region packed and indexed by the R-Tree. All other nodes of the root are descendants of the root, with those nodes branched directly to the root being children of the root. Thus, the following statements are definitive of features in a tree structure, where x, y and z are nodes:
If x is an ancestor of y, y is a descendent of x;
If x and y are children of z, z is a parent of x and y, and x and y are siblings;
If x has no children, x is a terminal node, commonly referred to as a leaf;
If x is not a leaf, it is an internal or branch node, and must be a parent.
More particularly, in original R-Tree structures, point, linear, and areal data features to be organized are represented by their minimum bounding rectangles. A minimum bounding rectangle, or bounding box, describes the maximum and minimum latitude and longitude extents of an object. Each node of the tree contains a collection of minimum bounding rectangles. At the leaf level, a collection of spatial features are grouped geographically, so that nearby features are stored together. Upper (non-leaf) nodes group a collection of nearby lower-level nodes, and serve to index the sub-level spatially. Typically, the number of sub-nodes grouped by a particular node has a fixed limit, say N. When a feature needs to be added to the tree, specific algorithms are used to search the existing tree for a leaf-level node suitable to contain the new feature. As the number of sub-nodes contained exceeds N, the node is split, and changes are propagated up the tree structure. The overall structure grows to create a tree structure with a single node at the top, bounding the entire geographic area covered by the data base, and a collection of sub-levels, each of which covers a certain portion of the data coverage area. An R-Tree constructed this way grows dynamically (in width and height) as spatial features are added at the leaf level. The organization of the tree relative to the feature density in a particular geographic region is governed primarily by the value of N, which determines the number of sub-nodes (or features), at the leaf, the structure is able to represent. Given a specific rectangular area of interest, this data structure provides an efficient means to access spatial data.
Conventionally, leaf nodes in an R-Tree contain index record entries of the form (A, ID-Pointer) where “A” is a minimum bounding rectangle of the region indexed and “ID-Pointer” is a pointer to the region indexed. Particularly, in a two dimensional format, the rectangle A representing the indexed region is defined by [X
min
, X
max
, Y
min
, Y
max
] and “ID-Pointer” is the address of the rectangle A.
Conventionally, non-leaf nodes contain entries of the form (A, Pointer), where A is the minimum bounding rectangle of all rectangles in the child node, and “Pointer” is the address of the child node. As set forth in R-Trees: A Dynamic Index Structure for Spatial Searching, 1994 by Antonin Guttman, incorporated herein by reference, a conventional R-Tree satisfies the following properties:
1. Every leaf node contains between m and M index records, unless it is the root, where M is the maximum number of entries that will fit in one node, and is a parameter, represented by m≦M÷2, specifying the minimum number of entries in a node.
2. For each index record (A, ID-Pointer) in a leaf node, A is the minimum bounding rectangle of the region identified by “ID-Pointer”.
3. Every non-leaf node has between m and M children, unless it is the root.
4. For each entry (A, Pointer) in a non-leaf node, A is the minimum bounding rectangle of the rectangles in the child node to which “Pointer” is pointing.
5. The root node has a least two children, unless it is a leaf.
6. All leaves appear on the same level of the R-Tree.
Recently, it has been proposed to use fractal geometry, and particularly, the Hilbert Space-Filling Curve, to achieve better ordering of the rectangles to be packed in an R-Tree. As set forth in On Packing R-Trees, 1993, by Ibrahim Kamel and Christos Faloustos, which is incorporated herein by reference, the Hilbert Space-Filling Curve visits all coordinates in a grid (e.g., rectangle) exactly once, and never crosses itself. The Hilbert Space-Filling Curve is utilized in an attempt to achieve an improved clustering of rectangular regions to be packed in an R-Tree.
Further theoretical developments and studies of R-Trees are set forth in the following papers, each of which is incorporated herein by reference:
1
. The R
*-
tree: An Efficient and Robust Access Method for Points and Rectangles
, 1990 by Norbert Beckman, et al.;
2
. The R
+-
Tree: A Dynamic Index For Multi
-
Dimensional Objects
, 1987 by Timos Sellis, et al.
3
. Direct Spatial Search on Pictorial Databases Using Packed R
-
trees
, 1985 by Nick Roussopoulos, et al.;
4
. DOT: A Spatial Access Method Using Fractals
, 1991 by Christos Faloutsos, et al.
While conventional R-Trees provide a useful indexing structure for spatial databases, current systems for developing R-Trees do not permit an operator flexibility in establishing useful parameters for the R-Tree. Additionally, while utilization of space-filling curves, when packing R-Tree nodes, has been theoretically proposed to enhance the packing efficiency of an R-Tree, it has been found that greater efficiency can be achieved in accordance with the buffering and packing techniques in accordance with the principals of the present invention, as described herein.
Accordingly, the need exists for a system and method for developing R-Tree index structures, which system is easy to configure for a variety of parameters. The need also exists for a system and method for packing R-Trees which improves the grouping, or clustering, of data representing different cartographic areas.
SUMMARY OF THE INVENTION
Accordingly, it is a primary object of the present invention to efficiently cluster data sets, representing various geographic regions or areas.
It is a further objection of the invention to generate an efficient R-Tree index structure.
It is an object of the invention to permit an operator to select configuration parameters for constructing an R-Tree index, and for packing spatial data.
It is a particular object of the invention to provide the ability to control the height and width of an R-Tree index structure.
An additional object of the present invention is to provide a buffering technique for enhancing clustering of
Beesley Darin J.
Robinson Stephen C.
Walters Thomas H.
Garmin Corporation
Garmin Corporation
Nguyen Phu K.
Rolf Devon A.
LandOfFree
System and method for packing spatial data in an R-tree does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for packing spatial data in an R-tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for packing spatial data in an R-tree will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2471584