a significant difference in the processing times.
While the processing time of Morton order
search is O(I + KLogL + KLogN), that of row
order is O(I + Yrange + YrangeLogN). Then,
what determines which algorithm is better very
much depends on the evaluation of the terms
KLogL versus Yrange, and the constants K
versus Yrange. Since there does not seem to be
any objective way to evaluate these parameters
theoretically, an experiment has been conducted
to compare their practical performances. What
is significant to note is that the determination of
FP's in the row order search is consistently
dependent on the y-range of the query window.
6.2 Experimental comparison
The new range search algorithm has been
implemented in C, using a fully-populated 2-d
space, defined over 1024 by 1024 points. It
has been run on the same platform, a SUN
SparcStation SLC. as used in the previous test
using the Morton order.
Statistics are generated for CPU times for both
algorithms, using three varying configurations
of query windows, namely:
(a) C-configuration: a query window
of size 300 by 300 resolution units, moved over
nine different locations of the data set (see Fig.
4a). The statistics comparing both methods are
given in Table 1.
(b) Z-configuration: the size of the
query window is varied by reducing it to 100 by
100 units while maintaining the same locations
as before (see Fig. 4b). The statistics are given
in Table 2.
(c) H-configuration: the shape of the
query window is varied and tested at different
locations (Fig. 4c). The statistics are in Table
2
6.1 Analysis of experimental results
l. It can be concluded from columns (6) and
(7) of each of the three tables that the algorithm
based on row order performs much better than
that based on Morton order. Generally, the
CPU time for the search in Morton order takes
about 2.5 times the time for the search based on
row order, for the same number of window
points (i.e., same size of query window), and at
the same location within the application space.
102
2. As theoretically expected, the result of the
experiment shows that a search on Morton
codes performs worst at the centre of the
application space, because of the quadrantic
nature of Morton curve. This is evident in
column (6) at each of the central locations C5
and 75. " The: time. for. C8 looks like an
exception, and may be partly because its
location also cuts across two major quadrants,
and also that higher digits are involved in the
handling of co-ordinates and codes of points.
3. Column (7) of both Tables 1 and 2 shows
that the search time using row ordering does not
depend on the location of the query window.
The time, however, generally increases with
increasing y. This can be partly due to the y-
range factor in the theoretical complexity, and
also partly to the fact that higher digits are being
manipulated with increasing y-coordinates.
4. It is observed from Tables 1 and 2 that
reducing the size of the query window by nine
times also reduces the query time by similar
amount, in both Morton and row orders.
Hence, the factor by which row order out-
performs Morton order is still maintained.
5. It is observed from Table 3 that variation of
the shape of the query window maintains the
same relationship in performance between the
search over Morton and row codes.
7. CONCLUSION
An n-d range search algorithm, based on row
order, has been developed for the special case
of orthogonal query windows. It has been
implemented using test data in 2-d space. À
theoretical analysis has been carried out to show
that row ordering may be more suitable than
Morton ordering of space, in the extension of an
existing 2-d range search algorithm to n-d,
because of some constraining properties of the
Morton curve. An experimental comparison of
2-d range search over both ordering has shown
that row order out-performs Morton order by
about 2.5 times in query response time.
The extension of the new range search
algorithm to rotated and irregular query
windows, with the full implementation of the n-
d version, is in progress.
299
Fig.
