ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Download
Citation
Volume VI-4/W1-2020
ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., VI-4/W1-2020, 119–128, 2020
https://doi.org/10.5194/isprs-annals-VI-4-W1-2020-119-2020
© Author(s) 2020. This work is distributed under
the Creative Commons Attribution 4.0 License.
ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., VI-4/W1-2020, 119–128, 2020
https://doi.org/10.5194/isprs-annals-VI-4-W1-2020-119-2020
© Author(s) 2020. This work is distributed under
the Creative Commons Attribution 4.0 License.

  03 Sep 2020

03 Sep 2020

AN OPTIMIZED SFC APPROACH FOR ND WINDOW QUERYING ON POINT CLOUDS

H. Liu, P. Van Oosterom, M. Meijers, and E. Verbree H. Liu et al.
  • Faculty of Architecture and the Built Environment, Delft University of Technology, the Netherlands

Keywords: Point Clouds, Query, SFC, Histogram, Distribution, B+-Tree, Oracle, Morton Curve

Abstract. Dramatically increasing collection of point clouds raises an essential demand for highly efficient data management. It can also facilitate modern applications such as robotics and virtual reality. Extensive studies have been performed on point data management and querying, but most of them concentrate on low dimensional spaces. High dimensional data management solutions from computer science have not considered the special features of spatial data; so, they may not be optimal. A Space Filling Curve (SFC) based approach, PlainSFC which is capable of nD point querying has been proposed and tested in low dimensional spaces. However, its efficiency in nD space is still unknown. Besides that, PlainSFC performs poorly on skewed data querying. This paper develops HistSFC which utilizes point distribution information to improve the querying efficiency on skewed data. Then, the paper presents statistical analysis of how PlainSFC and HistSFC perform when dimensionality increases. By experimenting on simulated nD data and real data, we confirmed the patterns deduced: for inhomogeneous data querying, the false positive rate (FPR) of PlainSFC increases drastically as dimensionality goes up. HistSFC alleviates such deterioration to a large extent. Despite performance degeneration in ultra high dimensional spaces, HistSFC can be applied with high efficiency for most spatial applications. The generic theoretical framework developed also allows us to study related topics such as visualization and data transmission in the future.