LOCALITYPRESERVING PROPERTIES OF
SPACEFILLING CURVES
By
HUALI
Bachelor ofPhysics
Nanjing University
Nanjing, China
1989
Doctor of Philosophy
Nanjing University
Nanjing, China
1995
Submitted to the Faculty ofthe
Graduate College ofthe
Oklahoma State University
in partial fulfillment of
the requirement for
the Degree of
MASTER OF SCIENCE
May, 2002
LOCALITYPRESERVING PROPERTIES OF
SPACEFILLING CURVES
Thesis Approved:
_}cfuJJkJ
L~~.~>
D~€Jjl~aduate=
ii
ACKNOWLEDGMENTS
I would like to extend my sincere gratitude to Dr. H.K. Dai, my advisor, for his
guidance, ideas, and expertise in helping me to develop and complete this study.
Sincerely thanks to Dr. Heisterkamp for his support in computing facilities. Sincerely
thanks to Dr. Hedrick and Dr. Chandler for their patience, support and services as
members ofmy advisory committee.
This thesis is dedicated to my husband Eric. It's his love, support, encouragement,
and patienoe that have kept me motivated and escorted me through the years.
iii
Chapter
TABLE OF CONTENTS
Page
I. INTRODUCTION 1
II. SPACEFILLING CURVES 4
III. LOCALITY OF SPACEFILLING CURVES: SURVEY AND RELATED
WORK 7
IV. SIMULATIONS AND ANALySES................... 12
V. APPLICATIONS IN IMAGE PROCESSING 48
VI. CONCLUSION 55
REFERENCES " 57
APPENDIX 60
Source code <thesis.cpp> 60
<hilbert.h> , , 67
iv
Table
LIST OF TABLES
Page
1. Intercluster distance constants for three kinds of spacefilling curves VS. three
kinds of query shapes for twodimensional grid spaces. The first column is the
resu1t I.n 27x 27 gn'd space and the second'IS I.n 215 x 215 gn'd space , . 32
2. Ratios of intercluster distance among three kinds of spacefilling CU.lVes for three
kinds of query shapes on threedimensional grid spaces. The result is for
210 x210x210 grid _ , , , """ 33
v
Figure
LIST OF FIGURES
Page
1 Illustration of twodimensional spacefilling curves: (a) ZcUIve, (b) Graycoded
curve, (c) Hilbert curve 3
2 The first three steps of the twodimensional Hilbert spacefilling curve: (a) first
step, (b) second step, (c) third step. 7
41 Average number of clusters for twodimensional queries (exhaustive simulation
on 27x27 grid): (a) square queries, (b) circular queries, and (c) rectangular queries..... 15
42. Average number of clusters for twodimensional queries (sampling simulation
on 2'5 x 215 grid): (a) square queries, (b) circular queries, and (c) hyperrectangular
queries. 17
43. Average number of clusters for threedimensional queries (exhaustive
simulation on 26x26x26 grid): (a) square queries, (b) circular queries, and (c)
rectangular queries. 19
44. Average number of clusters for threedimensional queries (sampling simulation
on z1°x2'°x2 Io grid): (a) cubic queries, (b) spherical queries, and (c) hyperrectangular
queries. 21
45. Average query indexing ranges for twodimensional queries (exhaustive
simulation on 27x27 grid): (a) square queries, (b) circular queries, and (c) rectangular
queries 24
46. Average query indexing ranges for twodimensional queries (sampling
simulation on z1sxzl s grid): (a) square queries, (b) circular queries, and (c)
rectangular queries. . . .. . . .. . .. . . . . . .. . .. . .. ... ... . . ... 26
4.7. A:erage ~ue~y ~nd~xing rang~s for. threedimensio~al quer~es (exhaustive
sImulatlOn on 2 x2 x2 grId): (a) CUbIC quenes and (b) spherIcal quenes 28
4.8. A~erage ~uer~ i~~ex~ng range~ for ~hreedimension~l queri~s (sampling
sllTIulatlOl1 on 2 x2 x2 gnd): (a) CUbIC quenes and (b) spherIcal querIes 30
vi 
Figure Page
49. Average intercluster distances for twodimensional queries (exhaustive
sim~lation on 27x27 grid): (a) square queries, (b) circular queries, and (c) rectangular
quenes 35
410. Average intercluster distances for twodimensional queries (sampling
simulation on 215x215 grid): (a) square queries, (b) circular queries, and (c)
rectangular queries 37
411. Average intercluster distances for threedimensional queries (exhaustive
simulation on 26x26x26 grid): (a) cubic queries, (b) spherical queries, and (c) hyperrectangular
queries............................................................................... 39
412. Average intercluster distances for threedimensional queries (sampling
simulation on iOx210xio grid): (a) cubic queries, (b) spherical queries, and (c)
hyperrectangular queries. 41
413. Indexdifference versus taxi/cab distance on twodimensional grid (a)
exhaustive simulation on 27 x 27 grid and (b) sampling simulation on 215 x2 15 grid ..... 45
414. Ratio of the indexdifference versus taxi/cab distance on twodimensional grid
(a) exhaustive simulation on 27 x 27 grid and (b) sampling simulation on 215x215 grid. 46
415. Indexdifference versus taxi/cab distance on threedimensional grid (a)
exhaustive simulation on 26x26x26 grid and (b) sampling simulation on
2Iox210x210grid 47
416. Ratio of the indexdifference versus taxi/cab distance on threedimensional
grid ,\a) exhaustive simulation on 26x26x26 grid and (b) sampling simulation on
2 10x2 0X210 grid 48
51. (a) A deer image applied Hilbert spacefilling curve scanning, (b) Autocorrelation
of the three scanned images under three families of spacefilling curves
and rowbyrow scanning , 53
52. Autocorrelation of the three scanned images under three families of spacefilling
curves and rowbyrow scanning, in which the image is 200 randomly placed
squares of S.Ize 8x8 on 210 x 2'0 gn'd' . 54
vii 
CHPATERONE
INTRODUCTION
\ . Ii Ih
Indexing of multidimensional data has been the focus of a considerable amount of
research effort over many years but no generally agreed paradigm has emerged to
compare with the impact of Btrees, for example, on the indexing of onedimensional
data. Gaede and Gunther [GG98] gave an extensive review of multidimensional access
methods. At the same time, the need for efficient multidimensional indexing methods is
ever more important in an environment where databases become larger and more
complex in their structures and aspirations for extracting valuable information become
more sophisticated.
Mapping multidimensional data to one dimension, enabling simple and wellunderstood
onedimensional access methods to be exploited, has been suggested as a
solution in the literature by FaLoutsos [FaI8o][FS89]. One way of implementing such a
mapping is to utilize spacefilling curves. For a historical account of classical spacefining
curves, we could refer to Sagan's book [Sag94].
A spacefining curve is a linear traversal of a discrete finite multidimensional space,
thus it passes through every point in a space once so giving a onetoone correspondence
between the coordinates of the points and the onedimensional sequence numbers of the
curve. Spacefining curves were a topic of interest for mathematicians in the late 19th
1
.; :
century. The first graphical representation of spacefilh 19 curve W.1S giv.::n by Hilbert
[Hi1l891].
Several mapping functions have been proposed in the titer~lurc_ One based on
interleaving bits from the coordinates, which is called Zordering, was proposed by
Orenstein [Ore86). Its modification was suggested lly Faloutsos [FaI8()~ using Gray
coding on the interleaved bits. A third mapping method, based on Hilbert spacefilling
curve. In a mathematical context, these three mapping functions are based on different
spacefilling curves: Zcurves, the Graycoded curves and the Hilbert curves. Figure I
illustrates the linear ordering yielded by the spacefilling curves for a 4x4 grid. More
information on the will be presented in the next chapter.
2
(a) (b)
(c)
Figure 1. Illustration of twodimensional second order spacefilling
curves: (a) Zcurve, (b) the Graycoded curve, (c) the Hilbert curve.
3
\ lh.~
CHPATERTWO
SPACEFILLING CURVES
For positive N, denote {1;",N} by (N]. A discrete mdimensional spacefilling
curve of length N n is a bijective mapping C : [Nil] ~ Nn
, thus providing a linear traversal
ordering of the grid points in [N'l]. An mdimensional grid is said to be or order k if it has
size N = 2k
; a spacefilling curve has order k if its codomain is a grid of order k. The
generation of a sequence of multidimensional spacefilling curves usually follows a
recurSIve process.
Although it was G. Peano who discovered the first spacefilling curve, it was
Hilbert who made this phenomenon of surfacefilli.n.g curves luminous to the geometric
imagination. Hilbert in 1891, first recognized a general geometric procedure that allows
the construction of an entire class of spacefilling curves [Hi1l891]. Thereupon he
proceeded to promulgate the following heuristic principle: If the interval I can be mapped
continuousJy onto the square S, then after dividing I into four congruent subintervals and
S into four congruent subsquares, each subinterval can be mapped continuously onto one
of the subsquares. Next, each subintervals is, in tum, partitioned into fOUT congruent
subintervals and each subsquare into four congruent subsquares, and the process is
repeated. If this is carried on infinitely, I and S are partitioned into 22n congruent replicas
for n = 1,2,3, ... , oq Hilbert proved that the subsquares can be arranged so that adjacent
subintervals correspond to adjacent subsquares with an edge in common, and so that the
inclusion relationships are preserved, that is, if a square corresponds to an interval, then
4
its subsquares correspond to the subintervals of the interval. Figure 2 illustrates how the
process is to be actualized for the first three steps. The generalization of a threedimensional
Hilbert curve was described in [Jag90][Sag93]. A generalization of the
Hilbert curve, in an analytic form, for higherdimensional space was given in [But69].
Sagan [Sag94] gave the definition of the Hilbert curve as follows: Every tEl is
uniquely determined by a sequence of nested closed intervals (that ~are generated by out
successive partitioning), the lengths of which shrink to O. With this sequence corresponds
a unique sequence of nested closed squares, the diagonals of which shrink into a point,
and which define a unique point in the square S.
Zcurve is based on Zordering, proposed by Orenstein [Ore86], which is based
on interleaving bits from the coordinates. For amdimensional Zcurve has order k, grid
sI•ze.IS N = 2k'. Sa m. b'mary code, we use the .l:1.01o1w'mg notati.on C k I k 2 lOt I CI .. .cIC / a
represent the Ith coordinate, where 1~ 1 ~ m and each small c is 0 or 1. Then the index is
constructed from interleaving bits from the coordinates
In the Graycoded curve, the index is generated from applying Gray coding on the
index under Zordering. There is one simple way to implement Gray coding is
performing XOR between the original index and its onebitrightshifted version.
Here in thesis, we will focus on these three families of spacefilling curves and try
to do some work on the locality properties which we will discuss in the next chapter.
5
(a)
I I
i I
rl !,
I
1
! :
! ,
II i
!I
II
I
I
,
~~
(b)
(c)
Figure 2. The first three steps of the twodimensional Hilbert spacefilling curve:
(a) first step, (b) second step, (c) third step.
6
CHAPTER THREE
LOCALITY OF SPACE,FILLINGCURVES:
SURVEY AND RELATED WORK
tuJ .)1
. ·HI! \ . \'
Spacefilling curves are useful in applications where a traversal (scan) of a multidimensional
grid is needed. Some algorithms perfonn ,local oomputations on
neighborhoods, or exploit spatial correlation present in data, so the preservation of
"locality" is required. By "locality", we mean that the traversal reflects proximity
between the points of [NY''', that is, points close in [NY" are also close in the traversal
order, and vice versa.
The localitypreserving properties of spacefilling curves arc used for efficient
algorithms in various fi.elds of computation (for examples, data organization in multidimensional
or geographic databases, data compression, image manipulation and
compression, computational geometry problems, and parallel computation). In Moon et
at.' s work [MSFO1], they listed several categories in which applications benefit from
linear mapping that preserves locality and also some related references were given out.
Clustering, one of the most desired locality properties, means the locality between
points in multidimensional space is also kept in the linear space. A cluster is a set of grid
points that are consecutively connected by a mapping curve. In tenns of multidimensional
database indexing, all the points within the query range that have
consecutive indices win be considered as a cluster.
Under linear mapping, each grid point in multidimensional space is given a new
index in onedimensional coordinate system. It is shown that under most situations, the
linear mapping based on Hilbert spacefilling curves perform better than the others in
7
preserving locality [Jag90nMJFOl]. Much work on empirical and analytical studies of
clustering effect of the spacefilling curves have been reported in the literature (see
[Jag90], [Jag97], [RF91], and [MJFOI] for details.)
Jagadish [Jag90] compared the clustering properties of several spacefilling curves by
considering 2x2 range queries. Rong and Faloutsos [RF91] derived a closedfonn
expression of the average number of the clusters for Zcurves. Jagadish [Jag97] derived
closedfonn expressions of the average number of clusters for the Hilbert curves in a twodimensional
grid, but only for 2x2 and 3x3 query regions.
Results are generalized in [MJFOl]. Moon et al. analyzed the clustering property of
Hilbert spacefilling curves by:
(l) Giving an asymptotic formula for the clustering property of Hilbert spacefilling
curves for general polyhedra in a multidimensional space.
(2) Derive a closedform, exact fonnula of the number of clusters within query region
of size 2k x 21< in a twodimensional grid space of order n.
Both the asymptotic solution for the general case and the exact solution for a special
case generalize previous work in pag90]. They agreed with the empirical results that the
number of clusters depends on the hypersurface area of the query region and not its
hypervolume. This works shows that the Hilbert curves achieve better clustering than Zcurves
and the Graycoded curves.
Although the Hilbert curves are superior to Zcurves and also the Graycoded curves
on clustering properties, however clustering is only one of the metric of localitypreserving
properties. Besides the clustering measure, there are a few locality measure
have been proposed and analyzed for spacefining curves in the literature. Denote by d,
8
~

dj , and d"", the Euclidean, taxicab, and maximum metrics, respectively. Let (! denote a
family of mdimensional curves ofsuccessive orders.
For quantifying the proximity preservation of closeby points in the mdimensional
space [n]m, [PKK.92] employ an average Locality measure:
'"' lijl LpKK(C)= LJ ..
i ,jerl/'" IIi <j d (C (1 ),C (j» for C E (!
Mitchison and Durbin [MD86] use a more restrictive locality measure parameterized
byq:
LMD,q(C)= L lijlq
i ,j ern'" land d (C (i ).C (j »=1
to study optimal 2dimensional mappings for q E [0, I].
for C E (!
For measuring the proximity preservation of closeby points in the indexing space
[nnl], Gotsman and Lindenbaum [GL96] consider the following measures:
. d(C(i),C(j»'"
LcL,rnin(C)= mIll .. ,and
i,je[II"'lli<j 11./1
d (C (i ),C (j »/11
LCL,rnax (C) = max I" I for C E (!
i,je[l/"' Ili<j 1 .J
They show that for arbitrary mdimensional curve C,
LOl, mineC) = O(n Jm), and
L (c»(zm l)(l!Y' GL.max n
For the mdimensional Hilbert curve family {H;' Ik = 1,2, ... }, they prove thait
In
LGL,max (H;' ) .::; 2m (m + 3) 2 •
For the twodimensional Hilbert curve family, they obtain tight bounds:
9
1

( " . , .
Furthermore Dai et a1. [DS02] present an analytical study of the locality properties of
the mdimensional korder discrete Hilbert and Zcurve families, (H;' Ik = 1,2, ... }, and
1
{Z ~n I k = 1,2,... }, respectively, based on the following locality measure Ls that
cumulates all the indexdifferences between pointpairs at a common. taxicab distance {},
which is similar to LMD.J conditional on a taxicab distance of 0 between points in [nt.
Lo(C)= L lijl
i,jE[II'" Jli<jand d ,(C(i).C(j»=O
They derived the exact formulas for Ls(H;' ) and Ls(Z ;J) for In = 2 and arbitrary 0
that is an integral power of 2, and m = 3 and (j = 1. The results yield a constant
L/}(H;' )
asymptotic ratio limk .....", III ) > 1, which suggests that the Zcurves perform better
Lo(Z k
than the Hilbert curves.
Besides the clustering properties, we will have interest in other locality properties,
such as intercluster distance, query indexing range, and indexdifference we've
mentioned above. By intercluster distance, we mean the index space between two
neighboring clusters. Query indexingrange means the index range the region query
covers. We find the largest index and smallest index inside the query region, then subtract
these two indices, and the result is the query indexing range. Interduster and query
indexing range will be both collected via region queries. While indexdifference can be
got through point queries. In chapter 4, we win present the simulation results and
analyses of all these locality properties. We will also apply different query shapes on
10
L
lowdimensional grid spaces. Our empirical study attempts to find out how these three
families of spacefilling curves will behave, together with plausible explanations.
Spacefilling curves are attractive to many imagespace algorithms that are based on
the spatial coherence of nearby pixels. The resulting sequence of pixels is processed as
required by the particular application. For instance, the sequence may be compressed
using lossless or lossy compression, it may be processed for haIftoning, analysis, pattern
recognition or texture analysis, and it may be converted into an analog form and be
transmitted through channels with limited bandwidth. To obtain the image after
processing, the pixelsequence is placed back in a frame along the same spacefilling
curve. In the above applications and others, it is important that the intraframe correlation
in the image translates to a favorable autocorrelation per) within the pixelsequence in
which per) = E(f(x)f(x+r)), E means the expectation over pixel index x, r is the distance
between two pixels and f(x) is the function of scanned image (f(x) is of value 0 for white
pixel and 1 for black pixel in binary images).
As an example of application of spacefilling curves on image processing, we will
make comparisons between the onedimensional representation of images that are
scanned along the three families of spacefilling curves. This will be presented in chapter
5.
11

CHPATER FOUR
SIMULATIONS AND ANALYSES
To obtain the average intercluster distance, it is required that we compute the mean
intercluster distance within a query region at all possible positions in a given grid space.
Exhaustive simulation runs allow us to approach the exact result of the average intercluster
distance versus the side length of the query region. For circular query and
spherical query, side length refers the radius. In addimensional N x N x ... x N grid
space, the total number of distinct positions of addimensional k x k x ... x k hypercubic
query is (N  k + l)d . For query shapes, we consider squares, rectangles, and circles for
twodimensional cases. Here we chose the two sides of the rectangle to 0.5 and 1.5 of the
side length. Cubes, hyperrectangles, and spheres are query shapes for threedimensional
cases. We chose the three sides of the hyperrectangle to be 0.5, 1.667, and I of the side
length.
To obtain the relationship between the Euclidean metric for onedimensional space
and taxi/cab (Manhattan) metric for multidimensional space, it is necessary that we
average indexdifferences for all possible pointpair queries with a given taxi/cab
distance. Such exhaustive simulation runs allow us to approach the exact result of the
average indexdifference versus taxi/cab distance.
In a twodimensional N x N grid space, the total number of distinct positions ofpointpair
queries with taxi distance (, is approximately (N  (j + Il(5 + J). In a threedimensional
N x N x N grid space, the total number of distinct positions of pointpair
12
queries with taxi distance 0 is approximately (N  0 + 1i (0 + 1) (0 + 2)12. In a ddimensional
N x N x ... x N grid space, the total number of distinct positions of a ddimensional
pointpair query is approximate~y (N  k + l)d 0 dlI(dl)!.
Consequently, for a large grid space and a high dimensionality, each simulation run
may require processing an excessively large number of queries, which in tum makes the
simulation timeconsuming. Thus, for large grid spaces, we carried out statistical
simulations by random sampling of queries. For small grid spaces, we perfonned
exhaustive simulations. Simulations are performed on twodimensional and threedimensional
grid spaces.
The first set of experiments was carried out in twodimensional grid spaces with size
27x27 and 215xi5
• For 27x27 grid, we perfonned exhaustive simulations, and for 215xi 5
grid we carried out sampling simulations. The second set of experiments was carried out
in threedimensional grid spaces with size 26x26x26 and 2lOxioxio. For 26x26x26 grid,
we perfonned exhaustive simulations, and for 210xiox21O grid we carried out sampling
simulations.
Results and Analyses on Average Number of Clusters
Figures 41 to 44 present the average number of clusters for square, rectangular, and
circular queries on twodimensionaI grid spaces, and cubic, hyperrectangular, and
spherical queries on threedimensional grid spaces.
The results of average number of clusters comply with those of Moon et a1.'s work
[MJFOI). The Hilbert curves perform the best on the clustering properties under aU
dimensionality and query shapes considered. In twodimensional grid spaces, for square
queries and rectangular queries, Zcurves and the Graycoded curves perform almost the
13
same; for circular queries, Zcurves achieve better clustering properties than the Graycoded
curves. In threedimensional grid spaces, the Graycoded curves outperfonn Zcurves
for all query shapes.
The average number of clusters depends on the hypersurface area of the query region
[MHFOl]. For the twodimensional case, the average number of clusters is a linear
function ofthe side length, for the threedimensional case, it is a quadratic function of the
side length. The Hilbert curves is superior to the other two spacefilling curves on the
clustering properties.
14
15
Average number of clusters (Grid: lx27
)
80 • Hilbert_rectangularll.5xO.5)
70 6 Gray_rectangular (1.5xO.5) ~ (I)
~ Q) ~ Z_rectangular (1. 5x 0.5)
.JJ 60
If)
~
rI
0 50
4l ~
0 ~
~ 4.0
(l)
~ ~ . ~
~ •• • ~ 20 ~ •• • III
H ~ • ,(jJ ~ .. ~ 10 ••
~ • 0
0 5 10 15 20 25 30 35
The side length of query
(c)
Figure 41. Average number of clusters for twodimensional queries
(exhaustive simulation on 27x27 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries.
16
17

Average number of clusters (Grid: iSxis)
80 • Hilbert_rectangular (1. 5x 0 .5)
en 70 b. Gray_rectangular (1. 5x 0.5)
~ 0> + Z_rectangular(1.5xO.5) .w 60 II)
::1
.l
U 50
lH
0
~ 40 i 30 •• ~ •• • (])
tJ'I 20 •• • cd
~ ~ •• • OJ
~ 10 •• • ~Q
0
0 5 10 15 20 25 30 35
The side length of query
(c)
Figure 42. Average number of clusters for twodimensional quenes
(sampling simulation on z15 x215 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries.
18
Average number of clusters (Grid: t x26 x26 l
• Hilbert cube
6. Gray_cube
(/) 2000 + Z cube + ll
(]) .w +
(/)
:::J + 6,
.\ 1500
0 1\
'H $
0 6.
ll
1000 i $6. • $ f:J. • $/:). • $6. • • (])
tyI 500 ~6. • ((\
 .. ll <lJ .a • • ~
0 ••
0 5 10 15 20 25 30 35
'The side length of query(s)
(a)
Average number of clusters (Grid: t X 26x l)
1200 • Hilbert_sphere
6. $ Gray_sphere
(/) + Z_sphere f:J. ll 1000 ..
(])
.jJ (/) $
;:l
.I 800  1\ • 0
~0
$
ll 600 /~ •
i 400 ~ • C
~ ~ • ((\ ll 200 • • g: •
.::x: i
o • $
I I I
0 2 4 6 B 10 12 14 16 18
The side length of queries I
(b)
19

Average number of clusters (Grid: 1x 26x 26
)
2600 • Hilbert_hyperrectangle(0.5x1.667xl) , 2400 6. Gray_hyperrectangle (0 . 5x 1 . 667x 1) •
(f) 2200 + Z_hyperrectangle(0.5xl.667x1l + Il
(]) 2000
~ " + 6 (f)
::J 1800
rl + f:::.
0 1600
4J 1400 +6
f:::.
0
Il 1200
(]) +L
~ 1000 +6 • • 800 +6. • ~ 600 ~6 ••
eu l, •• Il 400 ! . (]) •• ~ 200
0 $$$$
200
0 5 10 15 20 25 30 35
The side length of query(s)
(c)
Figure 43. Average number of clusters for threedimensiunal queries
(exhaustive simulation on 26x26x26 grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
I
20

Average number of clusters (Grid: iOxiox210)
• Hilbert cube
6. Gray_cube
~
(fJ .~ ~ Z cUte $
ill
+J
(fJ 1500 ~ ;J
rl 6 0 $
4l ;:.,
0 $
1\ ~ 1000 •
i $6. • $ 6. • l:: $6. • • ~ 500 6. •
ru
•• tt O:
•• ~ ~ ••
0
0 5 10 15 20 25 30 35
The side length of query (s)
(a)
Average number of clusters (Grid: iOxioxiol
3400
3200 • Hilbert_sphere
3000 t::" Gray_sphere $
0;.;1,
(fJ 2800 $ Z_sphere 6. ~' ~
ill 2600 $
.jJ
[/) 2400 A
~
:J rl 2200 $ • 0
~ 2000 ii 4al ~ 1800 • $..j 1600 /',
i ~ $ • 1400 ~ 1200 '"' •
l:: 1000 • ~ 800 ' ~ • III 600 ~ • $..j
ill 400 • ~
200
0 $ $
200
0 2 4 6 B 10 12 14 16 18 20 22 24 26
The side length of queries 1
(b)
21

Average number of clusters (Grid: iOxiox2ul)
2200 'II
2000 • Hilbert_hyperrectangle(0.Sxl.667 x l)
6 Gray_hyperrectangle(O.5xl.667 x l)
til 1800 $ Z_hyperrectangle(0.5xl.667 xll
ll $
OJ
.j.J 1600
til $ :::l
rl 1400 0 + ~ ~ 1200 t\ 0 $
ll 1000 ~ • OJ $6 •• ~ 800 ~6 • $~ •
OJ 600 tJ1 +66.· • ({1
ll 400 I
~ • ri:t: 200
0
0 5 10 15 20 25 30
The side length of query(s)
(c)
Figure 44. Average number of clusters for threedimensional queries
(sampling simulation on 210xiox2 1O grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
22
Results and Analyses on Que'ry Indexing Range
We also collect the average query indexing range during the simulation, which means
the difference between the indices of the two grid points with the. smallest index and the
largest index inside a query region. Figures 45 to 48 present the average query indexing
ranges for square, rectangular, and circular queries on twodimensional grid spaces, and
cubic, hyperrectangular, and spherical queries on threedimensional grid spaces.
We can see from those figures that the average query indexing range is nearly a linear
function of the side length of the query region in both twodimensional and threedimensional
grid spaces. We apply the linear fit, which fits quite well with the
experimental results especially in larger grids with size Z15 xZ15 and Z'ox210x2 1O. We can
also see that the query indexing range depends not only on the side length of the query
region, but also on the size of the grid space. The query indexing range increases with the
growing size of the grid space. Besides the query indexing range is related to the query
shape.
The Graycoded curves have the largest average query indexing range for all the
query shapes. Except twodimensional rectangular queries, Zcurves have the smallest
average query indexing range, and the Hilbert curves are in between.
Generally speaking, Zcurves are the best on the query indexing range propeliy.
23
I'
7000,.....,
A . d . (Gr1.'do. 21X 21
verage query 1.n eX1.ng range )
Hilbert_square
Gray_square
Z_square
5000
3000
4000
~
IV §. 2000
~e 1000
(])
~
6000 [
~
.~
'8,,j

o
o 5 10 15 20 25
The side length of query
(a)
30 35
Average query indexing range (Grid: i X 21
)
14000 ___.
o
e Hilbert circle f\
/::,. Gray_circle D. e
• Z circle 6 e •
6e.
6e.
L:.e.
6e.
L. e. I\e.
l. e. L/:, .e + 4000
2000
8000
6000
10000
12000 tH
U>
.~
~
~
~
.f
o 5 10 15 20 25
The side length of query
(b)
30 35
I
24
Average query indexing range (Grid: ZX 27
)
10000
9000 • Hi1bert_rectangular(l.SxO.SP
I
.6. Gray_rectangular (l.SxO.S) D
QJ
b'> BOOO ' ~ Z_rectangular(l.SxO.S) D
~
~ H 7000 .6. bc':> 6
.I 6000 6 ~
~ ~ 6 $
5000 6 $
~ .6. $. >. 11000 A $~  H I::. $ •• QJ
~ 3000 L:. ~ ••
(j) 6;**· b'> 2000
10 6. HI
~ 1000 • ~
0
0 5 10 15 20 25 30 3J
The side length of query
(c)
Figure 45. Average query indexing range for twodimensional queries
(exhaustive simulation on 27x27 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries.
25
J
6. •
Hilbert_square
Z_square
Gray_square
n"..verage query l'.ndexu. lg range \'Grl.',d_ L,J.5x215,\ .•
400000
200000
1600000
~ 1400000
b' c:
.~
~
·04
~&
~
(I)
~
. d . (Grl.'d·. ,J.sx21S
Average query lil eXlng range L )
• Hilbert circle
35
•
~
30
t\
1\ • 6 • 6. • ~
6. • ~
6 .~
~
;, • ~ •~
~ ~
15 20 25
length of query
(a)
5 10
The side
/\ Gray_circle
~ Z circle
a
~ 3500000
~
ll 3000000
b'
C 'Q 2500000
~
.~ 2000000
:>;
~ 1500000
§.
OJ 1000000
b'
rU
~ 500000
~
o
4000000
o
a 5 10 15 20 23
The side length of query
(b)
30
26
Average query indexing range (Grid: i 5xi5
)
2400000 • Hilbert_rectangular (1. 5>< 0.5)
2200000 ~ Gray_rectangular(1.5x O.5) it
(11 ..
tJ'l 2000000 + Z_rectangular(1.5x O.5)
~
~ 1800000 1\.
l:J' 6 .;i 1600000 6 ,
~ 1400000 f'::. (l) "d 6
l:: 1200000 f::" ·rl
,f::" D • G 1000000 aa
aJ 6 • __ g, 800000 f::"
600000 f::"
~ f::" tt cU 400000 .6.* ~
(IJ ~ 200000 w~·
0 ,
0 5 10 15 20 25 30 35
The side length of query
(c)
Figure 46. Average query indexing range for twodimensional queries
(sampling simulation on 21Sxi5 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries.
27
Average query indexing range (Grid: t x26x26 )
260000 l • Hilbert cube
240000 I 6
6 Gray_cube
(l) • tJ' 220000 l • Z cube 6 • ~ 200000 l • H 6 •
tJ' 180000 l • l:: /:; • rl 160000'1 •
~ J); • 140000 l • c: ll. • rl 120000 ll. S
:>. 6 I
H 100000 ll. I (l) g. 80000 I i 60000 l i ~ 40000 •i
H (l) • 20000 ~ • 0 • ....
20000 • I :(,
0 5 10 15 20 25 30 35 =t:
~
The side length of query(s) ~'
(a) ru
~
1x 26x26
)
l.ti
Average query indexing range (Grid: (g'
250000 ~ • Hilbert_sphere 6. ,
6. Gray_.sphere : C5 ([)
tJ' 200000 • Z_sphere ~
~ b.
tJ' 3 l
.S 150000 1\ tf
~ 3 ~
~ < C { ,
•..j
>. 100000
H
([) g.
~ 50000
R.1 ~
H~
• 0
0 2 6 8 10 12 14 16 18
The side length of queries
(b)
28
n7\., verage query l•lldex.l.llg range (Gn'c.t: L$x26X26)
250000 f",,
Figure 47. Average query indexing range for threedimensional queries
(exhaustive simulation on iX26x26 grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
150000
...
• Hilbert_hyperrectangle (0.5><1. 667>< 1)
/\
6. Gray_hyperrectangleIO.5><1.667>(1) • Z_hyperrectangleI0.5><1.667>(1)
1\
I:;.
I:;. • I:;. • I:;. • I:;. • I:;. • !\ •
/). • 1\ *
~
~
• •
0 5 10 15 20 25 30 35
The side length of query(s)
(c)
[ 200000
~
(]) g.
o
tJ1 c:
·rl
.>g:: 100000
c:
·rl
~ 50000
I'll
H
~
i:l::
29

Hilbert cube
Gray_cube
Z cuI:le
5000000
10000000
25000000
30000000
20000000 
~
15000000
~
~
~
o
40000000
Q) 35000000 [
g'
•..1
~
•..1
. ,.+0 10 10 Average query indexing range (Gnd: L ><2 x2 )
10 15 20 25 30 35
The side length of query (s)
(a)
o 5
70000000 • Hilbert_sphere
L:,. Gray_sphere /':"
(I)
~ 60000000 ' $ Z_sphere /:., • A. • <$
~g
50000000 I 6, • <$
Xn 6, : <$
~ 40000000 i 6, : s:: Je. , rl
~ 30000000 , ~
Q)
g. 20000000
~ !.'
~ 10000000 ~ • Q)
~ $
0
0 2 4 6 8 10 12 14 16 18 20 22 24 26
The side length of queries
(b)
30

•
10 15 20 25 30
The side length of query(s)
(c)
5
• Hilliert_hyperrectangle (0. 5x1. 667)( 1)
b. Gray_hyperrectangle (0 :5)( 1. 667x 1)
$ Z_hyperrectangle (0.5"1.667,. 1)
o
60000000 i
([) 55000000
·01
.~ 50000000
Il
:>, 45000000
Il
g(lJ. 40000000
01
35000000
c: . .j 30000000
~
~ 25000000
c: . .j 20000000
~ 15000000 ro
Il
(lJ 10000000
~
5000000
0
Figure 48. Average query indexin~ range for threedimensional queries
(sampling simulation on i Oxiox2l grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
31
Results and Analyses on Average Intercluster' Dista!lce .q
Figures 49 to 412 present the average query indexing range for square, rectangular,
and circular queries in twodimension~l grid spaces, and cubic, hyperrect~guLar. and
spherical queries in threedimensional grid spaces.
In twodimensional grid spaces, the intercluster distance approaches constant with
the growing side length of the query region. In Table 1 we list; the constants of the
average intercluster distance for three families of spacefilling curves. The constant
depends on the size of the grid space, the query shape, and the kind of spacefilling
curves. The average intercluster distance is larger for largersized grid space.
Table 1. Constants of a.verage intercluster distance for three kinds
of space filling curves vs. three kinds of query shapes for twodimensional
grid spaces. The first column is the result in 2')(2'
grid space and the second is in 2 15 )(2 15 grid space.
Hilbert curve Graycoded curve Zcurve
Square 150 40,000 85 25,000 64 16,800
Circle 140 56,000 80 32,000 73 30,000
Rectangle 130 35,000 80 25,000 70 D,OOO
In threedimensional grid spaces, the average intercluster distance decreases with the
growing side length of query region. In Table 2 we list the ratios of the average intercluster
distance among three families of spacefilling curves. From these figures and
Table 2, it seems that the ratios approach a constant with the growing side length of the
query regIOn.
32


Table 2. Ratios of the average interc1u~ter distance ~ong
three kinds of spacefilling curves for three kinds  of
query shapes on threedimensional grid spaces. The result
is for 210)(210x210 grid.
Hilbert over Graycoded Graycoded over Z
Cube , 1.4 1.42
I
Sphere 1.2 1.3
Hyper 1.3 1.3
rectangle
iC
f
So on interduster properties in both twodimensional and threedimensional grid
spaces, Zcurves perform the best, the Hilbert curves are the worst, and the Graycoded
curves in between.
Let N denote the number of all possible ddimensional query regions with side length
L. Suppose for the i th query, the query indexing range is Rj , and the number of clusters is
N
LCRj _Ld
)
C, in which i E U, 2, ...J N}. Then the average intercluster distance is ,i~"7~: , In Lee; 1)
1=1
which Ld is the number of grid point within the query region, and Cl l is the number of
intercluster segments for the i th query region. Compared with query range Rj , Ld is so
small for large grid space, and the average intercluster distance is approximated by
N
LRi NR 
...!..=.!. == =R Ie in which Rand C are the average query indexing range and
N NC ' ICj
;=1
average number of clusters respectively.
In the earlier section we've noticed that R is approximately a linear function of the
side length of the query region from the simulation runs. For the twodimensional case,
33
...

C is a linear function of side length of the query region [MJ~Ol]; t~e average intercluster
distance approaches constant in twodimensional grid spaces. In threedimensional
grid spaces, C is a quadratic function of side length of th~ query region
[MJFOI]; the intercluster distance decreases with the growing side length of the query
reglOn.
34

Average intercluster distance (Grid; ixii
)
250 ~ •
Q)
() b..
~
+J ~
til 200 ~ :B
Hilbert_square
Gray_square
z_square
100 ~
ll
2
til J.50 ~
~
()
~2
.;l
••••••••••••••••

35
••••••••••• •••••
• Hilbert circle
b.. Gray_circle
~ Z circle
Average intercluster distance (Grid: i x 21
)
0''''..... .......'......._..·.....·......'............'.......'
o 5 10 15 20 25 30
250
The side length of query
(a)
ll
Q) .w
~ 150
rl
UI
ll
OgJ 100
·rl
~
rtI
ll 50
()) ,g;
OLL..............."'..... .............. ..........
o 5 10 15 20 25 30 35
The side length of query
(b)
35
Average intercluster distance (Grid: 2x 21
)
250 ~ • Hilbert_rectangular (1. 5>< 0.5) I ~
OJ b. Gray_rectangular (1.5><0.5) 0 :
~ $ Z_rectangular(1.5><0.5) •
+J 200 ~
ll) :a 6.
H
OJ 150 l +J
ll) ::1 •••••••••••••• .; • 0 f::::.6.b" IH
100  b"b"b"b.b.b.b"b"b"b,,6. OJ
.+SJ $ $$$$$$$$$$$$$$$
~
ro 50 
H
OJ
~
0 • • •
D 5 10 15 20 25 30 35
The side length of query
(c)
Figure 49. Average intercluster distance for twodimensional queries
(exhaustive simulation on 27x27 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries.
36

Average intercluster distance (Grid~ iSx is)
70000...,
120000 ......
Average intercluster distance (Grid: i 5xi5
) ._.
35
Hilbert_squa.re
Z_square
Gray_square
j.
~L
$@~~$~~~$$$~$
I:::. 6. 6. ~ 6. I:::. 6. I:::. I:::. L t~ D ,t;,., 6. 6.
$$$$$$$$$$$$$$$$
• • • • • • • • • • • • • •
••••••••••••••••
6.
• Hilbert circle
I:::. Gray_circle
$ Z circle
5000 ..
o .....1..... 1..... 1.....'1.11 .11.11 .'
o 5 10 15 20 25 30
20000 
80000 ~
40000 
60000 
30000
90000 ..
50000 
70000
35000
40000 
55000
50000 
• 60000  •
6.
25000 ..
30000 ..
10000 f
15000 ..
110000
100000
~ 20000 fro
H
OJ
~
~ 45000
.j..J
OJ
::l
rl oIH
OJ
.j..J
~
·rl
OJ 65000
o
~
.j..J
OJ :a
The side length of query
(a)
H
OJ
.j..J
OJ
:=1 oIH
OJ
is ·rl
~
ro
H
OJ
~
a
10000 ...........__.......' &....__... 1 11. 1 __..111.1
5 10 15 20 25 30
The side length of query
(b)
37
t
A . t 1 di' (Gr;d"" ..J!5 x 215
ve.rage. ~n ere uster stance ) .L L
• Hilbert_rectangular {I. 5x 0 . 5)
.6.. Gray_rectangular (1.5x O.5)
$ ZJectangular(1.5x O.5)
10 15 20 25 30 35
The side length of query
(el'
5
•••••••••••••••
!:::,.6...6...6.. •
o
65000 ,
60000 i
QJ
U 55000 ~
+J (f) 50000 :a 45000
~
QJ 40000 +J
(f)
:J 35000 ,1
UI
~ 30000
QJ
+c:J 25000
''';
QJ 20000
tJ'1 ro 15000 ~
QJ
~ 10000
5000
,
Figure 410. Average intercluster distance for twodimensional queries
(sampling simulation on 215 x2 15 grid): (a) square queries, (b) circular
queries, and (c) rectangular queries. 
38
•
Average intercluster distance {Grid: 1x26x26
)
1600 ~ • Hilbert cube
(J) ..' ~ .• lJ. u Gray_~
~ 1400 ~ .wco lJ. • Z cube
B 1200 ~.
~
(J) .cwo 1000 i ••
::l
.;
UI
800 t H lJ.
(J) .cw • .1 600 I
~6..
~ 6 ro 400 I ~ • 6·. ~ .~66! ••
~::@:: ri:I::
200  ~ ..~~
• • . I I 0
0 5 10 15 20 25 30
"
35
~
The side length of query(s) .....,,
;)
(a) 3
U
I)
1x26X 26
)
..,.
Average intercluster distance (Grid: U
6 1400 l • • Hilbert_sphere SQ)
b. Gray_sphere § 0
~ 1200 !:" • Z_sphere i3 lJ
~ . :(a/) .;.:.1'
1000 .
ll • 3= Q)
+J .... f/) 800 l ll.'> ;:J rl • .~
0I
L::,
ll 600  Q)
+J c:: • •
..I /\
400  • ~ • /::., ~ ~ • • ~ : : ll Q) 200 ~
~
• . I I • 0
0 2 4 6 8 10 12 14 16 18
The side length of queries
(b)
39
Average intercluster distance (Grid: tx 26 x 26
)
2000,......_
10 15 20 25 30 35
_ Hilbert_hyperrectang1e(0. 5x 1. 667xl)
6. Gray_hyperrectang1e(0.5x1.66"7xl1
~ Z_hyperrectang1e(0.5x l.66"7 x 1)
•
The side length of query(s)
(c)
5
~
6.
•
•
o
600
OL....I__..L.__.L..__L_.......JL._......I__....J:""';;""....J
200
800
400
1000
1400
1200
1600
1800
Figure 411. Average intercluster distance for threedimensional queries
(exhaustive simulation on 26x26x26 grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
40
~.

The side length of query (s)
(a)
Average intercluster distance (Grid: iOx210x210)
350000 ~ • Hilbert_sphere
Q) • f:... Gray_sphere UC
n:l 300000 l f:... $ Z_sphere +J
If.l :a 250000 IH
Q) ~
+J
If.l 200000 ~ ;:::l
.l
UIH
(l) 150000 ~ 6
+J
C
..l ~ !
100000 Ipj,
n:l ~ • ft H ~ ~Q) 50000 I ~ ~ S ; ; ~ e e $
I I . I • I 0
0 2 4 6 8 10 12 14 16 18 20 22 24 26
The side length of queries
(b)
Average intercluster distance (Grid: iOxiox210),
400000 I
I • Hilbert cube
Q) 350000 ' • 6 Gray_cube ()
~ $ Z cube +col 6 300000 :a
H
Q) 250000
+l co $. ;J
.l
() 200000
II
H Q) D +l  c: 150000
. ..1
$.6.
~ 100000 6 H $~.6.~_. Q)
~
50000 ~~Li.6.
$$ : 0
0 5 10 15 20 25 30 35
4]
"
Average intercluster distance I(Grid: zox 210x 210)
600000...: :....._.....:.......,
Q}
0 500000 ra
+J
If)
B 400000
H
(J)
+J
If)
:.J rlI 300000
0I
lI
(J)
+cJ: 200000 .,j
Q)
tJ1
n1 100000 ll
Q)
~
[)
0
• Hilbe:ct_hyperrectangle (,0 .5x1.667xl)
• D. Gray_hype:crectangle(0.5X1.667xl) + Z_hyper:cectangle(O.5xl.667 xl)
Figure 412. Average intercluster distance for threedimensional queries
(sampling simulation on iOx2 10x21O grid): (a) cubic queries, (b) spherical
queries, and (c) hyperrectangular queries.
42
SD
.....
.".j.
:..:.!'
Results and Analyses on. Indexdifference ~'l ,:1<' rl.~ I j' II
Figures 413 and 4]5 present the average.inde~difference betw.een,pointpairs. at'a
common taxi/cab d.istance in twodimensional and threedimensional grid spaces.· The
average indexdifference grows linearly with growing size oftax,jkab distance for aU
three families of spacefilling curves.
Sampling simulations in largesized twodimensional and threedimensional grid
spaces show that Zcurves always have the smallest indexdiffer,ences, the Graycoded
curves the largest, and the Hilbert curves in between. Exhaustive simulations in small
size twodimensional grid 27x27 generate similar results. However exhaustive simulations.
in small size threedimensional grid 26x26x26 show that Zcurves have the lowest average
indexdifference at small taxi/cab distance, and as the taxi/cab distance grows, Zcurves
exceed both the Graycoded curves and the Hilbert curves. Over the considered range of
taxi/cab distance" the Graycoded curves always have larger average indexdifference
than the Hilbert curves.
Figures 414 and 416 present the ratios of the indexdifferences in twodimensional
and threedimensional grid spaces. Each figure consists of two curves, one is that
between the Graycoded curves and tIle Hilbert curves, and the other is that between the
Hilbert curves and Zcurves.
Figure 414(b) shows that in largersized 2'5x21S grid, the ratio of the Hilbert curves
versus Zcurves fits quite well with 1.21. This result complies with the analytical result of
Dai and Su in [DS02], in which the ratio approaches 1.21 as the order of spacefilling
curves grows to infinity. However Figure 414(a) shows in smallersized grid 27x27
, this
result only holds for small taxi/cab distances.
43
J:: ".
s
Figure 414(b) shows that the ratio of the Graycoded curves versus the Hilbert
curves is about 1.21 in largersized grid 215x21S. As switched to the smanersized grid
27x27 in Figure 414(a), the value decreases slightly over the range of large taxi/cab
distance. However the change is not so large compared with ratio between the Hi lbert
curves and Zcurves.
Figure 416(b) 'shows that in largersized grid 210X21Ox21O, the ratio of the Hilbert
curves versus Zcnrves keeps constant at approximately 1.08 over the considered range of
taxi/cab distance. This result again complies with Dai and Su's result in [DS02], where
they give the asymptotic ratio only for taxi/cab distance (j = 1 in threedimensional grid
spaces as the order of spacefilling curve goes to infinity. While in our simulation, we
found that this ratio also holds for all 0 >= 1. Again Figure 416(a) shows that in smallersized
grid 26x26x26, the result is valid only over the range ofsmall taxi/cab distance.
Figure 416(b) also shows that the ratio of the Graycoded curves versus the Hiibert
figure 416(31) shows, the value decreases slightly over the range of large taxi/cab
distance. Still just like the twodimensional case, the change is not so large compared
with ratio between the Hilbert curves and Zcurves.
We can conclude that based on locality measure which is the indexdifference
between pointpairs at a common taxi/cab distance, Zcurves perform better than the
Hilbert curves over the considered ranges of dimension, gridorder and taxi/cab distance,
and the Hilbert curves outperform the Graycoded curves. As the dimensionality grows,
the differences between the indexdifference of three families of spacefilling curves
minish.
44
.5.,.:.
),..
Average indexdifference (grid 2:(21
) 1
4096  • Hilbert curve
'" Graycoded curve
Q) 2048 ~ • Z curve
0c: Q) ~
~Q) 1024 •
lH
:lHa c.' 512 ~ 'I *
)<:
~ .t\ c: 25,6 •• ,..j
Q)
/};.
~ •
~ 128  •
~ /};. .:t: 64 ••
32 I I " I
0.5 1 2 4 8 16 32 '.
Taxi/cab distance ..
)
(a) j
.)
Average indexdifferenoe i 5x 215
)
f)
(Grid: ...
"J....
)
8.38861E6 l • Hilbert curve
• Z curve
., 5'"
4.1943E6 l • :: ..
/':; GrayCoded curve $ :; Q) b,
0 • ....
c: 2.09715E6 f • ')
a> ",
~ I;, :1'
a> : ~
lH 1.04858E6 IlH
:a /':; ..
• )~
I 524288 f $ ...
)<: :>
~ • !
262144 l • ..
c: ..1 /\
a> •
tJ:'I 131072 I <$
m Cc
~ •
~ 65536 I <$
.:t: ~
32768 l •
16384 " "
I ,
"
1 2 4 8 16 32 64 128 256
Taxi/cab distance
(b)
Figure 413 . Indexdifference versus taxi/eab distance on twodimensional
grilld (a) exhaustive simulation on 27 x 27 grid and (b) sampling simulation
on 215xi5 grid.
45
Ratio of average indexdifference (Grid; 2)(21
),
2.6
<IJ 2.4 ,6. tJ Gr:ayCcx:led cu.r;ve vs. Hilbe:r;t curve
C • Hilbert curve 'ITS. <IJ 2.2 ~ Z curve
ll
<IJ
'H 2.0 'H
BI 1.8f
><
~ 1.6fc
11
•.1 1.4
~ 1.21 • ,6. Do I!
ll • <ftIJl • 1.0
I·
<IJ 0.8 l I:
:5 
0.6 I
'H I;
0 0.4 I
0 I
..1 0.2 & I I Ii
0.0
0.5 1 2 4 8 16
Taxi/cab Qistance
(a) "
~.
o
J
Ratio of average indexdifference (Grid: z5)(ls) S~
2.6 f)
Q) • Hilbert curve vs. Z curve
"t.
0 2.4 ).
@ D.
.,
2.2 I GrayCooed curve vs. Hilbert curve )
ll
Q) 'H 2.0 I "" 'H
') :a ~'.
1.81 ..
I )
~ '\
1.6 :I
" .
.~ '3'
1.4
,
(J) • ! n ~ tyl 1.2 /:,
~ ,
((j )
ll
(J) " ftl 1.01 :>
~
0.8 Ioo
Q) :5 0.6
'H
0 0.4
0
..1 +J 0.2
&! 0.0 I
"
I I I I
1 2 4 8 16 32 64 128 256
Taxi/cab distance
(b)
Figure 414. Ratio of the indexdifference versus taxi/cab distance on
twodimensional grid (a) exhaustive simulation on 27
x 27 grid and (b)
sampling simulation on i 5x215 grid.
46
Average indexdifference (Grid: 1x26X26)
8192
16384
65536
(lJ 32768
o
~
&l
l/l :aI~
c: •..1
Hilbert curve
Grayeoded curve
Z curve
4096
2048
1 2 4 8 16 32
1024 L__..L..__....L.""";'_.....1 L...__.L..__....i.._1
0.5
Taxi/cab distance
(a)
Average indexdifference (Grid: :ZOx 210x210
)
/\ 3
Hilbert curve
Grayeoded curve
Z curve
i
5242881[1i  L'__.........L__........L__.........L .L_.....I
1 2 4 8 16 32
1.67772E7 Ii j
.
(lJ 8.38861E6
oc:
(lJ
H
$
l/l 4.1943£6
Bk
~
_~ 2. 09715E6 I
~
H
<lJ 1.04858E6
~
Taxi/cab distance
(b)
Figure 415. Indexdifference versus taxi/cab distance on threedimensional
grid (a) exhaustive simulation on 26x26x26 grid and (b)
sampling simulation on 210x210xiOgrid.
47
Ratio of average indexdifference (Grid: tX26X26)
1.8
Ql 0 • Hilbert curve vs. Z curve c:
Ql f::, Graycoded. vs. Z curve ll 1.6
Ql
4l
4l :a 1.4 IX~
~ 1.2 .
Q) '" tJ1 • • f::, I'll f::,
11 • f::,
Q) 1.0
~ •
4l ,I • 0 0.8
0
o,i
I 1
.j.J
~ 0.6
0.5 1 2 4 8 16 32
Taxi/cab distance
(a}
Ratio of average indexdifference (Grid: 2°xioxio)
1.8.,
• Hilbert curve vs, Z curve
f::, GrayCoded curve vs. Z curve
1.0
4l
o 0.8
o orl
.j.J
~ 0.6
:;
)
1 2 4 8 16
Taxi/cab distance
(b)
32
Figure 416. Ratio of the indexdifference versus taxi/cab distance on
threedimensional grid (a/ exhaustive simulation on 26x26x26 grid and (b)
sampling simulation on 2 °x2 JOx2 JO grid.
48
CHAPTER FIVE
APPLICATIONS IN IMAGE PROCESSING
Spacefilling curves have applications in a lot of field, among which is image
processing.. In this chapter, we will first of an introduce some concepts about image
processing, and then try to make comparisons of those. onedimensional representations
of images that are scanned long the three families of spacefilling curves.
Image processing has many interesting applications in medicine, biological research,
photography, space exploration, astronomy, and law enforcement forensics. Numerous
and widely varying types of image processing operations have been developed during the
past 20 years, among which are image enhancement, restoration, analysis, compression,
and synthesis. With the advent of the Internet and the WWW, image compression is now
more important than ever. To achieve acceptable throughout over the Internet, images are
usually compressed to minimize their size.
There are a host of known applications for image compressIOn techniques and
systems, and new applications are being proposed each day, creating a demand for
modifications of existing compression methods or entirely new approaches. Existing
applications of compression methods include facsimile, personal communications
systems, stillimage archival, videoconferencing, and video and movie distribution.
The goal of image compression is the reduction of the amount of data required to
represent a digital image. The idea of image compression is to remove redundant data
49
' : ..
,)
~
.;:
1': ,)
.p.
from the images (i ..e., data which do not affect image quality significantly).· Image
compression is very important for image storage and image transmission. .,
Some apphcations of image storage are: educational and business documents, medical
images, weather maps and fingerprints. Some applications of image transmission are:
remote sensing via satellite, military communications via aircraft, radar, and sonar,
teleconferencing, and facsimile transmission.
Image compression techniques are divided into two general groups: loseless and
lossy. Loseless image compression preserves the exact data content of the original.image.
Lossy image compression preserves some specified level of image quality, but not the
absolute data content of the original image.
Loseless coding techniques providle for exact recovery of the original image. Huffinan
coding, arithmetic decomposition, Lempel Ziv algorithms, and run length coding are all
loseless coding techniques. Lossy coding techniques include predictive coding,
frequencyoriented coding, importanceoriented coding, and hybrid coding.
Usually loseless coding techniques yield lower compression ratio, while lossy coding
techniques have higher compression ratio. So there is a tradeoff between image quality
and compression ratio. By compression ratio, we mean quotient of the number of units
used to represent the original image and number of units used to represent the
compressed image.
Before applying the image compression encoding, the twodimensional image data
should first be scanned into a bit sequence, or a bit string using some scanning function.
For simplicity, here we only consider the binary image in which 0 stands for white pixels,
and 1 for black pixels.
50
We assume an image to be a NxN grid of pixels. The pixel at point (i, j) in the image
has intensity value Pi.J°' Defmition: A scan of the image is a bijection! from the closed
interval of integers [1, .. .,Nl] to the set of ordered pairs {{iJ): 1<= i, j <= N}, where the
latter set denotes the points in the image. Equivalently, the image is encoded using the
scan! by encoding the pixel intensities in the order Pit!), Pr(2),"" Pl\N\
The level of compression using run length encoding is entirely dependent upon the
repetitive nature of the source image. An image with large runs of the same pixel
intensity will compress well. Images without this property will compress poorly.
However for the same image, different scanning functions yields different compression
ratios.
There is a lot of scanning methods applied in practice. Some of them are rowbyrow
scan, columnbycolurnn scan, zigzag scan. Besides these ordinary scanning methods,
spacefilling curves are also very popular scanning methods. If the image does not have
long runs, better compression may be produced by a method that scans the bitmap area by
area instead of rowbyrow scanning or columnbycolumn scanning. A spacefilling
curve completely fills up a part of space by passing through every point in that part.
To investigate how the three spacefilling curves we have interested in this thesis will
behave in image compression, we applied the image scan on an image of deer first, and
then on a 2' °x2 lo image filled with 200 randomly placed squares of size 8x8.
In Figure 51(a) we presented the image of deer [DeMOO], and in Figure 51(b) the
autocorrelation function based on scanned images which are scanned along three
families of spacefilling curves and also rowbyrow scanning. We can see that Hilbert
spacefilling curves have the highest autocorrelation over the whole range of index
51
.,,.: )
: "
")
j:
difference, while Zcurves and the Graycoded curves perform better than rowbyrow
scanning at relatively large index difference.
Still we also want to compare all these spacefilling curves when image of small
objects is scmmed. In Figure 52, we presented the autocorrelation results obtained
through onedimensional images scanned along three families of spacefilling curves and
rowbyrow scanning. We can see from the figure that spacefilling curves produce really
.
good autocorrelation even when the autocorrelation reaches almost zero under rowbyrow
scanrung.
It is very clear that spacefilling curves are really good at scanning images with
scattered small obj eets. Among these three families of spacefilling curves, Hilbert spacefilling
curves are superior to the other two. Zcurves and the Graycoded curves have
almost the same behavior when applied on image scanning. This is easy to understand if
we can recall that Hilbert spacefilling curves have the best clustering properties, while
Zcurves and the Graycoded curves have almost the same clustering properties in twodimensional
cases as shown in Figure 41 and 42.
Finally we can conclude that when applied on image compression, Hilbert spacefilling
curves is superior to Zcurves and the Graycoded curves, and Zcurves and the
Graycoded curves behave almost the same.
52
.. :<
~. ".
'. :'
(a)
Autocorrelation of the deer image
0.95 • Hilbert curve
0.90
~ Z curve
~ f.'.:... GrayCoded curve
c: 0.85 •  X  Row by row scan
0
.I +m.J 0.80 • • . .l
(1) • ll • ll 0.75 0
0
0 .w 0.70 t~ ~
0.65 ~ 0.60
0.55
0 2 4 6 8 10
Distance between two pixels
(b)
Figure 51. (a) A deer image applIed Hilbert spacefilling curve scanning,
(b) Autocorrelation of the three scanned images under three families of
spacefilling curves and rowbyrow scanning.
53
~,.
~ •
,.:.
10* 10 2 2 (200 randomly placed squares of size ax 8)
1.0
0.8
oc:
j 0.6
<ll
rl
~
Il 8 OA
o
W
~
0.2
0.0
o 2 4 6 8 10
Distance between two pixels
Figure 52. Autocorrelation of the scanned images under three families of
spacefilling curves and rowbyrow scanning, in which the image is 200
randomly placed squares of size 8xg on 210x2 10 grid.
54
I.
I
,"
,."
CHAPTER SIX
CONCLUSION
From the simulations and the analyses in chapter 4 and 5, We can conclude that the
Hilbert curves are superior to Zcurves and also the Graycoded curves on clustering
properties, Zcurves outperfonn the other two spacefilling curves on intercluster
distance, query indexing range, and indexdifference properties. When applied on image
scan in image compression, the Hilbert curves are the best.
Even though it seems that the Hilbert spacefilling curves are the best on clustering
locality measure, Gotsman and Lindenbaum [GL96] posed the question as to "whether
there exists families of spacefilling curves with locality properties better than those of
the Hilbert curves for all sizes". In their work [GL96], classic Hilbert spacefilling curves
come close to achieving optimal locality based on locality metric ofLGL ,max (C). The
answer from R. Niedermeier et a1.'5 work [NRS97] is affinnative. In their work, they
proposed a new twodimensional indexing scheme what they called !Iindexing, which is
related to twodimensional Sierpinski curve [Sag94]. They proved that Hindexings are
optimally localitypreserving with respect to the Euclidean metric, maximum metric, and
Manhattan or taxi/cab metric.
Here we can say that no matter which spacefilhng curve, it can't be always superior
to an the other spacefilling curves on aU those locality property measures. To chose
which spacefilling curve in a specific application filed depends on the locality measure
55
.,,::
which is the most important to that field, and also we should consider the spacefilling
curve that perfonns the best in that locahty metric.
I •
56
,
'
, r\.\ "
REFERENCES
[AM90] D.l. Abel and D.M. Mark, "A Comparative Analysis of Some TwoDimensional
Orderings," Int'IJournal ofGeographical Information Systems, 4(1): 2131, 1990.
[Bia69] T. Bially, "SpaceFilling Curves: Their Generation and Their Application to
Bandwidth Reduction," IEEE Tmnsactions on Information Theory, 15(6): 658664,
1969.
[BP82] J. J. Bartho~di and L.K. PIatsman, "An O(nlgn) Travelling Salesman Heuristic
Based on Spacefilling Curves," Operation Research Letters, 1(4): 121125, 1982.
[But69] A.R. Butz, "Convergence with Hilbert's Space Filling Curve," Journal of
Computer and System Sciences, 3: 128 t 46, 1969.
[DCMOO] Revital Dafner, Daniel CohenOr and Yossi Matias, "Contextbased Space
Filling Curves.," EUROGRAPHICS,19:19, 2000.
[DS02] H.K. Dati and H.c. Sll, "On the Locality Properties of SpaceFilling Curves~"
draft, 2002.
[Duf84] 1.S. Duff, "Design Features of a Frontal Code for Solving Sparse Unsymmetric
Linear Systems OutofCore," SIAM Journal of Scientific Statistical Computing,
5(2): 270280, 1984.
[FaI86] C. Faloutsos, "Mutltiattribute Hashing Using Gray Codes," Proceedings of 1986
ACMSIGMOD Conference, pages 227238, May 1986.
[FS89] C. Faloutsos and S. Roseman. " Fractals for Secondary Key Retrieval,"
Proceeding of the Eighth ACM SIGACTSlGMODSIGART Symposium on
Principles ofDatabase Systems, pages 247252, 1989.
[GG98] V. Gaede and O. GUnther. "Multidimensional Access Methods," ACM
Computing Surveys, 30(2): 170231, June] 998.
[GL96] C. Gotsman and M. Lindenbaum. "On the Metric Properties of Discrete SpaceFilling
Curves," IEEE Transactions on Image Processing, 5(5), 1996.
[Hi11891] D. Hilbert. "Uber stetige Abbildung einer Linie auf ein Flachenstuck,"
Mathematische Annalen, 38: 459460,.1891
57
.'
[Jag90] H.V. Jagadish, "Unear Clustering of Objects with Multiple Attributes,"
Proceedings ofACM SIMOD Conference, pages 312342, May 1990.
j
[Jag97] H.V. Jagadish, "Analysis of the Hilbert Curves for Representing Twodimensional
Space," Information Processing Letters, 62(1): 1722, 1997.
[KOR95] M. Kaddoura, C.W. Ou, and S. Ranka, "Partitioning Unstructured
Computational Graphs for Nonuniform and Adaptive Environments," IEEE
Parallel and Distributed Technology,.3(3): 6369, 1995.
[LZ84] A. Lempel and J. Ziv, "Compression of TwoDimensional Images," NATO ASI
Series. F12: 141154,1984.
[Lau85] R. Laurini. "Graphical Databases Built on Peano SpaceFillin.g curves," In
Proceedings ofEurographics '85, pages 327338. NorthHonand, 1985.
[LZ86] A. Lempel and J. Ziv, "Compression of TwoDimensional Data," IEEE
Transactions on Information Theory, 32{]): 28, 1986.
[MD86] G. Mitchison and R. Durbin. "Optimal Numberings of an NxN Array," SIAM
Journal on Algebraic and Discrete Methods, 7(4): 57l582, 1986.
[MJFOl] B. Moon, H.V. Jagadish, C. Faloutsos. "Analysis of the Clustering Properties of
the Hilbert SpaceFilling Curve," IEEE Transactions on Knowledge a1ld Data
Engineering, 13(1): 124141,2001.
[NRS97] R. Niedenneier, K. Reinhardt, and P. Sanders. "Towards Optimal Locality in
MeshIndexings," Lecture Notes in Computer Science 1279, 1997.
[Ore86] J. Orenstein, "Spatial Query processing in an ObjectOriented Database System,"
Proceedings of1986 ACMSIGMOD Conference, pages 326336, May 1986.
[PAR68] E.A. Patrick, D.R. Anderson a.nd F.K. Bechtel, "Mapping MultiDimensional
Space to One Dimension for Computer Output Display," IEEE Transactions on
Computers, 17(19): 949953, 1968.
[PeaI890] G. Peano, "Sur une Courbe qui Remplit Toute une Aire Plane, " .Math. Annual
36:157160,.1890.
[PB89] L.K. Platsman and J. J. Bartholdi, "Spacefilling Curves and the Planar Travelling
Saleman Problem," Journal of the Association for Computing Machinery, 36(4):
719737,1989.
[PK.K92] A. Perez, S. Kamata, and E. Kawaguchi. "Peano Scanning of Arbitrary Size
Images," Proceedings of the International Conference on Pattern Recognition,
pages 565568. IEEE Computer Society, 1992.
58
"
[RF91] Y. Rong and C. Faloutsos, "Analysis of the Clus~ering Property of Peano
Curves," Technical Report CSTR2792, UMlACSTR91151, Univers:ity of
Maryland, Dec. 1991.
[Riv76] R.L. Rivest, "Partial Match Retrieval Algorithms," SIAM Journal on Computing,
5(1): 1950, 1976.
[Sag93] H. Sagan, "A ThreeDimensional Hilbert Curve," International Journal ofMath.
Ed. Science Technology, 24: 541545, 1993.
[Sag94] H. Sagan. SpaceFilling Curves. Springer Verlag, 1994.
[Sim63] G.F. Simmons, Introduction to Topology and Modern Analysis. New York:
McGrawHill Book Company, Inc., 1963.
[ZW93] Y. Zhang and R.E. Webber, "Space Diffusion: An Improved ParaUel HaUtoning
Technique Using SpaceFilling Curves," Computer Graphics Proceedings, Annual
Conference Series, pages 305312. ACM, 1993.
59
APPENDIX
Source code of simulation <thesis.cpp>
/*************'*********************************************************
* Author Hua LI *
* Date Oct., 2001  April 2002 *
* Purpose This algorithm is used to perform simulation on locality*
* preserving properties of three kinds of spacefilling *
* curves, Hilbert curves, Zcurves, and Graycoded curves. *
***********************************************************************
* Function: zOrder_c2i( int nDims, int nBits, bitmask_t coord[]) *
* Purpose : Mapping coordinates (x,y,z) into the index under Zcurve.*
***********************************************************************
* Function gray_c2i ( int nDims, int nBits, bitmask_t coord [J *
* Purpose : Mapping coordinates (x,y,z) into the index under *
* Graycoded curve. *
***********************************************************************
* Function : *
* numCluster( int x,int y,int z,int querySize,double &maxLength) *
* Purpose Given the querySize and also the randomly chosen locate *
* (x,y,z), return the number of clusters, and also collect *
* the number of intercluster distance. *
***********************************************************************
* Function interCluster() *
* Purpose This function will collect the average number of cluster,*
* the intercluster distance, and the average query range. *
***********************************************************************
* Function : random ( int& iseed ) *
* Purpose : With input iseed, return a random value between 0 and 1. *
***********************************************************************
* Function: indexDiff( int taxiDistance ) *
* Purpose : With input taxiDistance, give an average indexdifference*
**********************************************************************/
#include "hilbert.h"
#include <iostream>
#include <string>
#include <iomanip>
#include <math.h>
#include <fstream>
#include <stack>
#include <utility>
#include <vector>
#include <list>
#include <numeric>
#include <algorithm>
using namespace std;
/***************************
* G  Graycoded curve *
60
* H  Hilbert curve
* Z  Zcurve
**
***************************/
const char curve_flag = 'G';
//output file name for indexdifference
const char * distribution = "dis_3d_graY_IO";
ofstream disfile(distribution);
Iioutput file name for intercluster metrics
Ilconst char *statFile = "stat_3dyoly_graY_10";
Ilofstream statOut(statFile};
Ilconstants
const int nDims 3; Iidimensionality
const int nBits 10; II k in 2 A (k)
const int length = pow (2, nBits.); I I the grid size
II the number of sampling for intercluster distance
const int numSample = 100000;
II the number of sampling for indexdifference
const int lengthSample = 20000000;
Ilglobal variants
double nlnterDis 0;
double totlnterDis = 0;
Ilfunctions and subroutines
int zOrder_c2i( int nDims, int nBits, void const* coordl );
int gray_c2i( int nDims, int nBits, void const* coordl );
int numCluster( int x, int y, int z, int querySize, double
&maxLength );
void interCluster();
float random ( int& iseed };
void indexDiff( int taxiDistance
int main ()
for( int i = 2; i <= 256; i *= 2 }
indexDiff (i) i
return 0;
/**********************************************************************
* Function: indexDiff( int taxiDistance )
* Purpose : With input taxiDistance, give an average indexdifference.
**********************************************************************1
void indexDiff( int taxiDistance
{
static int xseed
static int yseed
static int zseed
2834;
28479 ;
1484;
double totGrid = 0;
double testLength = 0;
61
double testTot = 0; . !
for( lnt i = 0; 1 < lengthSample; i ++ )
{
I/coordinates of the beginning point
lnt xl random (xseed) * length;
int yl random (yseed) * length;
int zl random (zseed) * length; *.
for ( int dx
for( int dy
{
0; dx <= taxiDistance; dx++)
0; dy <= taxiDistance  dXi dy++)
Iitaxi distance
int dz = taxiDistance  dx  dy;
Ilcoordinates of the ending point
int x2 xl + dx;
int y2 yl + dy;
int z2 zl + dz;
if( x2 < lengt.h && y2 < length && z2 < length)
{
double linearDi,s i
unsigned long cl[3]
unsigned long c2[3]
swit.ch(curve flag)
{
{xl fyI, Z 1 } ;
{x2 f y2 , z 2 } ;
case 'H':
linearDis
abs(hilbert c2i(3,nBits,cl)
hilbert_c2i(3,nBits,c2)) ;
break;
cas,e 'Z I :
IlnearDis =
abs(zOrder_c2i(nDims,nBit.s,cl)zOrder_
c2i(nDims,nBits,c2) };
break;
case 'G':
linearDis
abs(gray_c2i(nDims,nBits,cl)gray_
c2i(nDims,nBits,c2) i
break;
test.Length += linearDis;
testTot ++;
}
if( i % 100000 == 0)
cout « taxiDistance « " " « i « endl;
Iioutput t.he results
disfile « taxiDistance « " ";
disfile « testLength/testTot « endl;
cout « taxiDistance « " ";
62 
cout « testLength/testTot « endl,
1**********************************************************************
* Function interCluster() *
* Purpose : This function will collect the average number of cluster,*
* the intercluster distance, and the average query range. *
*'***********************************************.*********************/
void interCluster()
static int xseed
static int yseed
static int zseed
fort int querySize
{
876749;
1343 ;
34589;
2; querySize <= 32; querySize +=2 l
nlnterDis = 0;
totlnterDis = 0;
double totCluster = 0;
double maxRange = 0;
int maxCluster = 0;
fort int i = 0; i < numSample; i++
{
double maxLength = 0;
IICube queries
II int x random (xseed) * (length  querySize) ;
II int y random (yseed) * (length  querySize) ;
II int z random (zseed) * (length  querySize) ;
IIPolyhedra queries
int x random (xseed) *
int y random (yseed) *
int z random (yseedl *
(length  querySize);
(length  querySize);
(length  2*quex'ySizel;
1*
*/
Ilsphere queries
int x = random(xseed) * (length  2*querySize)
+ querySize;
int y = random (yseed) * (length  2*querySize)
+ querySize;
int z = random (zseed) * (length  2*querySize)
+ que.rySize;
int nc = numClust.er(x,y,z,querySize,maxLength);
tot Cluster += nc;
if( nc > maxCluster) maxCluster = nc;
maxRange += maxLength;
if( i % 10000 == 0 )
cout « querySize « II II « i « endl;
float avglnterDis = totlnterDis/float(nlnterDis);
float avgCluster = totCluster 1= double (numSample) ;
63
maxRange 1= double (numSample) ;
1*
cout « querySize « II n « avgCluster
« n " « maxCluster « " " « maxRange;
cout « " II « avgInterDis « endl;
statOut « querySize « " " « avgCluster
« n " « maxCluster « .. " « maxRange;
statOut « " " « avgInterDis « endl;
*1
int numCluster ( int x, int y, int z, int querySize, double & maxLength
)
{
int nc = 1; Iinumber of clusters, default value is set to 1.
list<int> Inc;
Iisquare query
II for ( int i X; i < X +
II for ( int j y; j < y +
II for ( int k z·, k < z +
Ilpolyhedra query
for ( int i x·, i < x +
fore int j y; j < y +
fore int k z; k < z +
querySize; i++
querySize; j++
querySize; k++
0.5 * querySize; i++
1.6667 * querySize; j++
querySize; k++ )
Iisphere query
II fore int i x  querySize; i < x + querySize; i++
II fore int j y  querySize; j < y + querySize; j++
II fore int k z  querySize; k < z + querySize; k++
{
/Isphere query check
/*float distance = (ix>*{ix);
distance += (j y) * (j y) ;
distance += (kz)*(kz);
if( distance <= pow (querySize,2) )
*1
{
int index = 0;
bitmask t cl[nDims]
switch (curve_flag)
{
case 'Z I :
{i,j,k};
index zOrder_c2i(nDims,nBits,cl);
break;
case 'G':
index = gray_c2i(nDims,nBits,cl);
break;
case 'H':
index = hilbert c2i(nDimS,nBits,cl);
break;
}
lnc.push_back{index) i
64
....
lnc.sort();
listcint>::iterator p
listcint>::iterator q
Inc .begin () ;
lnc.begin() ;
maxLength = 1* (*q) ;
qtt;
for( ; q != lnc.end(); qtt )
{
II discontinuous interger means two clusters
if( *q > *p + 1 )
{
nc ++;
Ilintercluster distance between two neighbouring clusters.
nInterDis ++;
totInterDis += *q  *p;
p++;
}
maxLength += *pill the Maximum range of the query
return nc;
1**********************************************************************
* Function: zOrder_c2i( int neims. int nBits, bitmask_t coord[]) *
* Purpose : Mapping coordinates (x,y,.z) into the index under Zcurve.*
**********************************************************************1
int zOrder_c2i( int nDims, int nBits, bitmask t coord[]
int zcode = 0, n = 1;
for( int i = 0; i c nBits; iTT)
{
int j = 0; j c nDims; j++)
1*
int xl
int y1
int zl
zcode
x »=
y »=
Z »=
n cc=
*1
for{
{
+=
l'I
1 ;
1;
3 ;
x%2;
Y %2' • I
z%2;
x1*4*n + y1*2*n + zl*n;llthreedimensional case
int k = coord[j] % 2;
zcode += k * n;
n c<= 1;
coord[j] »= 1;
}
return zcode;
65
1**********************************************************************
* Function gray_c2i( ,int nDims, int nBits, bitmask_t coord[] *
* Purpose Mapping coordinate's (x, y, z) into the index under *
* Graycoded curve.
*
**********************************************************************1
int gray_c2i ( int nDims, int nBits, bitmask_t coord []
int zcode = zOrder c2i(nDims, nBits, coord) i
return zcodeA(zcode »1 ) ii/convert binary code to gray code
1**********************************************************************
* Function : random ( int& iseed ) *
* Purpose : With input iseed, return a random value between 0 and 1. *
**********************~******************************* ****************1
float random ( int& iseed )
{
const int m
const int a
1048583;
1997i
iseed = ( a* iseed )tmi
return float (iseed) /float (m)
66
<hilbert.h>
/* C header file for Hilbert curve functions */
#i£ !defined( hilbert h )
#define hilb~rt h 
#ifdef __cplusplus
extern "C" {
#endif
/* define the bitmask_t type as an intege~ of sufficient size */
typedef unsigned long int bitmask t;
/* define the halfmask_t type as ~n integer of 1/2 the size of
bitmask_t */
typedef unsigned long halfmask_t;
/*****************************************************************
* hilbert i2c
*
The list of nDims coordinates, each with nBits bits.
bits (so nDims*nBits
Number of coordinate axes.
Number of bits per axis.
The index,. contains nDims*nBits
S*sizeof(bitmasK_t» .
* Convert an index into a Hilbert curve to a set of coordinates.
* Inputs:
* nDims:
* nBits:
* index:
must be <=
* Outputs:
* coord:
* Assumptions:
* nDims*nBits <= (sizeof index) * (bitsper~yte)
*/
void hilbert i2c(unsigned nDims, unsigned nBits, bitmask t index,
bitmask_t coord[]);
/*****************************************************************
* hilbert c2i
*
Number of coordinates.
Number of bits/coordinate.
Array of n nBitsbit coordinates.
output index value. nDims*nBits bits.
* Convert coordinates of a point on a Hilbert curve to its index.
* Inputs:
* nDims:
* nBits:
* coord:
* Outputs:
* index:
* Assumptions:
* nDims*nBits <= (sizeof bitmask_t) * (bitsper_byte)
*/
/*****************************************************************
* hilbert_cmp, hilbert_ieee_cmp
**
Determine which of two points lies further along the Hilbert curve
* Inputs:
* nDims: Number of coordinates.
67
*
Number of coordinates.
Number of bytes/coordinate.
Number of bits/coordinate. (hilbert_cmp only)
Is it the least vertex sought?
Array of nDims nBytesbyte coordinates  one corner of
Array of nDims nBytesbyte coordinates  opposite
Number of coordinates.
Number of bytes/coordinate.
* nByt,es: Number of bytes of storage/coordinate {hilbert_cmp
only)
* n.Bits:
* coordl:
ieee_crop) .
* coord2:
ieee_cmp} .
* Return value:
Number of bits/coordinate. (hilbert_cmp only)
Array of nDims nBytesbyte coordinates {or doubles for
Array of nDims nBytesbyte coordinates (or doubles for
1, 0, or 1 according to whether
coordl<coord2, coordl=.=coord2, coordl>coord2
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bitsper_byte}
*/
int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void
const* coordl, void const* coord2};
int hilbert_ieee_cmp(unsigned nDims, double const* coordl, double
const* coord2);
/*****************************************************************
* hilbert box vtx
*
* Determine the first or last vertex of a box to lie on a Hilbert
curve
* Inputs:
* nDims:
* nBytes:
* nBits:
* findMin:
* coordl:
box
* coord2:
corner
* output:
* cl and c2 modified to refer to selected corner
* value returned is 10g2 of size of largest poweroftwoaligned
box that
* contains the selected corner and no other corners
* Assumptions:
* nEits <= (sizeof bitmask_t) * (bitsper_byte)
*/
unsigned
hilbert box_vtx{unsigned nDims, unsigned nBytes, unsigned nBits,
int findMin, void* cl, void* c2}i
unsigned
hilbert_ieee_box_vtx(unsigned nDims,
int findMin, double* cl, double* c2);
/*****************************************************************
* hilbert box vtx
**
Determine the first or last vertex of a box to lie on a Hilbert
curve
* Inputs:
* nDims:
* nBytes:
68
Array of nDims nBytesbyte coordinates  opposite
Number of bits/coordinate _ ,(hilbert_cmp only)
Is it the least vertex sought?
Array of nDims nBytesbyte coordinates  one corner of
* nBit.s:
* findMin:
* coordl:
box
* coord2:
corner
* Output.:
* cl and c2 modified to refer to selected corner
* value returned is 10g2 of size of largest poweroftwoaligned
box that
* contains the selected corner and no other corners
* Assumpt.ions:
* nBit.s <= (sizeof bitmask_t) * (bits'yer_byte)
*/
unsigned
hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
int findMin, void* cl, void* e2);
unsigned
hilbert_ieee_box_vtx(unsigned nDims,
int findMin, double* el, double* e2);
/*****************************************************************
* hilbert_boxyt
*
r
* Determine
* Inputs:
* nDims:
* nBytes:
* nBits:
* findMin:
* eoordl:
box
* coord2:
the first or last point of a box to lie on a Hilbert curve
Number of coordinates.
Number of bytes/coordinate.
Number of bits/coordinate.
Is it the least vertex sought?
Array of nDims nBytesbyte coordinat.es  one corner of
Array of nDims nBytesbyte coordinates  opposite
corner
* Output:
* el and e2 modified to refer to least point.
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
unsigned
hilbert_boxyt(unsigned nDims, unsigned nBytes, unsigned nBits,
int findMin, void* coordl, void* coord2);
unsigned
hilbert_ieee_boxyt.(unsigned nDims,
int findMin, double* cl, double* c2);
/*****************************************************************
* h~lbert nextinbox
**
Determine the
Hilbert curve
* Inputs:
* nDims:
* nBytes:
* nBits:
first point of a box after a given point to lie on a
Number of coordinates.
Number of bytes/coordinate.
Number of bits/coordinate.
69 
Is the previousfpbint 'sought?
Array of nDims nBytesbyte coordinates  one corner of
* findPrev:
* coord!:
box
* coord2: Array of nDims nBy:tesbyte coordinates  opposite , '
r
*
Next point on Hilbert curve
Number of coordinates.
Number of bits/coordinate.
Array of nDims nBitabit coordinates.
corner
* point: Array of nDirns nBytesbyte coordinates  lower bound on
point returned
**
Output:
if returns 1:
c1 and c2 modified to refer to least point after "point" in box
else returns 0:
arguments unchanged; "point" is beyond the last point of the
box
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bitsper_byte)
*/
int
hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
int findPrev, void* coordl, void* coord2,
void const* point);
/*****************************************************************
* hilbert iner
**
Advance from one point to its successor on a Hilbert curve
* Inputs:
* nDims:
* nBits:
* coord:
* Output:
* coord:
* Assumptions:
* nBits <= (sizeof bitmask t) * (bits.yer_byte)
*/
void
hilbert_incr (unsigned nDims, unsigned nBlts I bitmask t coord (] ) ;
/* See LICENSE below for information on rights to use, modify and
distribute
this code. */
/*
* hilbert.c  Computes Hilbert spacefilling curve coordinates,
without
* recursion, from integer index, and vice versa, and other Hilbertrelated
* calculations. Also known as Piorder or Peano scan.
**
Author:
*
***
Date:
Doug Moore
Dept. of Computational and Applied Math
Rice University
http://www . caam. rice. edu/ dougm
Sun Feb 20 2000
70 I
_...
* Copyright (e) 19982000, Rice University
**
Acknowledgement:
* This implementation is based on the work of A. R. Butz ("Alternative
* Algorithm for Hilbert's SpaceFilling Curve", IEEE Trans. Comp.,
April,
* 1971, pp 424426) and its interpretation by Spencer W. Thomas,
University
* of Michigan (http://wwwpersonal.umich.edu/spencer/Home.html) in
his widely
* available C software. While the implementation here differs
considerably
* from his, the first two interfaces and the style of some comments
are very
* much derived from his work. */
//#include "hilbert.h"
/* implementation of the hilbert functions */
#define adjust_rotation (rotation,nDims,bits)
\
do
\
/* rotation = (rot,ation + 1 + ffs (bits» % nDims; */
\
bits &= bits & ndlOnes;
\
while (bits)
\
bits »= 1, ++rotation;
\
if ( TTrotation >= nDims
\
rotation = nDims;
\
} while (0)
#define ones(T,k) (((T)2) « (kl»  1)
#define rdbit (w, k) « (w) » (k» & 1)
#define rotateRight(arg, nRots, nDims)
\
( «arg) » (nRots» I ((arg) « «(nDims)  (nRots) ») &
ones (bitmask_t, nDims) )
#define rotateLeft(arg, nRots, nDims)
\
« ((arg) « (nRots» I ((arg) » «(nDims)  (nRots) > » &
ones(bitmask_t,nDims»
#define DLOGB_BIT_TRANSPOSE
static bitmask t
bitTranspose(unsigned nDims, unsigned nBits, bitmask t inCoords)
#if defined(DLOGB_BIT_TRANSPOSE)
{
71 
unsigned const nDims1 nDims1i
unsigned inB = nBitsi
unsigned utB;
bitmask t inFieldEnds = 1;
bitmask t inMask ones (bitmask_t,inB) ;
bitmask t coords = 0;
while « utB = inB / 2»
{
unsigned const shiftAmt = nDimsl * utB;
bitmask t const utFieldEnds =
inFieldEnds 1 (inFieldEnds « (shiftAmt+utB»;
bitmask t const utMask =
(utFieldEnds «utB)  utFieldEnds;
bitmask_t utCoords = 0;
unsigned d;
if (inB & 1)
{
bitmask t const inFieldStarts = inFieldEnds « (inBl);
unsigned oddShift = 2*shiftAmti
for (d = 0; d < nDims; ++d)
{
bitmask t in = inCoords & inMask;
inCoords »= inB;
coords 1= (in & inFieldStarts)« oddShift++i
in &= inFieldStarts;
in = (in 1 (in« shiftAmt» & utMask;
utCoords 1= in « (d*utB)i
}
else
{
for (d = 0; d < nDims; ++d)
{
bitmask t in = inCoords& inMask;
inCoords »= inB;
in = (in 1 (in« shiftAmt» & utMask;
utCoords 1= in « (d*utB);
}
inCoords = utCoords;
inB = utB;
inFieldEnds = utFieldEnds;
inMask = utMaski
}
coords 1= inCoordsi
return coords;
}
#else
{
bitmask t coords = 0;
unsigned d;
for (d = OJ d < nDimsi ++d)
unsigned b;
bitmask t in = inCoords & ones (bitmask_t,nBits) ;
bitmask tout = Oi
72

r
inCoords »= nBits;
for (b = nBits; b;)
{
out «= nDims;
out 1= rdbit(in, b);
}
coords 1= out « d;
return coords;
}
#endif
1***************************************************** ************
* hilbert i2c
**
Convert
* Inputs:
* nDims:
* nBits:
* index:
*
an index into a Hilbert curve to a set of coordinates.
Number of coordinate axes.
Number of bits per axis.
The index, contains nDims*nBits bits
(so nDims*nBits must be <= a*sizeof(bitmask_t».
* Outputs:
* coord: The list of nDims coordinates, each with nBits bits.
* Assumptions:
* nDims*nBits <= (sizeof index) *' (bitsyer_byte)
*1
void
Ilhilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index,
bitmask_t coord!])
hilbert i2c(unsigned nDims, unsigned nBits, bitmask t index, bitmask t
coord [])
{
if (nDims > 1)
{
bitmask t coords;
halfmask t const nbOnes
unsigned d;
if (nBi ts > 1)
{
ones (halfmask_t,nBits);
unsigned canst nDimsBits = nDims*nBitsj
halfmask t canst ndOnes = ones (halfmask_t,nDims) ;
halfmask t const nd10nes= ndOnes » 1; 1* for adjust rotation
*1
unsigned b = nDimsBits;
unsigned rotation = 0;
halfmask_t flipBit = 0;
bitmask_t const nthbits = ones(bitmask t,nDimsBits) I ndOnes;
index A= (index A nthbits) » 1;
coords = 0;
do
{
halfmask_t bits = (index » (b=nDims» & ndOnes;
coords «= nDims;
coords 1= rotateLeft(bits, rotation, nDims) A flipBit;
flipBit = (halfmask_t)l « rotation;
adjust_rotation (rotation,nDims, bitsl ;
73 
} while (b);
for (b = nDims; b < nDimsBitsi b *= 2)
coords A= coords » b;
coords bitTranspose(nBits, nDims, coords);
}
else
coords index A (index » 1) i
for (d
{
Oi d < nDims; ++d)
coord [d) = coords & nbOnesi
coords »= nBitsi
}
else
coord [OJ index;
/*****************************************************************
* hilbert c2i
*
Number of coordinates.
Number of bits/coordinate.
Array of n nBitsbit coordinates.
Output index value. nDims*nBits bits.
* Convert coordinates of a point on a Hilbert curve to its index.
* Inputs:
* nDims:
* nBits:
* coord:
* Outputs:
* index:
* Assumptions:
* nDims*nBits <= (sizeof bitmask_t) * (bitsyer_byte)
*/
bitmask t
//hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[])
hilbert_c2i(unsigned nDims, unsigned nBits, bitmask t coord[])
{
if (nDims > 1)
{
unsigned const nDimsBits
bitmask_t index;
unsigned d;
bitmask_t coords = 0;
for (d = nDimsi d;
{
coords «= nBits;
coords 1= coord[d]j
nDims*nBits;
if (nBits > 1)
{
halfmask t const ndOnes = ones (halfmask_t,nDims) i
halfmask t canst nd10nes= ndOnes » 1j /* for adjust_rotation
*/
unsigned b = nbimsBits;
unsigned rotation = OJ
halfmask_t flipBit = 0;
bitmask_t canst nthbits = ones(bitmask_t,nDimsBits) / ndOnes;
coords = bitTranspose(nDims, nBits, coords)j
74 
coords A= coords » nDims;
index = 0;
do
{
halfmask_t bits = (coords » (b=nDims» & ndOnes;
bits = rotateRight(flipBit A bits, rotation, nDims);
index «= nDims;
index 1= bits;
flipBit = (halfmask_t)l « rotation;
adjust rotation(rotation,nDims,bits);
} while (b) ;
index A= nthbits » 1;
}
else
index = coords;
for (d = 1; d < nDimsBits; d *= 2)
index A= index » d;
return index;
}
else
return coord [0] ;
}
#ifdef __cplusplus
}
#endif
#endif /* hilbert h */
75
VITA
HuaLI
Candidate for the Degree of
Master of Science
Thesis: LOCALITY PRESERVING PROPERTIES OF SPACEFILLING CURVES
Major Field: Computer Science
Biographical:
Education: Graduated from Nanjing University, Nanjing, China, with a Bachelor in
Physics in June, 1989; received a Doctor of Philosophy in Physics at Nanjing University,
Nanjing, China in June, 1995; completed the requirements for the Master of Science
degree in Computer Science at Oklahoma State University in May, 2002.
Experience: Visiting Computational Physicist March 1998  September 1999 Department
of Physics, HKUST Hong Kong. Computational Physicist and faculty September 1995 September
1999 National Lab of Solid Stat,e Microstructures, Nanjing University,
Nanj ing China.