Abstract

An improved database data structure and datatype is disclosed for storing, manipulating and accessing multidimensional spatial data in a database. Binary helical hyperspatial code (HH CODE) is used to represent data of N dimensions. The binary HH CODE data structure maintains the dimensional organization of multidimensional data within the data itself. Spatial data is stored using BH code which is modeled as a N-tree structure derived using recursive decomposition. A high water mark is set as the upper limit for data volume which may be stored in any one partition. As data stored in a partition exceeds the high water mark, the data is decomposed into child partitions such that no partition data stores exceed the high water mark. If the high water mark is exceeded, additional child partitions are automatically created and the parent table is not retained. A data structure is defined which represents the partitioned tables and BH code values. Appropriate attributes are associated with each of the BH code values which may represent non-spatial data such as temperature, salinity, or cosmic ray flux. Methods and apparatus are also provided to apply teachings of binary HH CODE to line segments and topology.

Other References

• Varma et al., "A Data Structue for Spatio-Temporal Databases", International Hydrographic Review, Monaco, LXVII(1), Jan. 1990
• Hsieh et al., "A Conversion and Management System for Parcel Maps", IEEE Comput. Soc. Pres., Nov. 1994
• Beng Chin Ooi, Ken J. McDonnell, Ron Sacks-Davis, "Partial kd-Tree: An Indexing Mechanism for Spatial Database", Dept. of Computer Science, Monash University, Victoria Australia; Dept. of Computing, Royal Melbourne Institute of Technology, 1987
• Yutaka Oshwawa, Masao Sakauchi, "A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database", Institute of Industrial Science, University of Tokyo, 1990
• Max J. Egenhoffer and Robert D. Franzosa, "Point-Set Topological Spatial Relations", Int. J. Geographical Information Systems, 1991, vol. 5, No. 2, 161-174
• "Implementation of HHCodes for use with hydrographic data", H. Iversen, Norwegian Hydrographic Service (NHS), http://www.statkart.no/nlhdb/hhimpl.htm, last updated Feb. 5, 1998
• "What are HH-codes and how can they be used to store hydrographic data?", H. Iversen, Norwegian Hydrographic Service (NHS), http://www.statkart.no/nlhdb/iveher/, last updated Jan. 19, 1998
• Applications of Spatial Data Structures; Computer Graphics, Image Processing, and GIS, H. Samet, University of Maryland, Addison-Wesley Publishing Company, 1990, pp. 1-15 and 174-175
• Hanan Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, 1990, pp. 30-41 and 174-18