×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

Full text

Title
Systems for data processing, anaylsis and representation

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.