Visualization of TV

Visualization of TV

Space Filling Curves and Functional Contours Database analysis can be broken down into 2 areas, Querying and Data Mining. Data Mining can be broken down into 2 areas, Machine Learning and Assoc. Rule Mining Machine Learning can be broken down into 2 areas, Clustering and Classification. Clustering can be broken down into 2 areas, Isotropic (round clusters) and Density-based Machine Learning usually begins by identifying Near Neighbor Set(s), NNS. In Isotropic Clustering, one identifies round sets (disk shaped NNSs about a center). In Density Clustering, one identifies cores (dense round NNSs) then pieces them together. In any Classification based on continuity we classifying a sample based on its NNS class histogram (aka kNN) or we identify isotropic NNSs of centroids (k-means) or we build decision tres with training leafsets and use them to classify samples that fall to that leaf, we find class boundaries (e.g., SVM) which distinguish NNSs in one class from NNSs in another. The basic definition of continuity from elementary calculus proves NNS s are fundamental: >0 >0 : d(x,a)< d(f(x),f(a))< or NNS about f(a), a NNS about a that maps inside it. So NNS Search is a fundamental problem to be solved. We discuss NNS Search from the a vertical data point of view. With vertically structured data, the only neighborhoods that are easily determined are the cubic or Max neighborhoods (L disks), yet usually we want Euclidean disks. We develop techniques to circumscribe Euclidean disks using the intersections of contour sets, the main of which are coordinate projection contours, the intersection of which form L disks. First we review the standard space filling curves, Peano (Z) and Hilbert. In both cases, as the gridding gets finer and finer, each point on the curve converges to a point in the square and those points densely fill the square (no empty spaces of any size) which is why they are called space filling curves. Other than the raster orderings of a gridding of the square, these two methods may have advantages in that Peano ordering preserves distance better than a raster ordering (not as many massive junps) and Hilbert ordering preserves distance even better than Peano (always move to a neighbor). Recall that choosing a pixel or voxel ordering is the first step in creating vertical pTree spatial data. In any Geospatial Analysis, some ordering of the pixels (voxels in 3D) is required. Which one is best may depend upon what the definition of best is and what data area is being analyzed. After a brief look at space filling curves, we treat functional contours. How are functional contours related to space filling curves? With space filling curves, we try to cover a space (2D space) with a 1D curve (up to the pixelization of the space). That is, we try to fill in the space with a function from the real line. In functional contouring, we consider sort of the opposite, namely what gets mapped to a single point by a function into the real line (that is, what does the preimage of a point look like). Familiar examples include isobars (which points get mapped to the same pressure value), isotherms, etc. Hilbert Ordering? In 2-dimensions, Peano ordering is 22-recursive z-ordering (raster ordering) Hilbert ordering is 44-recursive tuning fork ordering (H-trees have fanout=16) down 0 down 0123456789ABCDEF right 0123456789ABCDEF 1 2 3 4 ... ... 0123456789ABCDEF . . 5 6 7 8 left right . 9 A B C D E up ... 0123456789ABCDEF F down ... 0123456789ABCDEF down . 0123456789ABCDEF . 0123456789ABCDEF up . 0123456789ABCDEF Coordinates of a tuning-fork (upper-left) depend on ancestry. (x,y) = (ggrrbb, ggrrbb). If your parent points Down and you are the H node in your tuning-fork, 0 1 E F 3 2 D C 4 5 7 6 8 9 B A your 2-bit contribution is given by: row(x) col(y) 0 00 , 00 1 00 , 01 2 01 , 01 3 01 , 00 4 10 , 00 5 11 , 00 6 11 , 01 7 10 , 01 8 10 , 10 9 11 , 10 A 11 , 11 B 10 , 11 C 01 , 11 D 01 , 10 E 00 , 10 F 00 , 11 Lookup table for Up, Left, Right Parents are similar. FUNCTIONAL CONTOURS: Given f:R(A1..An)Y (any range but usually the Reals) and SY (any subset of the range, but usually 1 real) , define contour(f,S) f-1(S). R A1 A2 : : An f YS graph(f) = { (a1,...,an,f(a1.an)) | (a1..an)R } Y S ... contour(f,S) A1..An space There is a DUALITY between functions, f:R(A1..An)Y and derived attributes, Af of R given by x.Af f(x) where Dom(Af)=Y R A1 A2 An x1 x2 : xn ... f Y R*A f(x) A2 An Af x1 x2 : xn f(x) 1 ... Contour(Af,S) = SELECT A1..An FROM R* WHERE R*.Af S. If S={a}, f-1({a}) is Isobar(f, a) Given a similarity, s:RRReals (e.g., s(x,y)=s(y,x) and s(x,x)s(x,y) x,yR ) and an extension to disjoint subsets of R (e.g., single/complete/average link...) and CR, a k-disk of C is: disk(C,k)C : |disk(C,k)C'|=k and s(x,C)s(y,C) xdisk(C,k), ydisk(C,k). Define its skin(C,k) disk(C,k) - C skin stands for s k immediate neighbors and is a kNNS of C cskin(C,k) allskin(C,k)s closed skin, and ring(C,k) = cskin(C,k) - cskin(C,k-1) disk(C,r) {xR | s(x,C)r}, skin(C,r) disk(C,r) - C ring(C,r2,r1) disk(C,r2) - disk(C,r1) skin(C,r2) - skin(C,r1). r2 r1 C For C = {a} r1 a r2 Given a [psuedo] distance, d, rather than a similarity, just reverse all inequalities. A definition of Predicate trees (P-trees) based on functionals? (generalizes, but does not alter, previous definitions) Given f:R(A1..An)Y and SY define the uncompressed Functional-P-tree as Pf, S a bit map given by Pf,S(x)=1 iff f(x)S. . The predicate for 0Pf,S is the set containment predicate, f(x)S Pf,S a Contour bit map (bitmaps, rather than lists the contour points). If f is a local density (ala OPTICS) and {Sk} a partition of Y, {f-1(Sk)} is a clustering! What partition {Sk} of Y should be use? E.g., a binary partition? (given by a threshold value). In OPTICS Sks are the intervals between crossing points of graph(f) and a threshold line pts below the threshold line are agglomerated into 1 noise cluster. Weather reporters use equi-width interval partitions (of barametric pressure or temp..). Compressed Functional-P-trees (ls) Pf,S (with equi-width leaf size, ls) is a compression of Pf,S by doing the following: 1. order or walk R (converts the bit map to a bit vector) 2. equi-width partition R into segments of size, ls (ls=leafsize, the last 1 can be short) 3. eliminate and mask to 0, all pure-zero segments (via a Leaf Mask or LM ) 4. eliminate and mask to 1, all pure-one segments (via a Pure1 Mask or PM ) Notes: 1. LM is an existential aggregation of R (1 iff that leaf has a 1-bit). Others? (default=existential) 2. There are partitioning other than equi-width (but that will be the default). Doubly Compressed Functional-P-trees with equi-width leaf sizes, (ls1,ls2) Each leaf of (ls1,ls2) Pf,S Pf,S is an uncompressed bit vector and can be compressed the same way: (ls) (ls2 is 2nd equi-width segment size and ls2<< ls1) Recursive compression can continue ad infinitum, (ls1,ls2,ls3) Pf,S (ls1,ls2,ls3,ls4) Pf,S ... BASIC P-trees For Ai Real and fi,j(x) jth bit of the ith component, xi {(*)Pfi,j ,{1} (*)Pi,j}j=b..0 are the basic (*)P-trees of Ai, (* = ls1,...lsk k=0...). For Ai Categorical, and fi,a(x)=1 if xi=aR[Ai], else 0; then {(*)Pfi,a,{1} (*)Pi,a}aR[Ai] are the basic (*)P-trees of Ai For Ai real, the basic P-trees result from binary encoding of individual real numbers (categories). Encodings can be used for any attribute. Note that it is the binary encoding of real attributes, which turns an n-tuple scan into a Log2(n)-column AND (making P-tree technology scalable). Next, we consider various contour functionals that re useful in Machine Learning, starting with R(A1..An) TV(a)=xR(x-a)o(x-a) If we use d for a index variable over the dimensions, = xRd=1..n(xd2 - 2adxd

