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

entified Morton nt (FP). 1 Of the | space. codes is | query nts, the ake on e fora ry time n [A] is | that in evels of nerally gorithm ides are This is operties n codes ace are vindow . corner and the st code. ing of s which indows rdinate earches gure 1b ould be ove the ı time. multi- sible to nains of llection ] by an ., Wn} an n-d space riety of d to as 92]. In an bear utes are lues for n-d co- One can draw an analogy between the 2-d and the n-d case. An n-d query window is a solid figure composed of hypersurfaces. The analogy is to order the n-d space and search in the hypersurfaces (instead of along the edges, in the 2-d case) for the next data point in the window. The optimization of this search would involve, in the least, the determination of all possible faces in which the entry point could be —— b | l | | [D | l rro quy rm | l— J 5 - | [All @ | | (a) Influence of Location of Query Window Fig. 1 These problems, that have been identified with range search based on Morton ordering, generate a need to explore some other ordering schemes which has, at least, the simplicity of Morton order, and at the same time can offer some advantages for extending the 2-d search Concept to n-d search. 4. THE LAYERED APPROACH SOLUTION AND SPACE ORDERING To benefit from the simplicity of the 2-d range search algorithm, the concept can be extended to the n-d case. The n-d space is treated as a collection of 2-d layers. Points in each layer are consecutively coded, starting from the south- west corner of the basic or first layer (the x-y plane). All subsequent layers are then a projection of each layer on the x-y plane. The Coding of points within these layers is done in Such a way that the south-west corner of the first layer is given the code 0, and all the points within the layer are completely ordered until the north-east corner point, which has the maximum code in that layer. The code of the south-west corner of any succeeding layer is Sg to the maximum code in the previous layer plus 1. 99 found, and searching in these faces to find the first points. Doing this would require complex analysis, because of the complexity of hypersurfaces. It has already been shown in the 2-d algorithm that the cost of the search is highest in the optimization which finds the first points. With the complexity of hypersurfaces, the time for finding the FP's may be extremely high. (b) Over-head in a Rotated Window The Morton code in the entire application space are not automatically sorted by layer. In other words, a Morton curve does not completely traverse a layer before visiting another one. Instead it goes in and out of any given layer, depending on the size of the resolution units in every dimension greater than 2. This fact is demonstrated in Figure 2, using a 3-d space as an example. As a consequence, it is difficult, if at all possible, to apply the same technique of search optimization on Morton codes. The row order which does not seem to impose the same restriction in coding and optimization has been investigated, as an alternative to Morton order, in the solution of n-d range search. The row order completely traverses a layer before going into another layer (see Figure 3). Other properties of the row order are that: the codes are always sorted in increasing y-co- ordinates, even on profiles not parallel to the co- ordinate axes; it is also always sorted in x-co- ordinates, given any constant y-value. Due to the properties of row order, it seems to allow better optimization of n-d range search. Apart from being compatible with the layered approach, it also makes the determination of the first points (FP's) much easier than in the case of Morton order. (Recall that the most time is spent on the determination of the FP's in the 2-d algorithm using Morton order.) This is

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