Figure 2. Sample OVPF Objects for a DNC Coastline Feature and Its Metadata 
3. SPATIAL INDEXING SCHEME 
Indexes are built according to some criteria to facilitate faster retrieval of database 
records. For spatial data, this criteria can be the spatial location or bounding rectangle. 
Within the OVPF implementation, the quadtree indexing method (Samet, 1995) is used to 
organize VPF data. This is one of most common indexing schemes used for spatial data. 
The principle of this indexing scheme is based on a simple, recursive subdivision of spatial 
data into four equal-sized cells or quadrants. Each feature is placed in the smallest quadtree 
cell which will completely contain it. The quadtree subdivision terminates based on one of 
two criteria: (1) a preset number of iterations has been reached, or (2) all the data have 
been placed in a cell. In OVPF, the quadtree has been preset to not exceed 20 levels of 
subdivision. 
The quadtree structure has been the pre-dominant searching mechanism to access 
features in the OVPF. The root of the quadtree is determined during the program 
initialization. It is usually set to the spatial extent of a VPF library chosen to import. Each 
feature also has its bounding rectangle defined by the VPF specification. Bounding 
rectangles for area features are stored directly in the VPF source tables. However, 
bounding rectangles for line features must be computed by merging the bounding 
rectangles of component edges of each line feature. Bounding rectangles for point features 
or node features are created by offsetting the coordinate points in four directions by a small 
constant. Once the feature bounding box is known, the minimum sized quadtree cell that 
can include the feature’s bounding box is determined. 
With one of the working models of OVPF, an option to use a splay tree searching 
algorithm is provided. A splay tree is an unbalanced binary tree in which the most- 
recently-accessed node is rotated to the top of the tree. This searching algorithm works 
very well given typical usage patterns for working with a spatial database. Within the GIS 
community, the user tends to focus in on an area of interest for query, display, and