16-07-2012, 02:39 PM
The P-tree Algebra
ptree_algebra.pdf (Size: 83.77 KB / Downloads: 30)
INTRODUCTION
More and more spatial data have been collected in various ways.
An important issue is how to efficiently store spatial data and
derive useful information from them. Data mining can help to
find interesting patterns or derive useful rules from spatial data.
However, existing data mining algorithms do not scale well on
large sized spatial data.
In this paper, we try to discuss a data structure, called Peano
Count Tree (or P-tree), and its algebra and properties. P-tree
structure is a lossless representation of the original spatial data.
The P-tree structure can be viewed as a data-mining-ready
structure as it facilitates efficient ways for data mining [7].
P-tree variations
A variation of the P-tree data structure, the Peano Mask Tree
(PM-tree, or PMT), is a similar structure in which masks rather
than counts are used. In a PM-tree, we use a 3-value logic to
represent pure-1, pure-0 and mixed quadrants (1 denotes pure-1,
denotes pure-0 and m denotes mixed). The PM-tree for the
previous example is also given in Figure 3. Since a PM-tree is
just an alternative implementation for a Peano Count tree (PCtree,
or PCT), we will use the term “P-tree” to cover both Peano
Count tree (PCT) and Peano Mask tree (PMT).
P-TREE ALGEBRA
P-tree algebra includes three basic operations: complement, AND
and OR. Each basic P-tree has a natural complement. The
complement of a basic P-tree can be constructed directly from the
P-tree by simply complementing the counts at each level
(subtracting from the pure-1 count at that level), as shown in the
example below (Figure 4). Note that the complement of a P-tree
provides the 0-bit counts for each quadrant.
Levelwise P-tree ANDing
ANDing is a very important and frequently used operation for Ptrees.
There are several ways to perform P-tree ANDing. First
let’s look at a simple way. We can perform ANDing level-bylevel
starting from the root level. Table 1 gives the rules for
performing P-tree ANDing. Operand 1 and Operand 2 are two Ptrees
(or subtrees) with root X1 and X2 respectively. Using PMtrees,
X1 and X2 could be any value among 1, 0 and m (3-value
logic representing pure-1, pure-0 and mixed quadrant). Rules for
P-tree ANDing are given in Table 1. For example, to AND a
pure-1 P-tree with any P-tree will result in the second operand; to
AND a pure-0 P-tree with any P-tree will result in the pure-0 Ptree.
Note that it is possible that ANDing two m’s results in a
pure-0 quadrant if their four subquants result in pure-0 quadrants.
PROPERTIES OF P-TREES
In this section, we will discuss the good properties of P-trees.
We will use the following notations:
x y p , is the pixel with coordinate (x, y), x y i V , , is the value for the
band i of the pixel x y p , , x y i j b , , , is the jth bit of x y i V , , (bits are
numbered from left to right, x, y,i,0 b is the leftmost bit). Indices: x:
column (x-coordinate), y: row(y-coordinate), i: band, j: bit.
For any P-trees P, P1 and P2, P1 & P2 denotes P1 AND P2, P1 | P2
denotes P1 OR P2, P1 ⊕ P2 denotes P1 XOR P2, P′ denotes
COMPLEMENT of P.
Pi, j is the basic P-tree for bit j of band i, Pi(v) is the value P-tree
for the value v of band i, Pi(v1, v2) is the interval P-tree for the
interval [v1, v2] of band I, rc(P) is the root count of P-tree P. P0 is
pure-0 tree, P1 is pure-1 tree. N is the number of pixels in the
image or space under consideration.