+ ad 2 ) i,j,k bit slices indexes = xRd=1..n(k2kxdk)2 - 2xRd=1..nad(k2kxdk) + |R||a|2 = xd(i2ixdi)(j2jxdj) - 2xRd=1..nad(k2kxdk) + |R||a|2 = xdi,j 2i+jxdixdj - 2 x,d,k2k ad xdk + |R||a|2 = x,d,i,j 2i+j xdixdj - 2 dad x,k2kxdk + |R||a|2 = x,d,i,j 2i+j xdixdj - 2|R| dadd + = x,d,i,j 2i+j xdixdj + |R|( -2dadd + dadad ) TV(a) = i,j,d 2i+j |Pdi^dj| TV(a) = i>j,d 2i+j+1 |Pdi^dj| + k2k+1 dad |Pdk| + |R|dadad |R||a|2 k,d (22k- 2k+1ad) |Pdk| + collecting |Pdk|s: |R| (a12+..+an2) Note that the first term (the only one involving dual bit-slice predicates) does not depend upon a at all! So it can be subtracted from TV(a), giving a simpler derived attr, TV with identical contours (just a lowered graph) and which can be calculated simply from the basic Ptree rootcounts themselves (no preprocessing). Then subtracting TV() (=mean of R) is a function with identical contours (a High Dimensoin-ready TV). From equation 7, + |R| ( -2dadd +dadad ) TV(a) = x,d,i,j 2i+j xdixdj f(a)=TV(a)-TV() = |R| ( -2d(add-dd) + d(adad- dd) ) = |R|( dad2 - 2ddad + dd2 ) = |R| |a-|2 f()=0 and letting Taking g / ad (a) = g(a) HDTV(a) = ln( f(a) )=ln|R| + ln|a-|2 2( a -)d The Gradient of g at a = | a- |2 2/| a- |2 (a -) The gradient =0 iff a= and gradient length depends only on the length of a- so isobars are hyper-circles The gradient function is has the form, h(r) = 2/r in along any ray from , Integrating, we get that g(a) has the form, 2ln|a-| along any coordinate direction (in fact any radial direction from ), so the shape of graph(g) is a funnel: f(c) The way to get an exact -contour is to move in and out along a- by to inner point, b=+(1-/|a-|)(a-) and outer point c=+(1+/|a-|)(a-). Then take f(b) and f(c) as lower and upper endpoints of the red vertical interval (use EIN formulas on that interval to get a mask of the exact contour). What inteval endpts gives an exact -contour in feature space? f(b) b ac -contour (radius about a) Finally we note that the very same vertical pruning procedures can be used for any functional that requires no additional preprocessing (even if it does require preprocessing - i.e., additional ANDing and Root Counting just to generate the derived attribute values), can be used efficiently (e.g., the dimension projection functionals already have all their basic Ptrees generated for us (since their basic P-trees are precisely the basic P-trees of that dimension). The procedure is alway as shown in the previous slide. To classify a 1. Calculate basic P-trees for the derived attribute column of each training point 2. Calculate b and c (depend upon a and the chosen) 3. Mask the feature space mask for those points with derived attribute value in that the EIN ring [f(b),f(c)] (that is the precise -contour set). 4. User that mask to prune. 5. If the root count of the candidate set is scan-able, proceed to scan and assign votes, else look for another pruning functional (note that the combination of HDTV and all dimension projections will always suffice). f(c) f(b) b ac -contour (radius about a) Graph of TV, TV-TV() and HDTV HDTV TV TV(x15) TVTV() TV(x15)TV() TV()=TV(x33) 5 X 4 3 2 1 1 2 3 4 5 5 Y X 4 3 2 1 1 2 3 4 5 Y Parameters for Vertical Structuring and Smoothing (zooming) of R(A1..An) The parameters defining the conversion of horizontal tables to P-trees are: 1. method of ordering R (walking R) (e.g., (i1..in)-Raster, (i1..in)-Peano, (i1..in)-Hilbert, etc.) 2. leaf sizes (e.g., choice of number of levels, k, and a leafsize for each level, (ls1,...,lsk) Note: How to store these P-trees on disk is an important implementation parameter, but not a theoretical solution space parameter. llu ro po ra tio ga leaf size sequence, (ls1,...,lsk) re gg nm eth Given the Basic P-tree set, BPT { (ls1,...lsk)Pi,j | i=col, j = bit position or category}, a P-tree smoothing taxonomy requires two more solution space parameters: od 3. smoothing level = sl (# of low order bits) 4. rollup or aggregation method (the predicate) (e.g., count, existential, universal, rank, etc.) So the vertical smoothing solution space has four dimensions: Note: Smoothing is clustering (with a particular goal) and choosing good initial partition-clustering centroid sets can be done by smoothing (and then choosing a representative point in each smoothing component or cluster, e.g., the mean) g in th o o sm el, lev sl ordering method of R (walk of R) What is the goal of smoothing R(A1..An) This is the first question to be answered. One answer is that smoothing can increase the speed of DM algorithm processing and solve the curse of cardinality (essentially as a better alternative than random sub-sampling). In this direction, we think of smoothing as pre-clustering rather than random selection, to reduce the cardinality of the table being mined, hopefully without hiding exceptional data (as random sampling almost always does). So this application of smoothing requires that the smoothing algorithm be fast (or be amortizable) and also, if possible, be sensitive to exceptional data, else why do it? A related direction for smoothing is that is can be a method of pruning to reduce the computational complexity of an algorithm, i.e., to produce only the strong preclusters. Then the points outside these cores, can be individually scanned, e.g., to find exceptions or to be processed in some other way. In this direction, the smoothing is used to isolate those dense core neighborhoods that can be treated as "one unit" and therefore vastly increase the processing speed (over examining each individual point in each core). Other goals of Smoothing? Note that the walk order issue is easily described using functions as well. Given a walk of R (which can be thought of as an ordering of the tuples of R and a "step" numbering of those tuples in that order (i.e., assigning a step number to each tuple in the walk: 1,2,3,...). x z A C N F G p P m K L O Q S k h J M v I d e f g 9 a b c 5 6 7 8 1 2 3 4 u r s w K L u r s t u r s M v O P S m k Q R T U d i e f g 9 a b c 5 6 7 8 1 2 3 4 w A Mixed walk, Mw x y z A C N q F G I B D E l y-first Hilbert j walk, yHw. h T q t F p l h B H J o n R U i t N G x-first Peano walk, xPw H

I l q D E o B A D E n y z C In a walk, w:R{1,2,3,...}, w itself is a function on R and defines contours. Since it is a candidate key (uniqueness j property) every isobar, w -1(n), is a singleton, {x} (where x is the nth step of the walk). Interval contours are sets of consecutive steps in the walk. The # of steps from x to y is always an upper bound to the Manhattan distance (if x and y are close in steps, they are close in Manhattan distance). x y H J K o L p k v O P S m M Q R T U d i e f 9 a b c 5 6 7 8 1 2 3 4 g w x y z A C N J K p P h d e f g 9 a b c 5 6 7 8 1 2 3 4 y z N B q o L p P S m k M v O Q d e f g 9 a b c 5 6 7 8 1 2 3 4 s w N J L p u r s Q t u r s v R T U i d e f 9 a b c 5 6 7 8 1 2 3 4 x M O P S k y g z w A C B q D E N F G H I J K o L p P S m 1 t F K m j k y-first Raster h d walk, 9 yRw. 5 q H o l T B D I n R U i r A G x-first Raster walk, xRw F K u z E j x-first Hilbert h walk, xHw. t y C l H J x n w G h v T A y-first Peano order walk yRw. R D E l s M O C I r U i x L Q S k u H I m t F G l q D E o B M

v O Q R T U i e f g a b c 6 7 8 2 3 4 w Mixed Walk, Uncompressed, 2-bit Count Smoothing (Mw () 2 C) 2 2 3 2 This is smoothing using K1 130 120 x y z 0 0 uncompressed Ptrees with count aggregation on 2-lo-grid cells. 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 C E 5 A B D N G F q 7 1 t u 4r s H A j-hi grid is a grid of cells I J K L M resulting from using the j high-order bits to identify 2 3 cells and the rest to walk the interior of each cell. j-lo uses the j low order n o p O v bits to walk cell interiors R l m P Q and the rest to id-cells. 8 S 8 1 T j-hi gives a square pattern j k of cells and j-lo gives U h i square cells. When (and d e f g only when) the space is 9 a b c square (n..n space) are 168 1 w 5 6 7 they equal (j-lo=(b-j)-hi where b=bitwidth(n).) 1 2 3 4 Mw()2C creates a 2-lo-grid count 16 14 histogram and 12 10 is order independent, but requires a 56-tuple multi-scan (or use rootcounts of each value Ptree?) 8 6 4 2 0 (0,0) (0,1) (1,1) (3,0) (2,1) (0,2) (1,2) (0,3) (1,3) (2,3) (3,3) Mw () 1 C produces very accurate smoothing, but involves (expensive?) multiple bit column scan processing. Even calculating rootcounts of P1-lo cells may be expensive? Trade-off? give up accuracy for speed. Use LMs instead of uncompressed bit slices See next slide. K 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G

H I J K L M N O P Q R S T U 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 2 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1n 1 1 1 1 1 0 1 1j 1 1 1 1 1d 0 0 0 09 1 1 15 1 1 0 11 1 1 1 0 0 0 x y z A C N F G H J o l q D E I B K L p m P O Q S k h e f i g a b c 6 7 8 2 3 4 M v R T U w t u r s K 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D

E F G H I J K L M N O P Q R S T U 5 6 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 2 7 3 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 3 4 Mw (8) 2C scans the 1st level LM vectors instead of the full uncompressed bit. x y z C E It depends on the order, but requires only a multi-scan of |LM|=7 bits (not the entire uncompressed bit slice of 56 bits). 22 0 0 0 0 0 00 0 0 0 0 1 00 0 0 0 1 2 1 1 1 1 3 0 1 1 1 4 0 0 1 1 1 1 1 1 13 5 P e f g 9 a b c 5 6 7 8 1 2 3 4 10 01 01 01 01 00 01 11 00 11 00 01 01 00 01 01 01 01 0 1 01 01 01 10 01 01 11 11 11 11 11 11 11 01 0 1 00 01 11 01 11 00 00 11 1 10 0 1 1 1 00 01 0 10 11 01 01 01 0 1 01 01 01 01 01 01 6 00 0 1 10 1 10 11 0 0 1 01 0 1 11 01 s q M O v Q R T w 01 01 01 0 1 01 01 01 01 01 u r U i d 00 L S 00 11 01 00 11 00 t D F

p k 11 12 K m h 23 J o j B H I l 12 N G n 13 A 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 01 01 01 01 01 11 11 0 1 10 0 1 01 00 00 01 0 1 10 0 1 10 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 23 22 00 00 00 00 00 11 00 11 01 0 1 01 11 11 11 11 0 0 01 11 11 11 01 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 11 11 11 10 10 01 01 0 1 11 11 11 01 0 1 10 01 11 01 01 11 0 1 10 11 0 0 01 00 01 10 00 00 00 20 21 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 Mw (8,2) 1 C using 2 levels of LeafMaps (leaf sizes 8 and 2 respectively the black LMs and the red LMs). 0 x 7 y z C 6 E 2 3 1A BD 1 N H I J K L 4 4 5 6 7 u 3 r s t q 1 F G 5 (When there is no red LM shown, it's pure and one can tell which type of purity from the black/blue LM/PMs). 1 M 2 O 1R 1 T 1 4 3 n 2 o l 1j m k h 0 13 12 11 0 1 01 0 1 00 00 00 00 00 00 01 1 1 1 00 1 01 1 1 1 011 0 1 011 1 0 01 1 0 1 01 1 1 1 1 01 1 1 1 01 1 1 0 1 01 1 1 111 1 1 1 1 01 1 1 00 00 1 0 1 1 23 22 21 13 12 00 11 1 10 01 0 0 1 10 0 1 10 1 10 11 0 0 1 01 11 11 11 01 0 1 10 0 1 01 00 00 01 0 1 10 0 1 10 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 11 00 00 00 11 00 00 01 01 01 1 1 11 0 0 0 1 011 1 1 0 0 0 1 1 1 0 00 0 1 01 01 11 11 00 1 1 01 00 00 10 11 01 01 01 01 00 01 g 01 01 0 1 01 01 00 11 f 0 1 10 11 11 0 1 01 1 v 2 2 9 a b c 5 6 7 8 2 2

1 2 3 4 00 01 1 1 00 11 01 0 1 01 01 01 01 01 11 11 01 1 1 11 00 11 01 1 1 00 01 U 01 01 01 01 00 1 1 1 11 1 e 2S 01 01 01 0 1 01 00 1 1 1 11 0 d Q 00 1 01 1 00 11 00 010 0 1 1 01 1 1 1 011 1 1 1 011 i 2pP 01 01 01 01 01 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 01 01 01 01 01 w 23 22 00 00 00 00 00 11 00 11 01 0 1 01 11 11 11 11 0 0 01 11 11 11 01 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 11 11 11 10 10 01 01 0 1 11 11 11 01 0 1 10 01 11 01 01 11 0 1 10 11 0 0 01 00 01 10 00 00 00 20 21 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 0 Mw(8,2) 1 E (existential aggregation) x 7 6 A 3 4 N 5 6 B D q 7 t u r s F G 5 H I J K L M 4 3 n o l 1j 12 P m h 13 p S k 0 i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 11 00 1 01 1 00 11 01 01 01 0 1 01 01 01 01 01 01 01 0 1 01 01 01 01 01 01 00 11 1 10 01 0 0 1 10 00 01 1 1 00 11 01 0 1 01 01 01 01 01 11 11 01 1 1 11 00 11 01 1 1 0 1 10 1 10 11 0 0 1 01 11 11 11 01 0 1 10 0 1 01 00 00 01 0 1 10 0 1 10 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 00 00 00 00 00 00 0 1 01 01 11 11 00 1 1 01 00 z E 2 00 y 2 C Note this also requires a scan of same LM set, so it is the same expense as count smoothing but give up much information (the only advantage is that the result may be simpler to express (one predicate tree over the 1-lo grid cells) 01 1 0 1 10 11 11 0 1 01 01 01 01 01 01 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 01 01 01 01 01 O

v Q U R T w 23 22 00 00 00 00 00 11 00 11 01 0 1 01 11 11 11 11 0 0 01 11 11 11 01 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 11 11 11 10 10 01 01 0 1 11 11 11 01 0 1 10 01 11 01 01 11 0 1 10 11 0 0 01 00 01 10 00 00 00 20 21 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 hs hs hs hs hs hs hs hs hs 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 19 21 23 25 27 29 31 33 35 36 37 39 41 43 45 87 113 168 169 170 171 179 194 195 196 197 201 204 205 209 222 223 224 225 244 247 248 250 251 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0

0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 k P13P12 P11 P10 P23 P22 P21 P20 1 5 6 2 3 4 8 7 b c g f e a 9 d h j n l o m k i U S P p Q O R T w v r s u t q D B A z N H F M L K J I G E C y x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 1 2 1 2 2 2 3 2 9 0 9 7 5 6 7 Changing the walk order to y-first Hilbert and reconstructing the LM(8,2) Ptrees. Note compression. 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 x y z A B C E N J 0 00 00 1 00 00 2 00 00 3 00 11 4 01 01 11 11 5 0 01 1 10 11 01 6 00 0 1 10 00 00 00 s M O Q v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 w 23 22 20 21 00 00 01 11 11 00 11 01 0 1 01 0 1 10 00 00 00 11 01 11 0 1 01 00 01 00 00 11 11 01 00 00 0 1 01 11 11 0 1 01 01 0 1 10 0 1 10 00 00 00 11 00 11 01 01 01 01 01 10 10 10 00 11 01 01 0 1 01 11 1 011 11 0 01 01 0 11 11 00 01 01 00 11 11 10 01 01 0 1 0 1 01 11 11 01 01 1 1 01 01 01 01 01 01 01 01 11 1 011 11 00 11 0 1 10 01 01 0 0 11 11 11 0 1 01 11 11 0 1 10 0 1 01 11 11 0 1 10 0 1 10 11 0 1 10 11 11 0 1 01 0 1 01 P S m k 11 12 L p l 13 K o h r H I j u F G n q D t 01 0 1 10 0 1 01 1 1 01 0 1 01 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 10 01 0 1 10 0 1 10 00 01 11 0 1 10 0 1 01 00 01 0 0 0 1 01 0 1 01 11 11 11 0 1 01 00 00 01 00 11 1 11 1 11 11 00 0 1 01 11 11

01 01 01 0 0 11 00 01 1 1 01 01 01 10 10 01 11 00 11 00 0 y-first Hilbert (8,2) 1-lo Count Vertical Smoothing yH (8,2) 1 C 1 2 7 3 y z A C E 6 N On these Hilbert ordered basic Ptrees smoothing with count aggregation by using the both levels of LMs (black and red) J K 3 2 l j 1 12 00 00 01 11 11 00 00 00 00 00 00 00 11 01 01 11 11 0 0 11 01 01 11 1 11 1 01 00 11 11 01 11 01 00 0 1 00 00 11 11 01 00 00 01 11 11 01 01 00 00 00 01 11 11 11 22 21 13 12 00 00 00 0 00 00 00 11 1 00 00 00 11 2 00 00 00 11 3 00 11 01 01 01 11 1 011 11 0 01 0 11 11 00 01 00 11 11 01 0 1 01 11 11 01 1 1 11 1 011 11 00 11 01 01 0 0 11 00 01 11 11 11 01 01 11 00 11 1 11 1 11 01 00 01 11 01 01 23 h 11 00 4 01 01 11 11 5 0 0 1 1 10 11 01 6 00 11 0 1 10 00 00 00 p P O Q S i d e f 7 t D r q u 3 s M 1 2 1 2 1 1 v R T U g 1 2 9 a b 3c 5 6 7 8 2 2 1 2 3 4 10 w 23 22 20 21 00 00 01 11 11 00 11 01 0 1 01 0 1 10 00 00 00 11 01 11 0 1 01 00 01 00 00 11 11 01 00 00 0 1 01 11 11 0 1 01 01 0 1 10 0 1 10 00 00 00 11 00 11 01 01 01 01 01 10 10 10 00 11 01 01 0 1 01 11 1 011 11 0 01 01 0 11 11 00 01 01 00 11 11 10 01 01 0 1 0 1 01 11 11 01 01 1 1 01 01 01 01 01 01 01 01 11 1 011 11 00 11 0 1 10 01 01 0 0 11 11 11 0 1 01 11 11 0 1 10 0 1 01 11 11 0 1 10 0 1 10 11 0 1 10 11 11 0 1 01 0 1 01 1 1 1 1 m k 0 13 L 4 o 6 H I n 5 B F G 5 4 3 1 1 1 1 x 01 0 1 10 0 1 01 0 1 01 0 1 01 01

0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 10 01 0 1 10 0 1 10 00 01 11 0 1 10 0 1 01 00 01 0 0 0 1 01 0 1 01 11 11 11 0 1 01 00 00 0 1 10 00 11 1 11 1 11 11 00 0 1 01 11 11 01 01 01 0 0 11 00 01 1 1 01 01 01 10 10 01 11 00 11 00 key P13 0 1 0 2 0 5 0 6 0 3 0 4 0 7 0 8 0 9 0 a 0 d 0 e 0 b 0 c 0 f 0 g 0 h 0 j 0 i 0 k 0 l 0 n 0 m 0 o 0 U 0 S 0 T 0 P 0 Q 0 p 0 R 0 O 1 w 1 v 0 I 0 J 0 K 0 L 0 M 0 G 0 E 0 C 0 x 0 y 0 N 0 H 0 F 0 z 0 A 0 D 0 B 1 q 1 r 1 s 1 t 1 u P12 P11 P10 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 P23 P22 P21 P20 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1

1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 Change walk order to peano (x first or Z-ordered) and reconstruct 2-level Ptrees. x y z A C N j 13 12 P 11 K L r s M O Q S k h J p m u H I l t F G o q D E n B v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 w 23 22 20 21 0 00 00 00 00 01 11 11 0 1 01 0 1 01 01 0 1 01 0 1 01 00 00 00 00 11 01 0 0 11 1 00 00 0 1 01 01 00 11 11 00 01 0 1 01 0 1 01 0 0 01 00 00 11 00 01 1 1 00 11 2 00 00 01 00 11 00 11 01 11 00 0 1 10 00 01 11 01 11 0 1 10 11 00 00 1 0 1 01 1 10 11 01 00 11 00 11 0 1 0 1 01 01 1 1 11 0 1 10 01 0 1 10 0 1 10 0 1 10 0 1 10 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 01 01 0 0 00 11 01 01 01 01 01 01 01 01 00 11 01 01 0 1 01 00 0 110 1 1 01 01 01 01 01 01 10 01 01 00 11 1 11 1 11 0 01 01 0 00 11 11 01 01 00 0 1 01 11 01 01 1 1 0 1 01 11 11 01 0 1 10 01 11 11 0 1 01 11 01 11 0 0 0 1 01 0 1 10 11 0 1 10 11 3 00 4 01 11 00 5 0 0 00 00 6 01 00 0 1 01 11 11 11 0 1 10 11 11 0 1 01 11 11 11 00 0 1 01 01 0 0 00 01 01 01 01 10 01 01 01 11 11 11 0 1 10 0 1 10 0 1 10 00 11 0 xP (8,2) 1 C 7 y z C E 6 Now on these x-first Peano ordered basic Ptrees smoothing with count aggregation by using the both levels of LMs: 1 x 2 A 2 N D H I J K L 4 12 3 1 F G 5 3 B 5 6 7 t r q u 3 s M 1 1 4

3 n 2 o l j 1 h 5 1 12 11 00 00 00 00 01 11 11 00 00 01 01 00 11 11 00 00 00 11 01 01 11 00 0 0 00 00 01 00 1 01 1 01 00 00 01 1 1 11 01 00 01 11 11 11 01 11 11 01 00 11 00 11 01 00 01 00 01 11 11 11 0 01 0 11 11 11 01 01 01 01 11 11 11 23 22 21 13 12 11 P O Q S i d 9 13 p m k 0 1 1 1 1 e f a b c 6 7 8 2 3 4 1 1 1 v 1 R T U g 1 1 3 2 2 w 23 10 22 21 20 00 0 00 00 00 00 01 11 11 0 1 01 0 1 01 01 0 1 01 0 1 01 00 00 00 00 11 01 0 0 11 00 11 1 00 00 0 1 01 01 00 11 11 00 01 0 1 01 0 1 01 0 0 01 00 00 11 00 01 1 1 00 11 00 11 2 00 00 01 01 01 01 00 11 01 01 00 0 110 11 01 01 10 01 01 00 11 1 11 1 11 01 0 1 01 00 0 110 1 1 01 01 01 01 01 00 11 1 11 1 11 0 01 01 0 00 11 11 01 01 00 0 1 01 11 01 01 1 1 0 1 01 11 11 01 0 1 10 01 01 01 01 01 01 01 0 1 10 0 1 10 0 1 10 0 1 10 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 01 01 0 0 11 11 11 11 01 00 11 00 11 01 11 00 0 1 10 00 01 11 01 11 0 1 10 11 00 00 1 0 1 01 1 10 11 01 00 11 00 11 0 1 0 1 01 01 1 1 11 0 1 10 00 00 0 01 0 00 11 11 01 00 01 11 01 1 1 01 11 11 01 0 1 11 11 0 1 01 11 01 11 0 0 0 1 01 0 1 10 11 0 1 10 11 00 00 00 11 11 11 0 0 11 3 00 4 01 11 00 5 0 0 00 00 6 01 00 0 1 01 11 11 11 0 1 10 11 11 0 1 01 11 11 11 00 0 1 01 01 0 0 00 01 01 01 01 10 01 01 01 11 11 11 0 1 10 0 1 10 0 1 10 00 11 key P13 0 1 0 5 0 9 0 d 0 j 0 n 0 2 0 6 0 e 0 h 0 l 0 3 0 7 0 b

0 a 0 f 0 k 0 o 0 I 0 G 0 E 0 C 0 x 0 4 0 8 0 c 0 g 0 i 0 m 0 J 0 y 0 S 0 P 0 p 0 K 0 N 0 z 0 U 0 Q 0 L 0 A 0 T 0 O 0 M 0 H 0 F 0 D 0 B 0 R 1 v 1 q 1 w 1 r 1 t 1 s 1 u P12 P11 P10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 P23 P22 P21 P20 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 Change walk order to raster (yfirst or Z-ordered) and reconstruct 2-level Ptrees. x y z A C N j 13

11 12 P K L r s M O Q S k h J p m u H I l t F G o q D E n B v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 w 23 22 20 21 0 00 00 00 00 00 01 0 0 11 00 00 00 011 1 00 00 11 01 0 1 01 00 1 00 00 00 0 1 0 1 01 11 11 11 01 0 1 10 00 00 00 0 1 01 010 1 10 00 00 0 1 10 0 1 10 01 0 0 01 01 0 1 10 01 0 1 01 0 1 01 11 2 00 00 11 3 00 01 01 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 0 1 01 11 0 1 10 01 00 0 1 01 0 1 10 01 1 1 11 0 1 01 1 011 1 1 10 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 0 1 10 1 01 01 0 11 11 00 0 1 10 11 11 11 1 10 010 11 11 0 1 10 11 01 01 0 0 11 11 01 01 0 0 00 00 0 1 01 01 11 11 11 01 0 1 10 00 00 0 1 01 01 1 1 01 0 0 01 1 11 1 11 11 0 1 10 00 01 0 0 00 00 00 00 101 00 11 0 1 4 00 5 00 6 01 0 1 01 11 11 11 0 1 10 0 1 01 11 11 11 11 11 0 1 10 0 1 10 0 1 10 00 11 10 01 10 10 01 11 0 1 10 11 11 0 1 01 0 1 01 01 1 1 0 1 01 01 01 01 01 01 01 01 01 01 1 1 01 01 10 01 1 1 01 10 11 10 01 01 0 1 10 10 01 01 01 10 01 10 01 10 11 0 1 10 11 11 01 10 01 11 11 0 1 01 0 1 01 01 01 01 01 01 01 01 01 0 yR (8,2) 1 C 7 y N G J l L h 5 1 00 00 00 01 01 11 11 00 01 010 1 00 00 01 01 0 1 01 11 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 01 11 01 01 00 01 01 01 1 1 11 01 1 011 11 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 01 1 01 0 11 11 00 01 11 11 11 1 010 11 11 01 11 01 0 0 11 11 01 11 11 11 01 11 11 00 00 00 00 00

11 00 01 01 00 00 01 01 11 11 11 11 11 11 00 01 11 01 01 00 1 11 1 11 11 01 01 11 11 00 11 01 0 1 00 00 00 011 1 00 00 00 00 00 11 0 1 13 12 p P t u r s 3 1 q M e f Q a b c 6 7 8 2 3 4 1 v R T U g 10 11 O S i d 9 21 1 2 1 3 1 2 1 3 2 1 m k 0 22 7 F K o j 1 23 6 4 2 11 5 H I n 12 4 B 3 13 3 1 4 3 3 3 1 A D E 5 2 z C 6 Now on these y-first raster ordered basic Ptrees smoothing with count aggregation by using the both levels of LMs: 1 x w 23 22 20 21 0 00 00 00 00 00 01 0 0 11 00 00 00 011 1 00 00 11 01 0 1 01 00 1 00 00 00 0 1 0 1 01 11 11 11 01 0 1 10 00 00 00 0 1 01 010 1 10 00 00 0 1 10 0 1 10 01 0 0 10 01 0 1 10 01 0 1 01 0 1 01 11 2 00 00 11 3 00 01 01 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 0 1 01 11 0 1 10 01 00 0 1 01 0 1 10 01 1 1 11 0 1 01 1 011 1 1 10 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 0 1 10 1 01 01 0 11 11 00 0 1 10 11 11 11 1 10 010 11 11 0 1 10 11 01 01 0 0 11 11 01 01 0 0 00 00 0 1 01 01 11 11 11 01 0 1 10 00 00 0 1 01 01 1 1 01 0 0 01 1 11 1 11 11 0 1 10 00 01 0 0 00 00 00 00 101 00 11 0 1 4 00 5 00 6 01 0 1 01 11 11 11 0 1 10 0 1 01 11 11 11 11 11 0 1 10 0 1 10 0 1 10 00 11 10 01 10 10 01 11 0 1 10 11 11 0 1 01 0 1 01 01 1 1 0 1 01 01 01 10 01 10 11 0 1 10 0 1 10 0 1 10 01 0 1 01 01 10 01 1 1 01 10 11 10 01 01 0 1 01 10 11 0 1 10 11 11 10 10 01 01 10 01 11 11 0 1 01 0 1 01 01 01 01 01 01 01 01 01 0 1 x 7 y A 4 5

N G 6 J F K L t u r s 3 1 q H I 0 7 B D E 5 3 1 4 3 3 3 1 z C 6 2 7 y 2 z C E 6 A 2 N yR (8,2) 1 C J K L 4 12 3 1 D H I 5 3 B F G M 4 1 x 5 6 7 t r q u 3 s M 1 1 xP (8,2) 1 C 4 3 3 n o 2 l j h Q 9 5 1 e f g a b c 6 7 8 2 3 4 1 n v 2 R S o l j T 1 U i d 0 O P m k 1 1 2 1 3 1 2 1 3 2 1 p P i d 9 5 1 O Q S h w p m k 0 1 1 1 1 e f a b c 6 7 8 2 3 4 1 1 1 v 1 R T U g 1 1 3 2 2 w Comparing orderings of (8,2) 1-low-bit Count Smoothing 0 1 x 7 y 2 1 D1 z A C 6 E N F G 5 B H I J K L M 3 4 4 5 6 7 3 r s t q u 1 2 2 7 3 3 1 1 1 1 x y z A C N J K 3 o l 1j m k h i d 2P Q 2S U p e f O T 1R 1 1 v 1 2 o l j 1 g 2a b 2c 5 6 7 8 2 2 1 2 3 4 n 0 9 w 1 1 1 1 p P m k h O Q S i d e f 6 7 t r q u 3 s H I

L 4 n 5 F G M (8,2) 1 C 4 B D E 5 3 0 1 6 4 2 0 1 2 1 2 1 yH (8,2) 1 C 1 v R T U M g 1 2 9 a b 3c 5 6 7 8 2 2 1 2 3 4 w 0 yH (8) 2 C x 3 o j 0 22 0 0 0 0 0 0 13 12 0 0 00 00 0 0 1 00 00 0 0 1 2 00 00 0 1 0 1 3 00 11 1 1 1 1 4 01 1 1 01 11 11 5 0 0 1 1 10 11 01 1 6 00 0 0 1 1 1 N F h 11 0 1 10 00 00 00 J K 1 m k L p P i e f 9 a b c 5 6 7 8 1 2 3 4 2 Q t u r s 1 q v 1 R T U d 2 3 M O S 2 g 10 w 23 22 20 21 00 00 01 11 11 00 11 01 0 1 01 0 1 10 00 00 00 11 01 11 0 1 01 00 01 00 00 11 11 01 00 00 0 1 01 11 11 0 1 01 01 0 1 10 0 1 10 00 00 00 11 00 11 01 01 01 01 01 10 10 10 00 11 01 01 0 1 01 11 1 011 11 0 01 01 0 11 11 00 01 01 00 11 11 10 01 01 0 1 0 1 01 11 11 01 01 1 1 01 01 01 01 01 01 01 01 11 1 011 11 00 11 0 1 10 01 01 0 0 11 11 11 0 1 01 11 11 0 1 10 0 1 01 11 11 0 1 10 0 1 10 11 0 1 10 11 11 0 1 01 0 1 01 H I 2 B D G l 23 A C 1n 12 1 z E On these Hilbert ordered basic Ptrees smoothing with count aggregation by using highest level LMs only. 13 y 01 0 1 10 0 1 01 0 1 01 0 1 01 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 10 01 0 1 10 0 1 10 00 01 11 0 1 10 0 1 01 00 01 0 0 0 1 01 0 1 01 11 11 11 0 1 01 00 00 0 1 10 00 11 1 11 1 11 11 00 0 1 01 11 11 01 01 01 0 0 11 00 01 1 1 01 01

01 10 10 01 11 00 11 00 xP (8,2) 2 C x A j 13 12 k 11 J K L p 1 P m h 22 F H I l 23 N G o B D E n 12 z C On these Peano ordered basic Ptrees smoothing with count aggregation by using highest level LMs only. 13 y Q d e f 9 a b c 5 6 7 8 1 2 3 4 2 r s 2 1 q v 1 R T U i u M O S 1 t g w 23 10 22 21 20 0 0 0 0 0 00 00 00 00 01 11 11 0 1 01 0 1 01 01 0 1 01 0 1 01 00 00 00 00 11 01 0 0 11 0 0 0 0 1 00 00 0 1 01 01 00 11 11 00 01 0 1 01 0 1 01 0 0 01 00 00 11 00 01 1 1 00 11 0 0 0 1 2 00 00 11 01 01 01 01 0 1 3 00 00 11 1 1 1 1 4 01 01 01 0 1 01 00 0 110 1 1 01 01 01 01 01 01 10 01 01 00 11 1 11 1 11 0 01 01 0 00 11 11 01 01 00 0 1 01 11 01 01 1 1 0 1 01 11 11 01 0 1 10 01 01 01 01 01 1 01 0 1 10 0 1 10 0 1 10 0 1 10 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 01 01 0 0 00 0 01 00 11 00 11 01 11 00 0 1 10 00 01 11 01 11 0 1 10 11 00 00 1 0 1 01 1 10 11 01 00 11 00 11 0 1 0 1 01 01 1 1 11 0 1 10 11 11 0 1 01 11 01 11 0 0 0 1 01 0 1 10 11 0 1 10 11 0 1 1 1 1 1 1 1 11 00 5 0 0 00 00 6 01 00 0 1 01 11 11 11 0 1 10 11 11 0 1 01 11 11 11 00 0 1 01 01 0 0 00 01 01 01 01 10 01 01 01 11 11 11 0 1 10 0 1 10 0 1 10 00 11 yR (8,2) 2 C x j h 23 Q S v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 11 O

w 23 22 20 21 1 00 00 011 1 00 00 11 01 0 1 01 00 0 1 1 00 00 00 0 1 0 1 01 11 11 11 01 0 1 10 00 00 00 0 1 01 010 1 10 00 00 0 1 10 0 1 10 01 0 0 10 01 0 1 10 01 0 1 01 0 1 01 11 1 1 2 00 00 11 1 1 3 00 01 01 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 0 1 01 11 0 1 10 01 00 0 1 01 0 1 10 01 1 1 11 0 1 01 1 011 1 1 10 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 0 1 10 1 01 01 0 11 11 00 0 1 10 11 11 11 1 10 010 11 11 0 1 10 11 01 01 0 0 11 0 0 0 1 1 2 P M 00 0 1 p s 00 00 01 0 0 11 0 1 L r 00 0 0 12 K u 00 0 1 13 F t 0 00 0 0 22 J m k 1 B H I l 12 N G o A D E n z 1 3 C On these y-first raster ordered basic Ptrees smoothing with count aggregation by using highest level LMs only. 13 y 1 1 4 00 1 1 5 00 1 6 01 1 11 01 01 0 0 00 00 0 1 01 01 11 11 11 01 0 1 10 00 00 0 1 01 01 1 1 01 0 0 01 1 11 1 11 11 0 1 10 00 01 0 0 00 00 00 00 101 00 11 0 1 0 1 01 11 11 11 0 1 10 0 1 01 11 11 11 11 11 0 1 10 0 1 10 0 1 10 00 11 10 01 10 10 01 11 0 1 10 11 11 0 1 01 0 1 01 01 1 1 0 1 01 01 01 10 01 10 11 0 1 10 0 1 10 0 1 10 01 0 1 01 01 10 01 1 1 01 10 11 10 01 01 0 1 01 10 11 0 1 10 11 11 10 10 01 01 10 01 11 11 0 1 01 0 1 01 01 01 01 01 01 01 01 01 x y z A t 1 3 C N G F H I J K L x u r D E 0 1 B s 3 y 1 z A C D E N F G M H I 2 B J K L 2 l p 2 P m O

Q S k h i e f g 9 a b 5 6 7 1 2 3 4 t u r s t u r s 1 q yH (8,2) 2 C 1n v R o l T j U d 3 M yR (8,2) 2 C o 2 0 1 m k h p P Q S i e f c 9 a b c 8 5 6 7 8 1 2 3 4 1 v R T U d w O g 2 w Comparing orderings of (8,2) 2-lo-bit Count Smoothing x y z A C B D E N q t u r s x J K L A N F G H I M B D E H I z C F G y J K L 1 M xP (8,2) 2 C M (8,2) 2 C o l p m Q S k h P O i e f g a b c 6 7 8 2 3 4 n v o l R j T w p 1 P m k h U 2 1 q O Q S d e f 9 a b c 5 6 7 8 1 2 3 4 2 1 R T U i v g w 0 M (8,2) 1 C 1 x 7 y 2 z A C 6 B N 4 5 6 7 1 t 3 D E u r q s F G 5 3 H I J K L M 4 3 n 2 l 1j 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 23 22 0 0 11 21 13 12 7 1

2 3 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 00 00 1 1 1 1 01 1 1 1 1 0 1 01 01 11 11 00 1 1 01 0 1 10 11 11 0 1 01 01 01 01 01 01 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 T w 4 10 11 U R 8 00 00 01 0 1 10 0 1 10 1 00 6 Q c 11 11 01 0 1 10 0 1 01 1 1 5 v 1 1 0 1 10 1 10 11 0 0 1 01 11 0 1 b 00 11 1 10 01 0 0 1 10 00 1 a 01 01 01 01 00 1 9 O g 01 01 0 1 01 01 1 00 f 00 01 1 1 00 11 01 0 1 01 01 01 01 01 11 11 01 1 1 11 00 11 01 1 1 0 1 e 01 01 01 01 00 1 i d 01 01 01 0 1 01 0 1 S 00 1 01 1 00 11 00 1 P m h 12 p k 0 13 1 o 01 01 01 01 01 23 22 00 00 00 00 00 11 00 11 01 0 1 01 11 11 11 11 0 0 01 11 11 11 01 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 11 11 11 10 10 01 01 0 1 11 11 11 01 0 1 10 01 11 01 01 11 0 1 10 11 0 0 01 00 01 10 00 00 00 20 21 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 yH (8,2) 1 C x y z A C D E N 12 11 23 22 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 1 21 13 12 0 0 00 00 0 1 1 00 00 0 1 1 2 00 00 1 0 1 1 3 00 11 1 1 1 1 4 01 1 1 1 1 1 1 1 01 11 11 5 0 0 1 1 10 11 01

1 6 00 11 0 1 10 00 00 00 L 1 p P u s M O Q S k R 1 v T U i d e f 9 a b 5 6 7 1 2 3 g 1 1 c 8 w 4 10 23 22 20 21 00 00 01 11 11 00 11 01 0 1 01 0 1 10 00 00 00 11 01 11 0 1 01 00 01 00 00 11 11 01 00 00 0 1 01 11 11 0 1 01 01 0 1 10 0 1 10 00 00 00 11 00 11 01 01 01 01 01 10 10 10 00 11 01 01 0 1 01 11 1 011 11 0 01 01 0 11 11 00 01 01 00 11 11 10 01 01 0 1 0 1 01 11 11 01 01 1 1 01 01 01 01 01 01 01 01 11 1 011 11 00 11 0 1 10 01 01 0 0 11 11 11 0 1 01 11 11 0 1 10 0 1 01 11 11 0 1 10 0 1 10 11 0 1 10 11 11 0 1 01 0 1 01 K m h 13 J o j r q 1 H I l t F G n 2 B 01 0 1 10 0 1 01 0 1 01 0 1 01 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 10 01 0 1 10 0 1 10 00 01 11 0 1 10 0 1 01 00 01 0 0 0 1 01 0 1 01 11 11 11 0 1 01 00 00 0 1 10 00 11 1 11 1 11 11 00 0 1 01 11 11 01 01 01 0 0 11 00 01 1 1 01 01 01 10 10 01 11 00 11 00 xP (8,2) 1 C x 23 22 0 s F K L 1 p P m M O Q S k R 1 v T U i d e f 9 a b 5 6 7 1 2 3 g 1 1 c 8 w 4 23 10 11 u 22 21 20 0 00 00 01 11 11 0 1 01 0 1 01 01 0 1 01 0 1 01 00 00 00 00 11 01 0 0 11 0 1 1 00 00 0 1 01 01 00 11 11 00 01 0 1 01 0 1 01 0 0 01 00 00 11 00 01 1 1 00 11 0 1 1 2 00 00 11 01 01 01 01 1 1 3 00 00 11 1 1

1 1 4 01 01 01 10 01 01 1 00 11 1 11 1 11 01 0 1 01 00 0 110 1 1 01 01 01 01 01 11 00 5 0 0 00 00 0 01 01 0 00 11 11 01 01 00 0 1 01 11 01 01 1 1 0 1 01 11 11 01 0 1 10 01 01 01 01 01 0 01 0 1 10 0 1 10 0 1 10 0 1 10 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 01 01 0 0 00 1 1 6 01 01 00 11 00 11 01 11 00 0 1 10 00 01 11 01 11 0 1 10 11 00 00 1 0 1 01 1 10 11 01 00 11 00 11 0 1 0 1 01 01 1 1 11 0 1 10 11 11 0 1 01 11 01 11 0 0 0 1 01 0 1 10 11 0 1 10 11 1 0 0 0 1 0 0 0 1 0 1 1 1 1 12 r q 2 1 00 0 1 13 t 0 00 0 1 21 J o h 1 B H I j 11 N G l 0 A D E n 12 z C On these Peano ordered basic Ptrees smoothing with count aggregation by using highest level LMs only. 13 y 1 1 1 1 1 1 00 0 1 01 11 11 11 0 1 10 11 11 0 1 01 11 11 11 00 0 1 01 01 0 0 00 01 01 01 01 10 01 01 01 11 11 11 0 1 10 0 1 10 0 1 10 00 11 yR (8,2) 1 C On these x-major raster ordered basic Ptrees smoothing with count aggregation by using highest level LMs only. 22 K L M 1 O p P m Q S v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 10 w 23 22 20 21 1 00 11 01 0 1 01 00 1 1 1 00 00 00 0 1 0 1 01 11 11 11 01 0 1 10 00 00 00 0 1 01 010 1 10 00 00 0 1 10 0 1 10 01 0 0 10 01 0 1 10 01 0 1 01 0 1 01 11 1 1 1 2 00 00 11 1 1 1 3 00 01 01 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 0 1 01 11 0 1 10 01 00 0 1 01 0 1 10 01 1 1 11 0 1 01 1 011 1 1 10 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 0 1 10 1 01 01 0 11 11 00 0 1 10 11 11 11 1 10 010 11 11 0 1 10 11 01 01 0 0 11 0 1

0 0 0 1 0 1 1 0 1 1 1 4 00 1 1 1 1 5 00 1 6 01 1 F 00 00 011 1 00 0 1 s 00 1 1 r u 00 00 01 0 0 11 0 1 J k 11 D 1 00 0 0 12 t 00 0 1 13 B 0 00 0 0 21 A H 1 h 23 z o j 11 N I l 12 E y G n 13 C 1 1 2 x 1 1 11 01 01 0 0 00 00 0 1 01 01 11 11 11 01 0 1 10 00 00 0 1 01 01 1 1 01 0 0 01 1 11 1 11 11 0 1 10 00 01 0 0 00 00 00 00 101 00 11 0 1 0 1 01 11 11 11 0 1 10 0 1 01 11 11 11 11 11 0 1 10 0 1 10 0 1 10 00 11 10 01 10 10 01 11 0 1 10 11 11 0 1 01 0 1 01 01 1 1 0 1 01 01 01 10 01 10 11 0 1 10 0 1 10 0 1 10 01 0 1 01 01 10 01 1 1 01 10 11 10 01 01 0 1 01 10 11 0 1 10 11 11 10 10 01 01 10 01 11 11 0 1 01 0 1 01 01 01 01 01 01 01 01 01 C 1 1 2 E N x y z A B t D r x 1 u J K L A N 1 l 1 p I P m O Q h n v J K L j d e f g 9 a b c 5 6 7 8 1 2 3 4 p s M Q S k w O P m h U 1 o l T i u yH (8,2) 1 C R S k r q 1 H yR (8,2) 1 C o t F G M 2 B D E H I z C s F G y R 1 v T U i d e f 9 a b 5 6 7 1

2 3 g 1 1 c 8 w 4 Comparing orderings of (8,2) 1-lo-bit Count Smoothing 0 1 x 7 y 2 z A C 6 N 4 5 6 r q F G H I J K L M M (8,2) 1 C 4 3 n 2 l 1j p P m S k h 0 1 o i d e f 9 a b 5 6 7 1 2 3 O Q U v R T g 1 1 c 8 4 7 t 3 D E 5 3 B w 1 u s As far as using this info to create an good initial cluster centroid set, I like Hilbert because the centriod at (3,3) is strong and would n attract I, so the initial clustering is j very good (actually doesn't necessarily need improvement) x y z A C 1 B D E N t r q F G H I J K L M xP (8,2) 1 C 1 o l p P m S k h O Q R 1 v T U i d e f 9 a b 5 6 7 1 2 3 g 1 1 c 8 4 w 2 1 u s Comments so far x Someone should look at y-first-Peano yPw (N-ordering) It might be a bit better since it moves immediately from the lower left octant to the one above it??? How about y-first Raster (x-major sorting order)? z A C N l P K L O Q S k h J p m u r s H I o q t F G n B D E j How about x-first-Hilbert? y M v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 w What about other aggregations? What about universal? (note that finding good initial centroids may work better using universal since it identifies only very dense areas (but maybe too dense? That is, too few centroid areas?). What about majority aggregation (1 iff the majority of the bits are 1-bits)? Note that one cannot use the LMs or PMs for this, but must recompute these bit vectors of size |LM| by examining each not-pure-zero leaf. What about other rank aggregations (e.g., 3/4ths i.e., 1 iff at least 3/4ths of the bits are 1-bits)? Of course any rank aggregation takes a lot of additional processing, whereas, existential and universal use the LM and PM vectors that are already computed and immdiately available. Comments continued x-first Hilbert ordering is as shown here --> x y z A B C D E N z A C N t u r s I J K o L p P S m k 9 a b c 5 6 7 8 1 2 3 4 d e f g 9 a b

c 5 6 7 8 1 2 3 4 y z n R A j N w q F H J K L p P S m k h B D o l T r s w C I v u g G O t R T f x v U E U i Q e M Q P S d H s M O i F G h q D E l B L p k Below is x-first Raster and below at right is y-first Raster y K m h x J o j u r H I l t F G n q M v O Q R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 w M (8) yH (8) xP (8) yR (8) m13 0 0 0 0 0 0 0 1 0 0 0 0 0 0 m23 0 0 0 0 0 0 0 1 1 1 1 1 0 1 H13 0 0 0 0 0 0 0 0 0 1 0 0 0 0 H23 0 0 0 0 0 0 0 0 0 1 1 1 1 1 P13 0 0 0 0 0 0 0 0 0 1 0 0 0 1 PH23 0 0 0 0 0 0 0 0 0 1 1 1 1 1 01111111 01111100 10000000 11111110 00111111 11000000 00011111 00111111 m12 0 0 0 0 0 0 0 1 0 1 0 1 1 1 m22 0 0 0 0 1 1 0 1 1 1 0 1 1 1 H12 0 0 0 0 0 0 1 1 0 1 1 1 1 1 H22 0 0 0 0 1 1 1 1 0 1 0 1 0 1 P12 0 0 0 0 0 0 1 1 0 1 0 1 0 1 P22 0 0 0 0 1 1 1 1 0 1 1 1 1 1 X13 0 0 0 0 0 0 0 0 0 0 0 0 0 1 01111111 X12 0 0 0 0 0 0 0 1 1 1 1 1 0 1 X23 0 0 0 0 0 1 0 1 0 1 0 1 0 1 X22 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00111110 00000110 00111001 10011111 00101111 10111101 00111010 10100111 11111110 11100000 10111101 10000000 01111111 11111100 00011111 10001110 00001111 11101111 01000001 m11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 m21 0 0 1 1 0 1 0 1 0 1 0 1 0 1 H11 0 1 0 1 0 1 0 1 1 1 0 1 0 1 H21 0 0 1 1 0 1 0 1 0 1 0 1 0 1 P11 0 1 0 1 0 1 0 1 1 1 0 1 0 1 P21 0 0 1 1 0 1 0 1 0 1 0 1 1 1 00110011 00110011 01010101 01111111 11001111 11111001 01001010 00001111 11111110 11111110 00011111 01111000 00001111 11110100 00001111 00000111 10001110 01111111 00111100 00111110 01111111 11100011 11100111 00001111 01001111 00110011 00100011 11110011 11110110 -1111111 00001111 00011111 01111110

01110001 m10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 m20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 H10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 H20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 P10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 P20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 10011111 X11 0 0 0 1 00011111 1 1 0 1 11111110 0 0 0 1 01111111 1 1 X10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00001100 01100000 11011110 00011011 11011110 11101111 11101111 X21 0 1 0 1 0 1 0 1 0 1 0 1 0 1 X20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00000001 00110100 10100111 01100110 01101110 11101011 10110011 11101111 01010101 01010101 11001100 01010100 01010000 00001010 00011001 00001111 00001111 00110011 10001111 11111001 10011111 11000110 00110110 01101000 10010101 10001010 00011010 01000001 01000010 01100011 00111001 01101010 01010101 11001100 11110111 11101011 01010101 00010101 10101010 10001010 00010100 01000001 10010101 00110011 00110011 01010101 01100101 11111110 10111011 10100011 00000011 11100000 00000001 11111110 00000111 10000000 10100011 01011101 10001001 01010101 01100101 11111110 10111011 10100011 We have a wealth of classification and clustering tools now (also ARM). What methods leap to mind? yH key P13 P12 1 0 0 5 0 0 6 0 0 2 0 0 3 0 0 4 0 0 8 0 0 7 0 0 b 0 0 c 0 0 g 0 0 f 0 0 e 0 0 a 0 0 9 0 0 d 0 0 h 0 0 j 0 0 n 0 0 l 0 0 o 0 0 m 0 0 k 0 0 i 0 0 U 0 1 S 0 1 P 0 1 p 0 1 Q 0 1 O 0 1 R 0 1 T 0 1 w 1 1 v 1 0 r 1 1 s 1 1 u 1 1 t 1 1 q 1 0 D 0 1 B 0 1 A 0 1 z 0 1 N 0 1 H 0 1 F 0 1 M 0 1 L 0 1 K 0 1 J 0 0 I 0 0 G 0 0 E 0 0 C 0 0 y 0 0 x 0 0 ANDing Alg: resLM = ^TLM ^T'^PPM' resLeaf exists iff resLM=1 resLeaf=^TresLeaf^T'^PresLeaf' P11 P10 P23 P22 P21 P20 Hs 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 1 0 0 0 1 3 0 1 0 0 0 0 4 1 0 0 0 0 0 5 1 1 0 0 0 0 6 1 1 0 0 0 1 7 1 0 0 0 0 1 8 1 0 0 0 1 0 9 1 1 0 0 1 0 10 1 1 0 0 1 1 11 1 0 0 0 1 1 12 0 1 0 0 1 1 13 1 0 0 0 1 0 14 0 0 0 0 1 0 15 0 0 0 0 1 1 16 0 1 0 1 0 0 18 0 0 0 1 0 1 20 0 0 0 1 1 1 22 0 1 0 1 1 0 24 1 0 0 1 1 1 26 1 1 0 1 1 0 28 1 0 0 1 0 1 30 1 1 0 1 0 0 32 0 1 0 1 0 0 34 0 0 0 1 0 1 36 0 0 0 1 1 0 37 0 0 0 1 1 1 38 0 1 0 1 1 0 40 1 0 0 1 1 1 42 1 1 0 1 1 0 44 1 0 0 1 0 1 46 1 0 0 0 0 1 88 1 0 0 1 1 1 114 1 0 1 1 1 0 169 1 1 1 1 1 0 170 1 1 1 1 1 1 171 1 0 1 1 1 1 172 1 1 1 1 1 0 180 1 0 1 1 1 0 195 1 0 1 1 1 1 196 0 1 1 1 1 1 197 0 0 1 1 1 1 198 0 0 1 1 0 1 202 1 0

1 1 0 0 205 1 0 1 1 0 1 206 1 0 1 0 1 1 210 0 1 1 0 1 1 223 0 0 1 0 1 1 224 1 1 1 0 1 1 225 1 0 1 0 1 1 226 1 0 1 1 0 0 245 1 0 1 1 0 1 248 1 0 1 1 1 0 249 1 1 1 1 1 1 251 1 0 1 1 1 1 252 H13 0 0 0 0 0 0 0 0 0 1 0 0 0 0 H23 0 0 0 0 0 0 0 0 0 1 1 1 1 1 yH (8) 11111110 00111111 H12 0 0 0 0 0 0 1 1 0 1 1 1 0 1 H22 0 0 0 0 1 1 1 1 0 1 0 1 0 1 10000000 H11 0 1 0 1 0 1 0 1 1 1 0 1 0 1 01111111 11111100 00011111 H21 0 0 1 1 0 1 0 1 0 1 0 1 0 1 10111101 x A fast isotropic clustering algorithm: 0. remove noise using H-step gap analysis. y z A C B D E N F G H I J K L 10001110 01111111 H10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00111100 00111110 01111111 11100011 11100111 H20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00001111 11110100 00001111 00000111 2 00110110 01101000 10010101 10001010 00011010 01000001 01000010 01100011 00111001 01101010 01010101 11001100 11110111 11101011 q 1 t u r s 1 t u r s M 1. Use yH (8) 2-lo cells as initial clusters (with strengths) n o l j 1 m k h P 9 5 1 2. expand the strongest cluster by 1 bit (but only if they do not collide with an existing cluster): expand (01 11) to (0 1) O Q T U e f g a b c 6 7 8 2 3 4 y z A 2 x C N G o l j J 1 m k h K 9 5 q F 1 L p P O f g a b c 6 7 8 1 v R T U e 2 M Q S i d B H I n w D E revise strength and repeat 2 1 v R S i d This gives us 3 noise points {q,v,w} and 5 clusters (the right ones except that it doesn't separate out an tiny embedded cluster in octant (01,01) but that is to be expected since the diameter of that embedded cluster is smaller than the 2hi cell diameter. p w xP (8) xP (8,2) P13 0 0 0 0 0 0 0 0 0 1 11000000 0 0 0 1 00011111 P12 0 0 0 0 0 0 1 1 0 1 0 1 0 1 P23 0 0 0 0 0 0 0 0 0 1 1 1 1 1 P22 0 0 0 0 1 1 1 1 0 1 1 1 1 1 13 00111111 12 11 10001110 00001111 11101111 01000001 23 10 P11 0 1 0 1 0 1 0 1 1 1 0 1 0 1 P21 0 0 1 1 0 1 0 1 0 1 0 1 1 1 P10

0 1 0 1 0 1 0 1 0 1 0 1 0 1 00001111 01001111 00110011 00100011 11110011 11110110 -1111111 P20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00001111 00011111 01111110 01110001 22 21 01010101 00010101 10101010 10001010 00010100 01000001 10010101 00110011 00110011 01010101 01100101 11111110 10111011 10100011 20 0 00 00 00 00 01 11 11 0 1 01 0 1 01 01 0 1 01 0 1 01 00 00 00 00 11 01 0 0 11 1 00 00 0 1 01 01 00 11 11 00 01 0 1 01 0 1 01 0 0 01 00 00 11 00 01 1 1 00 11 2 00 00 01 00 11 00 11 01 11 00 0 1 10 00 01 11 01 11 0 1 10 11 00 00 1 0 1 01 1 10 11 01 00 11 00 11 0 1 0 1 01 01 1 1 11 0 1 10 01 0 1 10 0 1 10 0 1 10 0 1 10 01 0 1 10 00 0 1 10 01 0 1 10 00 0 1 01 0 1 01 01 0 0 00 11 01 01 01 01 01 01 01 01 00 11 01 01 0 1 01 00 0 110 1 1 01 01 01 01 01 01 10 01 01 00 11 1 11 1 11 0 01 01 0 00 11 11 01 01 00 0 1 01 11 01 01 1 1 0 1 01 11 11 01 0 1 10 01 11 11 0 1 01 11 01 11 0 0 0 1 01 0 1 10 11 0 1 10 11 3 00 4 01 11 00 5 0 0 00 00 6 01 00 0 1 01 11 11 11 0 1 10 11 11 0 1 01 11 11 11 00 0 1 01 01 0 0 00 01 01 01 01 10 01 01 01 11 11 11 0 1 10 0 1 10 0 1 10 00 11 yR (8) yR (8) 13 X13 0 0 0 0 0 0 0 0 0 0 0 0 0 1 01111111 X12 0 0 0 0 0 0 0 1 1 1 1 1 0 1 X23 0 0 0 0 0 1 0 1 0 1 0 1 0 1 X22 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00111110 00000110 00111001 10011111 00101111 12 10011111 X11 0 0 0 1 00011111 1 1 0 1 11111110 0 0 0 1 01111111 1 1 X10 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00001100 01100000 11011110 00011011 11011110 11101111 11101111 X21 0 1 0 1 0 1 0 1 0 1 0 1 0 1 X20 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00000001 10 11 23 00110100 10100111 01100110 01101110 11101011 10110011 11101111 22 00000011 11100000 00000001 11111110 00000111 10000000 10100011 01011101 10001001 01010101 01100101 11111110 10111011 10100011 20 21 0 00 00 00 00 00 01 0 0 11 00 00 00 011 1 00 00 11 01 0 1 01 00 1 00 00 00 0 1 0 1 01 11 11 11 01 0 1 10 00 00 00 0 1 01 010 1 10 00 00 0 1 10 0 1 10 01 0 0 10 01 0 1 10 01 0 1 01 0 1 01 11 2 00 00 11 3 00 01 01 01 0 0 11 11 01 01 0 0 00 01 01 01 00 11 01 01 0 1 011 1 0 1 01 11 0 1 10 01 00 0 1 01 0 1 10 01 1 1 11 0 1 01

1 011 1 1 10 01 0 1 01 01 01 01 01 01 11 01 0 1 11 01 01 01 1 1 0 1 10 1 01 01 0 11 11 00 0 1 10 11 11 11 1 10 010 11 11 0 1 10 11 01 01 0 0 11 11 01 01 0 0 00 00 0 1 01 01 11 11 11 01 0 1 10 00 00 0 1 01 01 1 1 01 0 0 01 1 11 1 11 11 0 1 10 00 01 0 0 00 00 00 00 101 00 11 0 1 4 00 5 00 6 01 0 1 01 11 11 11 0 1 10 0 1 01 11 11 11 11 11 0 1 10 0 1 10 0 1 10 00 11 10 01 10 10 01 11 0 1 10 11 11 0 1 01 0 1 01 01 1 1 0 1 01 01 01 10 01 10 11 0 1 10 0 1 10 0 1 10 01 0 1 01 01 10 01 1 1 01 10 11 10 01 01 0 1 01 10 11 0 1 10 11 11 10 10 01 01 10 01 11 11 0 1 01 0 1 01 01 01 01 01 01 01 01 01 Implementation Specification R(A1..An) has basic Ptrees, (ls)Pi,j i=1..n and if Ai is real with bitwidth=mi or if Ai is categorical with categories {a1..ami} then j=1..mi Let m=i=1..nmi Sort {(ls)Pi,j} by i first, then j. Alias each P-tree by Pk where k is its sort position, k=1..m. Develop a simple transportable AND utility (assembler, C, C++...) that takes as input: 2 m-bit vectors P, T and and a 2-bit output-switch, S where P (Pattern) specifies which P-trees are to be involved by (1-bit) and T (Truth) has a 1-bit iff P=1 and is the operand (uncomplemented). For those with P=1 and T=0 their complements are the operand. Note: If a simple P-tree complement is called for (no ANDing) just set that P-bit to 1 and leave that T-bit at 0. Let M be a state variable specifying the number of P-trees in the set (M must be at least m). For the output-switch: if the first bit is 1, the result P-tree is to be stored as (ls)PM+1 and if the second bit is 1 the rootrccount is to be returned. P,T,S (ls) PM+1 K 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U 5 6 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 2 7 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 3 4 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 2 2 2 3 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 3 4 2 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 3 5 2 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 3 3 1 1 1 1 1 1 32 31 3021 2010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 5 7 3 3 7 2 2 2 2 2 2 32 31 30 21 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 2 1 7 7 5 2 9 Note that PM(B')=LM'(B) LM(B')= PM'(B P = AND-input-pattern (vertical slices involved in AND) T = AND=truth-pattern (truth value of thos inolved) 2 10 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 2 1 ANDing Algorithm: resLM = ^TLM ^T'^PPM' resLeaf exists iff resLM=1 and then resLeaf=^TresLeaf^T'^PresLeaf' (if no operands, install pure1 or create a PM) e.g., 13^12: P=1100 0000 T=1100 0000, resLM = LM13^LM12 =0001000 resLeaf(3): same P and T. LMs in red and PMs in blue below. so resLM 11 ^ 11 = 11 PMs show that the 2 middle leaves are pure1 (rc=4 already) 1 1 1 1 1 1 and that the last leaf of 13 is pure1 so just retrieve last leaf of 12 (01) and accumulate 1-count into rc (=5) and ANDing first leaves, 01 ^ 10 = 00, so rc=5 2L Mw 13 01 01 01 0 1 01 01 01 01 01 00 01 11 00 11 00 01 01 00 01 01 01 01 01 0 1 01 01 0 1 10 01 11 11 11 11 11 11 01 1 1 0 1 00 01 11 01 11 00 00 11 1 10 0 1 1 1 00 01 0 10 11 01 01 01 0 1 01

01 01 01 01 01 1 00 3 4 5 10 00 11 01 00 11 0 00 2 11 12 6 00 00 00 0 1 10 1 10 11 0 0 1 01 0 1 11 01 01 01 01 01 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 23 01 01 11 11 0 1 10 0 1 01 00 00 01 0 1 10 0 1 10 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 20 21 00 00 00 00 00 11 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 01 0 1 11 11 0 1 01 1 1 11 11 11 11 11 10 10 0 1 0 0 11 01 11 01 0 1 11 11 11 01 11 01 0 1 10 01 11 00 01 01 01 22 11 0 1 10 11 0 0 01 00 01 01 10 00 00 00 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 K 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U 5 6 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 2 7 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 3 4 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1

1 0 0 1 2 2 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 3 4 2 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 3 5 2 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 3 3 1 2 1' 0 3 2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 2 resLM = ^TLM ^T'^PPM' resPM unnecessary - must be construct. resLeaf exists iff resLM=1 and then resLeaf=^TresLeaf^T'^PresLeaf' 1 1 1 1 0 1 1 1 1 1 1 1 13'^12^20: P=1100 0001 T=0100 0001, resLM = LM12^LM20 ^PM'13 =0001111 resLeaf(3456): 10 1 1 1 ^0 ^ 0 = 0 rc=12 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 11 10 00 1 1 1 1 1 1 1 1 1 1 1 1 10 00 01 11 1 0 1 1 1 1 1 1 1 0 1 1 11 Note that PM(B')=LM'(B) LM(B')= PM'(B P = AND-input-pattern (vertical slices involved in AND) T = AND=truth-pattern (truth value of thos inolved) 01 10 13 01 01 01 0 1 01 01 01 01 01 00 01 11 00 11 00 01 01 00 01 01 01 01 01 0 1 01 01 0 1 10 01 11 11 11 11 11 11 01 1 1 0 1 00 01 11 01 11 00 00 11 1 10 0 1 1 1 00 01 0 10

11 01 01 01 0 1 01 01 01 01 01 01 1 00 3 4 5 10 00 11 01 00 11 0 00 2 11 12 6 00 00 00 0 1 10 1 10 11 0 0 1 01 0 1 11 01 01 01 01 01 01 1 1 00 11 01 01 01 01 01 01 0 0 01 01 00 01 0 0 23 01 01 11 11 0 1 10 0 1 01 00 00 01 0 1 10 0 1 10 0 1 01 00 0 1 10 0 1 10 00 0 1 01 0 1 10 0 1 01 20 21 00 00 00 00 00 11 00 00 1 0 11 11 00 01 0 0 11 11 0 01 01 0 00 11 11 01 01 01 0 1 11 11 0 1 01 1 1 11 11 11 11 11 10 10 0 1 0 0 11 01 11 01 0 1 11 11 11 01 11 01 0 1 10 01 11 00 01 01 01 22 11 0 1 10 11 0 0 01 00 01 01 10 00 00 00 00 11 00 11 0 1 10 00 11 11 11 11 0 1 10 0 1 01 00 0 1 01 01 11 11 0 1 10 0 1 01 11 11 0 1 01 11 0 1 10 00 11 00 0 1 01 0 1 10 k 1 1 1 1 3 2 1 0 2 2 2 2 3 2 1 0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1

1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 x-first Peano (Z-ordering?) Given R(A1..An) (vector space), a = (a1 .. an) = x ( k=b..0 a1,k2k ... k=b..0 an,k2k ) i=1..n Dom(Ai) i=1..nk=b..0(xi,k-ai,k)2 = k=b..0 rk2 A N H I or l P K L M O Q S k h J p m q F G o B D E First we treat p=1 (Manhattan distance) and we consider only the polytant where all ai xi (other n polytants are handled similarly with the appropriate signs) so that all |xi-ai| = xi-ai = 0 and thus, j L1Ring(x,a)= {x | i=1..n(xi-ai) = r } or all x such that k z C The Lp r-Ring about a, LpRing(a,r) is: {x | Lp(x,a)p = rp} where Lp(x,a)p = i=1..n |xi-ai|p k y v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 i=1..n(k=b..0 xi,k2k - k=b..0ai,k2k) = k=b..0 rk2k or i=1..nk=b..0 xi,k2k - i=1..nk=b..0ai,k2k = k=b..0 rk2k or i=1..nk=b..0 xi,k2k = k=b..0 rk2k + i=1..nk=b..0ai,k2k or i=1..nk=b..0 xi,k2k = k=b..0 (rk+i=1..nai,k)2k or k=b..0(i=1..nxi,k)2k = k=b..0(rk+i=1..nai,k)2k Forming a P-tree mask for the set of xs that solve this equation seems difficult because increasing one dimension requires decreasing another, etc. w t u r s k 1 1 1 1 3 2 1 0 2 2 2 2 3 2 1 0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 Given R(A1..An) (vector space), x-first Peano (Z-ordering?) a = (a1 .. an) = x ( k=b..0 a1,k2k ... k=b..0 an,k2k ) i=1..n Dom(Ai) z A C N H I o l j The left side can be multiplied out and one can, again, seek a P-tree mask for the set of solutions, but it presents the same "trade off" problem, right? P K L O Q S k h J p m q F G Next we treat p=2 (square Euclidean distance) and L2Ring(x,a)2= {x | i=1..n(xi-ai)2 = r } or all x such thatn B D E The Lp r-Ring about a, LpRing(a,r) is: {x | Lp(x,a)p rp} where Lp(x,a)p = i=1..n |xi-ai|p i=1..n(k=b..0(xi,k-ai,k)2k)2 = (k=b..0 rk2k)2 y M v R T U i d e f g 9 a b c 5 6 7 8

1 2 3 4 w t u r s ps k 1 1 1 1 3 2 1 0 2 2 2 2 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 33 34 37 38 41 42 45 46 49 50 54 56 57 58 61 62 86 110 142 143 154 155 158 164 166 172 174 175 178 180 182 186 187 188 190 237 252 253 254 255 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1

1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 Dr. Scott is looking for a formula the P-tree mask of the solution set based on the tree position of a and x. Is there a closed form formula for the P-tree mask of the L1 or L2 ring of radius r about a? Note that the walk of any quadrant is the same at a given level. But that suggests an approach based on j-lo cells is the way to do it (the mask any such cell is trivial). The only concern here is when a is near the boundary of its cell (so in order to get a superset mask of its r-disk, one has to consider some neighboring cells). That suggests just using the EIN-disk about a? x y z A C N j J p P m h K L O Q S k 9ade bcfg hj ik ln mo US T PQ p s v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 RO r M w IJ 1256 3478 u H I l t F G o q D E n B KL M w GE C xy N H F zAD B v q ps ps ps ps ps ps ps ps 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 ps k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 33 34 37 38 41 42 45 46 49 50 54 56 57 58 61 62 86 110 142 143 154 155 158 164 166 172 174 175 178 180 182 186 187 188 190 237 252 253 254 255 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u rstu Summary slide: The last few slides have been an attempt to develop a formula to mask the Manhattan ring of a point at a given radius. This work builds off of a discussion with Dr. Kirk Scott and his CATA-06 paper. It seems to come down to a case of solving the equation (creating a P-tree mask for the solutions of): k k k=b..0(i=1..nxi,k)2 = k=b..0(rk+i=1..nai,k)2 This involves trading off among the dimensions (give from 1, take from another). Can we form P-tree masks in this case? One can use j-lo grid cells as Euclidean r-disk supersets. However, when the center, a, is not in the middle of the cell, these may not give small enough supersets so they can then be pruned using scans. One could always take the j-lo cell and a selection of its bordering j-lo cells to make sure the Euclidean r-disk is completely super-setted. This would involve determining the subset of dimensions in which ai is close to zero (pushing a too close to those "low-side" cell borders) and close to 1 (pushing a too close to those "hi-side" cell borders). The EIN r-disk about a (the L r-disk about a) is the best cube-shaped superset, of course. But is its P-tree mask easily computed, i.e., is there preprocessing that makes it a matter of plugging the a i and r values into one formula with no additional ANDing or Root-Counting? That is, can all the vertical processing be preprocessing and therefore amortized for all a and r? One additional note regarding EIN-disk super-setting of the Euclidean r-disk about a: That's what Taufik is now doing. First, he takes the r-disk-superscribed TV-countour of a (the thinnest TV-contour that contains the Euclidean r-disk about a). Then prune out a sufficient number of the "far away or halo points" by intersecting it with (ANDing masks) the r-disk-superscribing Xi-ai-contours of a (either one i at a time or taking the cluster of all large i-ai values, if there is one). We note that the intersection of all Euclidean-r-disk-superscibing X ei-contours IS the EIN-disk or radius r about a. Another approach suggested by Dr. Scott is to develop formulas for an approximation of the Euclidean disk (or ring) about an arbitrary center point based on where it sits in its j-lo cell. Once these formulas are developed for one cell, they are the same for others (just change the hi-bits that are used to address the cell). (This is similar to the process described in the j-lo grid cell paragraph above). K 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U 5 6 1 1 3 2 3' 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1

1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 2 7 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 3 4 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 2 2 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 3 4 2 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 3 5 2 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 3 3 rc(13^23)=5 <32 rc(13^23')=rc13-rc(13^23)7-5=2<32 rc(13'^23)=rc23-rc(13^23)=22-5=17<32 rc(13'^23')=56-17-2-5=3232 so 3-lo cell (0,0) is core x y z A C N j K L O P Q S k h J p m u r s H I l t F G o q D E n B M v R T U i d e f g 9 a

b c 5 6 7 8 1 2 3 4 w j-lo core cell mining (assume a cell is core iff it is 50% full): What we note is that we need all patterns precomputed (and RootCounted). Can we AND, RootCount, e.g., 13^23 13'^23 13^23' 13'^23' in 1 step? (e.g., by concatenating, flipping and shifting before ANDing???) Next slide attempts to use the PeanoStep derived attribute in combo with this approach since it walks by j-lo cells. There are no 2-lo core cell in 3-lo cells (1,1) or (1,0) since <8 points in them (5 & 2 resp.) 2-lo core cells in 3-lo cell (0,1)? rc(13'^23^12^22)=7<8 ... p s k p p p p 1 1 1 1 3 2 1 0 p p p p 2 2 2 2 3 2 1 0 p p p p s s s s 7 6 5 4 p p p p s s s s 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 33 34 37 38 41 42 45 46 49 50 54 56 57 58 61 62 86 110 142 143 154 155 158 164 166 172 174 175 178 180 182 186 187 188 190 237 252 253 254 255 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1

1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 2 3 2 7 3 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 2 3 3 3 2 4 5 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 2 3 2 2 7 4 3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1

0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 3 3 3 2 5 4 3 2 NOTE!! ps7=p23 ps6=p13 ps5=p22 ps4=p12 ps3=p21 ps2=p11 ps1=p20 ps0=p10 So there is nothing in the basic p-tree set of the Peano Step Count derived attribute that we didn't already have in the basic Ptree set of the table itself! x y z A C N F G H I o l j P K L O Q S k h J p m q D E n B M v R T U i d e f g 9 a b c 5 6 7 8 w t u r s k 1 1 1 1 3 2 1 0 2 2 2 2 3 2 1 0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 2 3 2 7 3 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 2 3 3 3 2 4 5 3 What's next? What do we get for free once we have computed all of basic P-tree pairs? i.e., The basic P-tree set is {Pi,j | j=bi..0 for each i=1..n} (there are b=i=1..nbi+1 of them ) Taufik precomputes {rc(Pi,j^Pi,k) | i=1..n, all j,k} (there are i=1..n(bi+1)2 of them ) If we were to pre-compute all { rc(Pi,i^Ph,k | Pi,i and Ph,k basic P-trees } (b2 of them), we can get the rcs of any equi-width partition of TV-contours out of it for free (just using Taufik's precomputation). We can also get the rcs of all 2-hi grid cells out of it. We can also get the rcs of all intersections of equi-width TV-contours with 2-hi cells. That might be good enough to always yield up a very good Euclidean disk superset? By very good, I mean, given a point, a, a superset of Disk(a,r) which has few enough points so it can be scanned for the Disk(a,r) points (or it can be fitted with a Gaussian Radial Basis Vote Function for NN Classification). If we were to pre-compute { rc(Pi,i^Ph,k^Pl,m} (b3 of them), we can get the rcs of any equi-width partition of TV-contour and also the rcs of all 3-hi grid cells, etc. Clearly, if we had the rcs of all basic P-tree combinations, we could do anything! Is there a parallel (or pipelined) way to compute all of them? h s h h h h h h h h s s s s s s s s 7 6 5 4 3 2 1 0 k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 19 21 23 25 27 29 31 33 35 36 37 39 41 43 45 87 113 168 169 170 171 179 194 195 196 197 201 204 205 209 222 223 224 225 244 247 248 250 251 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 6 2 3 4 8 7 b c g f e a 9 d h j n l o m k i U S P p Q O R T w v r s u t q D B A z N H F M L K J I G E C y x 5 6 2 1 2 1 2 2 2 3 2 9 0 9 7 5 6 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Changi 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 h h h h 1 1 1 1 3 2 1 0 h h h h 2 2 2 2 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1

1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 2 3 2 7 3 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 2 3 3 3 2 4 5 3 x y z A C N F G H I J K o P S m k h L p l j q D E n B M O Q v R T U i d e f g 9 a b c 5 6 7 8 1 2 3 4 w t u r s Pre-processing costs? Pairs within attributes first (what Taufik does). rc(a3^a2') no^ required = rc(a3) - rc(a3^a0) rc(a3^a2) = 7-3=4 7-5=2 rc(a3^a0') rc(a3^a1') rc(a3^a1) 7-7=0 rc(a3'^a2) ^ req, (but just count black-0 red-1 combos = 19) rc(a3'^a1) rc(a3'^a0) 18) ( a3^a2 and a3'^a2 in 1 instr or in || ?) 27) 2 3 3 3 2 4 5 3 b1' 23 b2' 21 22 b3' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0

1 0 0 0 1 1 34 a0' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 34 a1' 2 3 2 7 3 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 22 a2' 5 6 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 33 a3' 2 3 3 4 7 2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 49 31 22 30 33 b0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 35 0 34 b2 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M

G E C x y N H F z A D B q r s t u 0 22 b3 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 22 a0 b b b b 3 2 1 0 19 34 a1 a a a a 3 2 1 0 0 27 23 a2 k a3 a 2 1 3 0 b0' rc(a3'^a1') no ^ req, = rc(a3') - rc(a3'^a0) rc(a3'^a0') rc(a3'^a1) 27 22 rc(a3'^a2') rc(a3'^a2) = 49 - 19 18 = 30 31 (so far: 4 rc's out of 2 ANDs) 7 5 7 3 56 a3 a2 a1 a0 b3 b2 b1 b0 0 18 0 0 2 0 4 a3' a2' a1' a0' b3' b2' b1' b0' Pre-processing costs? rc(a2^a1') no^ required = rc(a2) - rc(a2^a0) rc(a2^a1) = 23-7=16 23-13=10 rc(a2^a0') rc(a2'^a1) ^ req, (but just count black-0 red-1 combos = 15) rc(a2'^a0) 21) 2 3 3 3 2 4 5 3 b1' 23 b2' 21 22 b3' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 34 a0' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 34 a1' 2 3 2 7 3 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 22 a2' 5 6 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1

0 1 0 1 a3' 3 2 3 4 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 49 33 12 18 31 22 30 33 b0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 35 0 34 b2 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 0 22 b3 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 22 a0 b b b b 3 2 1 0 34 a1 a a a a 3 2 1 0 19 15 0 27 21 0 23 13 7 18 0 10 16 7 5 7 3 0 2 0 4 56 a3 a2 a1 a0 a3' a2' a1' a0' a2

k a3 a 2 1 b0' rc(a2'^a0') rc(a2'^a1') no ^ req, = rc(a2') - rc(a2'^a0) rc(a2'^a1) = 33 - 15 21 = 18 12 b3 b2 b1 b0 b3' b2' b1' b0' Pre-processing costs? rc(a1^a0') no^ required = rc(a1) - rc(a1^a0) = 34-12=22 rc(a1'^a0) ^ req, (but just count black-0 red-1 combos = 10) 2 3 3 3 2 4 5 3 b1' 23 b2' 21 b3' 22 a0' 34 a1' 34 a2' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 a3' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 49 22 12 33 12 18 31 22 30 33 b0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b1 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 35 0 34 b2 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 22 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1

1 1 1 1 1 1 0 1 1 1 1 0 22 19 15 10 0 34 12 27 21 0 22 23 13 7 18 0 10 16 7 5 7 3 0 2 0 4 56 a3 a2 a1 a0 a3' a2' a1' a0' a0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 a1 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u a2 b b b b 3 2 1 0 a3 a a a a 3 2 1 0 b0' rc(a1'^a0') no ^ req, = rc(a1') - rc(a1'^a0) = 22 - 10 = 12 (total of 12 ANDs so far. k b3 b2 b1 b0 b3' b2' b1' b0' 2 3 3 3 2 4 5 3 b1' 23 b2' 21 b3' 22 a0' 34 17 16 16 34 a1' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 a2' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a3' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 49 22 12 33 12 18 31 22 30 33 b0 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1

0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 b1 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 18 35 22 17 17 17 22 19 15 10 0 34 12 27 21 0 22 23 13 7 18 0 10 16 7 5 7 3 0 2 0 4 56 a3 a2 a1 a0 a3' a2' a1' a0' b3 b2 b1 0 18 34 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 a0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u a1 b b b b 3 2 1 0 a2 a a a a 3 2 1 0 a3 k b0' Pre-processing costs? b0 0 17 0 0 5 5 7 b3' b2' b1' b0' 2 3 3 3 2 4 5 3 b1' 23 9 22 9 8 34 17 16 16 33 18 14 14 0 35 21 18 13 0 12 34

22 19 17 0 12 15 17 17 17 0 5 5 7 b3' b2' b1' b0' a0' b3' b2' 21 34 a1' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 a2' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a3' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 49 b0 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 b1 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 22 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 22 12 33 12 18 31 22 30 22 19 15 10 0 34 12 27 21 0 22 23 13 7 18 0 10 16 7 5 7 3 0 2 0 4 56 a3 a2 a1 a0 a3' a2' a1' a0' a0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u a1 b b b b 3 2 1 0 a2 a a a a 3 2 1 0 a3 k b0' Pre-processing costs? b3 b2 b1 b0 2 3 3 3 2 4 5 3 b0' b1' 23 21 9 22 9 8 34 17 16 16 32 21 20 20 b2' b3' a0' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 34 a1' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a2' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a3' 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 49 22 22 12 33 12 18 31 22 30 33 29

18 14 14 0 35 21 29 18 13 0 12 34 22 19 28 17 0 12 15 17 17 17 17 0 5 5 7 b0 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 b1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 b3 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u 22 19 15 10 0 34 12 27 21 0 22 23 13 7 18 0 10 16 7 5 7 3 5 6 6 4 0 2 0 4 2 1 1 3 56 a3 a2 a1 a0 b3 b2 b1 b0 a3' a2' a1' a0' b3' b2' b1' b0' a0 b b b b 3 2 1 0 a1 a a a a 3 2 1 0 rc(a3'^b3) = rc(b3) - rc(a3^b3) = 22-5 = 17 rc(a3'^b3') = total - rc(a3^b3)-rc(a3^b3'(-rc(a3'^b3)=56-5-2-17=32 similarly, similarly, rc(a3^b2)=6 rc(a3^b1)=6 rc(a3^b2')=1 rc(a3^b0)=4 rc(a3^b1')=1 rc(a3'^b2)=28 rc(a3^b0')=3 rc(a3'^b1)=29 rc(a3'^b2')=21 rc(a3'^b0)=29 rc(a3'^b1')=20 rc(a3'^b0')=20 a2 k rc(a3^b3') = rc(a3) - rc(a3^b3) = 7-5 = 2 a3 Pre-processing costs? Pre-processing costs? 2 3 3 3 2 4 5 3 b0' b1' 23 9 22

9 8 34 17 16 16 a0' b3' b2' 21 34 a1' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 22 12 33 12 18 25 18 18 15 49 31 22 30 32 21 20 20 33 29 18 18 14 14 0 35 21 29 19 18 13 0 12 34 22 19 28 15 17 0 12 15 17 17 17 17 8 0 5 5 7 22 19 15 10 0 34 12 27 21 0 22 23 13 7 14 19 16 15 18 0 10 16 9 4 14 8 7 5 7 3 5 6 6 4 0 2 0 4 2 1 1 3 56 a3 a2 a1 a0 b3 b2 b1 b0 a3' a2' a1' a0' b3' b2' b1' b0' a2' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a3' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b0 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 b1 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1

1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 22 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 a0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u similarly, similarly, rc(a2^b0)=15 rc(a2^b2)=19 rc(a2^b3)=14 rc(a2^b1)=16 rc(a2'^b2)=15 rc(a2'^b0)=18 rc(a2'^b3)=8 rc(a2'^b1)=19rc(a2^b3')=9 rc(a2^b2')=4 rc(a2^b0')=8 rc(a2^b1')=7rc(a2'^b3')=25 rc(a2'^b2')=18 rc(a2'^b0')=15 rc(a2'^b1')=14 a1 b b b b 3 2 1 0 a2 a a a a 3 2 1 0 a3 k Pre-processing costs? 2 3 3 3 2 4 5 3 b0' b1' 23 9 22 9 8 34 17 16 16 34 19 12 14 10 22 12 17 10 9 9 33 12 18 25 18 18 15 49 31 22 30 32 21 20 20 33 29 18 13 24 18 14 14 0 35 21 29 19 13 20 18 13 0 12 34 22 19 28 15 12 22 17 0 12 15 22 17 17 17 17 8 5 15 0 5 5 7 22 7 12 15 9 19 15 10 0 15 10 7 13 34 12

17 22 22 20 27 21 0 22 17 12 12 14 23 13 7 14 19 16 15 18 0 10 16 9 4 14 8 7 5 7 3 5 6 6 4 0 2 0 4 2 1 1 3 56 a3 a2 a1 a0 b3 b2 b1 b0 a3' a2' a1' a0' b3' b2' b1' b0' a0' b3' b2' 21 a1' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 a2' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a3' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b0 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 b1 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 a0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u similarly, similarly, similarly, similarly, rc(a0^b0)=9 rc(a1^b1)=22 rc(a1^b0)=20 rc(a0^b3)=7 rc(a0^b2)=12 rc(a0^b1)=15 rc(a1^b3)=17 rc(a1^b2)=22 rc(a0'^b0)=24 rc(a0'^b3)=15 rc(a0'^b1)=20 rc(a1'^b1)=13 rc(a1'^b0)=13 rc(a0'^b2)=22 rc(a1'^b3)=5 rc(a1'^b2)=12 rc(a0^b3')=15 rc(a0^b0')=13 rc(a1^b3')=17 rc(a1^b1')=12 rc(a1^b0')=14 rc(a0^b2')=10 rc(a0^b1')=7 rc(a1^b2')=12rc(a0'^b3')=19 rc(a1'^b3')=17 rc(a0'^b0')=10 rc(a0'^b1')=14 rc(a1'^b1')=9 rc(a1'^b0')=9 rc(a0'^b2')=12 rc(a1'^b2')=10 (16 additional AND operations were required for the mixed attribute pairs. The total was 28 ANDs) a1 b b b b 3 2 1 0 a2 a a a a 3 2 1 0 a3 k 2 3 3 3 2 4 5 3 b1' 23 9 22 9 8 34 17 16 16 34 19 12 14 10 22 12 17 10 9 9 33 12 18 25 18 18 15 49 31 22 30 32 21 20 20 33 29 18 13 24 18 14 14 0 35 21 29 19 13 20 18 13 0 12 34 22 19 28 15 12 22 17 0 12 15 22 17 17 17 17 8 5 15 0 5 5 7 22 7 12 15 9 19 15 10 0 15 10 7 13 34 12 17 22 22 20 27 21 0 22 17 12 12 14 23 13 7 14 19 16 15 18 0 10 16 9 4 14 8 7 5 7 3 5 6 6 4 0 2 0 4 2 1 1 3 56 a3 a2

a1 a0 b3 b2 b1 b0 a3' a2' a1' a0' b3' b2' b1' b0' a0' b3' b2' 21 a1' 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 a2' 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 a3' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b0 2 3 2 7 3 4 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 b1 5 6 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 b2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 b3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 1 1 a0 1 2 5 6 3 4 7 8 9 a d e b c f g h j i k l n m o U S T P Q p R O w v I J K L M G E C x y N H F z A D B q r s t u a1 b b b b 3 2 1 0 a2 a a a a 3 2 1 0 a3 k b0' With 4 aj^bj ANDs (i,j=3,2) plus the 12 intra-attribute ANDs required for TV-contouring, preprocessing, TV-contours plus 2-hi cell masks can be created by just plugging the right selection of the resulting rootcounts into a formula. For 3-hi cell masks how many would be needed (in addition to the 12 for TV contouring)? b0' Attributes and Complements b1' 9 22 9 8 34 17 16 16 34 19 12 14 10 22 12 17 10 9 9 33 12 18 25 18 18 15 49 31 22 30 32 21 20 20 33 29 18 13 24 18 14 14 0 35 21 29 19 13 20 18 13 0 12 34 22 19 28 15 12 22 17 0 12 15 22 17 17 17 17 8 5 15 0 5 5 7 22 7 12 15 9 19 15 10 0 15 10 7 13 34 12 17 22 22 20 27 21 0 22 17 12 12 14 23 13 7 14 19 16 15 18 0 10 16 9 4 14 8 7 5 7 3 5 6 6 4 0 2 0 4 2 1 1 3 56 a3 a2 a1 a0 b3 b2 b1 b0 a3' a2' a1' a0' b3' b2' b1' b0' b3' a0' b0 b1 b2 b3 a0 a1 a2 e.g., a3b2-triple rc slice card a3' a2' a1' A+A' e.g., a3-triple rc slice card 21 b2' 1 A+ A' 1 23 a3 dual rc card (the 104 black values shown below) A+A' We can think of the preprocessing as filling RoloDex cards (Note that this RoloDex is built to fit TV-analysis - i.e., 2-D cards with the primary one containing the needed dual-AND P-tree rootcounts needed for TV analysis (40 red and blue rc s below)

Recently Viewed Presentations

  • History of Communications Media - George Mason University

    History of Communications Media - George Mason University

    History of Communications Media Class 8
  • Iroquois Confederacy Chapter 4 How was the Iroquois

    Iroquois Confederacy Chapter 4 How was the Iroquois

    Grand Council - Decision Making Process. For serious matters and matters that affected the whole Confederacy, the people would turn to the Grand Council. Someone (often a clan mother) would inform the Onondaga chiefs of the issue or proposal. It...
  • Lecture 1: What is CV?

    Lecture 1: What is CV?

    Stanford Vision and Learning Lab. Today's agenda . Deep convolutional networks. ... Machine Learning (CS 229) Deep Learning (CS 230) NLP with Deep Learning (CS 224n) Convolutional Neural Networks (CS 231n) Don't think we've solved computer vision.
  • Children in care: Information for kindergarten teachers

    Children in care: Information for kindergarten teachers

    A companion document, L Downey 2010, Caring classrooms: A guide to understanding traumatised children and young people — for parents and the school community is available at the same page. Children in care
  • Reading Street - PC&#92;|MAC

    Reading Street - PC\|MAC

    spring crow Long o: oa, ow and three Letter Blends Teach/Model Word Reading: Phonics Songs and Rhymes Chart 21 Frame each of the following words on the Phonics Songs and Rhymes Chart whoa strong loads scrape splendid scratch roamed thrill...
  • Novel Investigation Techniques and Lessons Learned in ...

    Novel Investigation Techniques and Lessons Learned in ...

    HCV treatment is curative - Treat and Prevent. Large Clusters of Hepatitis C Viruses. HCV transmission is on-going. HCV networks involve HIV-infected and HIV-uninfected persons. Despite high burden of HCV infection - HCV prevention is needed . Novel, Direct HCV...
  • ESSENCE AND MORAL IDEAL OF NURSING - WordPress.com

    ESSENCE AND MORAL IDEAL OF NURSING - WordPress.com

    Meaning of Caring. Watson (1988) believes that human life is a gift to be cherished - process of wonder, awe and mystery, holds the view that humans are valued to be cared for, respected, nurtured, understood and assisted, as a...
  • Informal document No. GRRF-70-07 (70th GRRF, 12-13 May

    Informal document No. GRRF-70-07 (70th GRRF, 12-13 May

    Track safety marshals will help and lead the visitors. Please follow their instructions and stay inside the marked out areas. Take care when entering and leaving the vehicles, especially when leaving the truck or tractors (descend facing inwards) and wear...