ge of the 
arch time 
on of the 
. It only 
)W. 
layer 4 
  
  
  
  
  
  
  
  
nd more 
. For one 
forming 
ating the 
es which 
  
LISTING 1: Pseudocode of the n-d search algorithm for a regular window 
Begin 
Compute the codes of the QW extremes (Code LE, Code HE] 
Find the next data point, DP (Code DP), at or after Code LE 
While ( (Code DP « Code, HE) and end of data point list not reached) 
Call IncludeTest 
If (Code. DP is IN) Then Report 
Take next DP sequentially 
Else (Code. DP is OUT) 
DP 
Call LayerInfo (to determine current layer) 
If (Code. DP » Code HE(L)) 
Call FwdPoint2 (to determine the next FP) 
Else 
Call FwdPointl (to determine the next FP) 
EndIf 
Set new Lower Extreme (Code_LE = Code_FP) 
EndIf 
End While 
EndBegin. 
5. AN N-DIMENSIONAL RANGE SEARCH 
ALGORITHM BASED ON ROW ORDER 
The pseudocode of an n-d range search 
algorithm for an orthogonal query window is 
given in LISTING 1l. The following 
explanations are necessary for understanding 
the pseudocode: 
QW is the query window. 
LE, HE are the Lower Extreme (south-west 
corner point) and Higher Extreme (north-east 
corner point), respectively, of the query 
window. 
DP, FP stand for Data Point and Forward 
Point respectively. 
HE(L), NE(L) are the Higher Extreme and 
the North-East point (the highest point) of any 
arbitrary layer, L. 
Code. p is the code of any given point, p. 
The function, IncludeTest tests if a given 
point is inside the window, while the function 
LayerInfo determines the next layer with its 
relevant homolog points (those corresponding 
geometrically to the LE, HE, and NE of any 
given layer L), whenever a data point is found 
to be outside the window (this information is 
relevant for the determination of the next 
forward point). The function FwdPointl 
determines the next FP when the search is still 
within the same layer, while FwdPoint2 
determines FP when a data point which has 
been found to be out of the window is also 
found to be in a different layer. 
Given are the sorted points with codes 
precomputed, the highest resolution unit in each 
101 
of the dimensions, and the LE and HE (each 
being n-d co-ordinates) of the query window. 
5.1 Performance of the new algorithm in 2-d 
The preprocessing required to create a sorted list 
of row codes takes O(NLogN) time, where N is 
the number of data points. The storage 
complexity is O(N). Each time the search exits 
the window, it requires a constant time to 
compute the next FP, and a time of O(LogN) to 
retrieve FP or the next data code from the list. 
Hence, the total determination and retrieval of 
FP's is of O(Yrange + YrangeLogN) where 
Yrange is the difference in resolution units 
between the y-values of LE and HE of the query 
window. This is the worst case for a fully- 
populated space. The total search time for 
retrieving I data points in a given window is 
therefore O(I + Yrange + YrangeLogN). 
6. A COMPARISON OF THE 2-D MORTON 
ORDER AND ROW ORDER SEARCH 
ALGORITHMS 
6.1 Theoretical comparison 
The performance of the Morton order search is 
dependent on both the size and location of the 
query window, whereas, the row order search 
is only dependent on the size of the window. 
Also, the determination of FP's in row order 
does not seem to be as critical as that of Morton 
order search. 
The time complexities in preprocessing and 
storage are the same in both orders, but there is