Item – Theses Canada

​
OCLC number
31172360
Author
Yang, Wei-Ping,1958-
Title
A new range searching algorithm for large point databases.
Degree
M. Sc. E. -- University of New Brunswick, 1992
Publisher
Ottawa : National Library of Canada = Bibliothèque nationale du Canada, 1993.
Description
2 microfiches.
Notes
University Microfilms order no. UMI00421720.
Includes bibliographical references.
Abstract
This thesis offers an indexing structure design with efficient algorithms for range search in a large 2-D point data set. After reviewing and evaluating various data structures, it is evident that a linear indexing structure, obtained from ordering the space, efficiently handles spatial data. Range search algorithms for both orthogonal and rotated rectangular query windows are consequently designed for a linear indexing structure based on Morton ordering. For any search information, overheads are necessary because of points outside the query window. With the proposed algorithm, this overhead is reduced by using special properties of Morton ordering. Compared to previous methods, this method is conceptually straightforward and does not require additional data structure support. The time complexity is never poorer than that of existing algorithms. The rotated range search is performed by forming a bounding rectangle so that the algorithm for the orthogonal case can still be utilized. An additional search overhead, caused by rotation, is reduced by the development of a block extending algorithm designed in this thesis.
ISBN
0315815116
9780315815117