ding 
re. 
; In" 
; ; 
nics 
the 
leer- 
and 
ribu- 
AN EVEN FASTER RANGE SEARCH ALGORITHM FOR 
MULTI-DIMENSIONAL POINT SETS 
Y. C. LEE and BENSON O. AGI 
Department of Geodesy and Geomatics Engineering 
University of New Brunswick, Fredericton, N. B., Canada E3B 5A3 
Phone: (506) 453-5148, Fax: (506) 453-4943, E-mail: yclee 9 unbmvsl.csd.unb.ca 
ABSTRACT 
The paper describes a range search algorithm on two-dimensional point sets based on the row-major 
ordering of points. These algorithms are particularly useful for bathymetric applications where a 
large number of soundings are often involved. 
The algorithm uses a range search strategy developed earlier at the University of New Brunswick but 
based on the Morton ordering of points. That strategy does not require any spatial indices other than 
a sorted list of Morton codes. Its performance was found to compare favourably with the fastest 
range search method on point sets. 
It was discovered that the recursive nature of Morton ordering has adverse effects on range search, 
particularly in terms of multi-dimensional extensions and multi-sided query windows. We will 
describe these problems and their solutions in this paper. As a result, an even faster range search 
algorithm with better performance has been developed. 
KEY WORDS: Geographic Information Systems, Algorithms, Range Search, Point Sets. 
1. INTRODUCTION 
The requirement for an increasingly large spatial 
database is inevitable. While the ability of 
computers has steadily improved, the number of 
data sources and densities have also increased 
[McCormick et al., 1987]. The rate of increase 
of data volume arising from higher resolutions 
of data (e.g., new earth resource satellite data) 
far exceeds the rate of improvement in computer 
efficiency. Goodchild [1989] has shown that a 
doubling of spatial resolution produces at least a 
fourfold increase in data volume, in many 
cases. 
Applications involving large amounts of spatial 
data cause special concerns in the field of spatial 
database management systems [Guenther and 
Buchmann, 1990; Yang, 1992]. The 
application areas include pure geometric 
computations, entity relationship 
representations, resource and administrative 
management, socio-economic and 
administrative planning, on local and global 
Scopes. 
97 
Operations in a GIS require fast access and 
retrieval of data in spatial databases. On the 
other hand, large volumes of data involved in 
spatial databases cause slow response to user 
queries for some spatial data. The solution to 
this problem generates the need to employ 
optimized data structures and algorithms for 
spatial indexing and searching [Yang, 1992]. 
While various search algorithms exist, there is a 
continual need for improvement as uses of GIS 
diversify. 
Searching in a spatial database is influenced by 
the type of ordering of the data space. The 
performance of any search algorithm would 
depend on the optimization which could 
possibly be applied to that algorithm. Linear 
indexing structures have been favoured for use 
in GIS because of their advantages [Yang, 
1992]: they optimize the storage and query 
process; they are simple and flexible, allowing 
for both direct and sequential access to any 
point; and they allow optimization of algorithms 
necessary for image database applications 
[Orenstein and Manola, 1988]. The ordering 
scheme which has been popular in database 
applications is the Morton order.