The P-tree algebra

ABSTRACT

The Peano Count Tree (P-tree) is a quadrant-based lossless tree representation of the original spatial data. The idea of P-tree is to recursively divide the entire spatial data, such as Remotely Sensed Imagery data, into quadrants and record the count of 1-bits for each quadrant, thus forming a quadrant count tree. Using P-tree structure, all the count information can be calculated quickly. This facilitates efficient ways for data mining. In this paper, we will focus on the algebra and properties of P-tree structure and its variations. We have implemented fast algorithms for P-tree generation and P-tree operations. Our performance analysis shows P-tree has small space and time costs compared to the original data. We have also implemented some data mining algorithms using P-trees, such as Association Rule Mining, Decision Tree Classification and K-Clustering.

REFERENCES

• 1: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 2: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 3: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 4: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 5: R. A. Finkel and J. L. Bentley, "Quad trees: A data structure for retrieval of composite keys", Acta Informatica, 4, 1, 1974.
• 6: HH-codes. Available at http://www.statkart.no/nlhdb/iveher/hhtext.html
• 7: William Perrizo , Qin Ding , Qiang Ding , Amalendu Roy, Deriving High Confidence Rules from Spatial Data Using Peano Count Trees, Proceedings of the Second International Conference on Advances in Web-Age Information Management, p.91-102, July 09-11, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Algorithms, Performance, Theory

Keywords:
Peano ordering, compression, quadrant, spatial data, tree structure