Systems for data processing, anaylsis and representation

Allam, Mosaad; Plunkett, Gordon

Bibliographic data

Monograph

Persistent identifier:: 1067490280

Title:: Systems for data processing, anaylsis and representation

Sub title:: ISPRS Commission II Symposium : June 6 - 10, Ottawa, Canada

Scope:: 1 Online-Ressource (XX, 530 Seiten)

Year of publication:: 1994

Place of publication:: Ottawa

Publisher of the original:: The Surveys, Mapping and Remote Sensing, Natural Resources Canada

Identifier (digital):: 1067490280

Illustration:: Illustrationen

Signature of the source:: ZS 312(30,2)

Language:: English

Additional Notes:: Erscheinungsdatum des Originals ist aus dem Copyrightjahr ermittelt.

Usage licence:: Attribution 4.0 International (CC BY 4.0)

Editor:: Allam, Mosaad; Plunkett, Gordon

Corporations:: Symposium Systems for Data Processing, Analysis and Representation, 1994, Ottawa; International Society for Photogrammetry and Remote Sensing; International Society for Photogrammetry and Remote Sensing, Commission Instrumentation for Data Reduction and Analysis; Kanada, Surveys, Mapping and Remote Sensing Sector

Adapter:: Symposium Systems for Data Processing, Analysis and Representation, 1994, Ottawa; International Society for Photogrammetry and Remote Sensing; International Society for Photogrammetry and Remote Sensing, Commission Instrumentation for Data Reduction and Analysis; Kanada, Surveys, Mapping and Remote Sensing Sector

Founder of work:: Symposium Systems for Data Processing, Analysis and Representation, 1994, Ottawa; International Society for Photogrammetry and Remote Sensing; International Society for Photogrammetry and Remote Sensing, Commission Instrumentation for Data Reduction and Analysis; Kanada, Surveys, Mapping and Remote Sensing Sector

Other corporate:: Symposium Systems for Data Processing, Analysis and Representation, 1994, Ottawa; International Society for Photogrammetry and Remote Sensing; International Society for Photogrammetry and Remote Sensing, Commission Instrumentation for Data Reduction and Analysis; Kanada, Surveys, Mapping and Remote Sensing Sector

Publisher of the digital copy:: Technische Informationsbibliothek Hannover

Place of publication of the digital copy:: Hannover

Year of publication of the original:: 2019

Document type:: Monograph

Collection:: Earth sciences

Chapter

Title:: [Tuesday, June 7, 1994]

Document type:: Monograph

Structure type:: Chapter

Chapter

Title:: [Session D-2 WG II/2 - Hardware and Software Aspects of GIS - Part A]

Document type:: Monograph

Structure type:: Chapter

Chapter

Title:: AN EVEN FASTER RANGE SEARCH ALGORITHM FOR MULTI-DIMENSIONAL POINT SETS Y. C. LEE and BENSON O. AGI

Document type:: Monograph

Structure type:: Chapter

A 2-d search algorithm based on the Morton order is compared, in this paper, with a new algorithm based on row-major ordering, in terms of its simplicity and performance. Problems identified with the range search algorithm using Morton codes are discussed, and solutions are suggested to overcome these problems. As a result, an extended version of the 2-d range search algorithm to a multi- dimensional solution , using the layered approach, has been achieved. 2. SUMMARY OF THE 2-D ALGORITHM BASED ON MORTON ORDER A detailed description of the range search algorithm based on Morton order has been given by Yang [1992] and Lee and Yang [1993]. The basic concept on which that algorithm was developed is that: over-searches are reduced by keeping the search within the query window. The moment a data point is found to be outside the window, the next entry point of the window is accessed by searching along the edges of the window. A data point immediately after that is called the Forward Point (FP). Some optimizations, based on the properties of Morton curve, are then applied, to further reduce the search over-head. The major advantage of this strategy is that it does not need additional data structures to support the search, and the search time depends on the query window with less influence from the size of the database. The performance of that algorithm was judged to largely depend on how fast FP could be found. The preprocessing required to create a sorted list of Morton codes is of O(NLogN), where N is the number of data points. The storage complexity is O(N). The processing time required to find an FP, and retrieve the data at or after FP, is O(KLogL + KLogN); where L is the average length of an edge in resolution units, and K is the number of times the Morton curve exits the window. On a fully-populated space, N > L, and the search over-head 1s bounded by KLogN. K depends on the size and location of the query window. The time it takes to retrieve I data points within a window of L by L units is O(I + KLogL + KLogN). 3. PROBLEMS WITH RANGE SEARCH BASED ON MORTON ORDER 98 The following problems have been identified with the search algorithm based on Morton order: 1. The time for finding a forward point (FP). This depends on the size and location of the query window within the application space. The recursion that generates the Morton codes is quadrant-based. Therefore, as the query window cuts across different quadrants, the processing of the forward points take on different characteristics. For example, for a given 2-d space as in Figure la, the query time for the same size of a window in location [A] is expected to be significantly lower than that in location [B] which cuts across higher levels of quadrants. 2. Costly overhead for rotated or generally irregular window. The 2-d search algorithm works only for a query window which sides are orthogonal to the co-ordinate axes. This is because its efficiency depends on the properties of Morton order, namely: (a) the Morton codes on lines parallel to the axes of the space are sorted; and (b) for any rectangular window orthogonal to the axes, the south-west corner (SW) has the smallest Morton code, and the north-east corner (NE) has the greatest code. This constraint necessitates the forming of bounding rectangles over query windows which have irregular sides, or rectangular windows which are not orthogonal to the co-ordinate axes. As a result of this constraint, over-searches corresponding to the shaded area of Figure 1b arise. The accuracy of the search could be jeopardized, and any attempt to improve the accuracy may be at the expense of search time. 3. Extension of the concept to multi- dimensional range search. It seems possible to extend the 2-d algorithm to involve domains of n-d spaces. In this case, the file is a collection of records, each of which is identified by an ordered n-tuple of keys {W1, W2, ..., Wn} which can be viewed as a point in an n-d Cartesian space. The Cartesian space formulation is the abstraction of a variety of important applications, often referred to as multikey search [Knuth, 1973; Yang, 1992]. In the Cartesian space, aspatial problems can bear geometric significance if the record attributes are regarded as co-ordinates and the n-values for each record as representing a point in an n-d co- ordinate system. One ca the n-d figure analogy the hyp the 2-d window involve possible These p range generat scheme Morton some ac concept 4. THE To bene search a the n-d collectic consecu west co plane). projecti coding « Such a first lay: within tl north-e maximu South-w equal to plus 1.

Access restriction

Copyright

fullscreen: Systems for data processing, anaylsis and representation

Monograph

Chapter

Chapter

Chapter

Table of contents

Cite and reuse

Monograph

Chapter

Image

Image fragment

Citation links

Citation recommendation