An optimized SFC approach for nD window querying on point clouds

Research output: Contribution to journalConference articleScientificpeer-review

47 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)119-128
Number of pages10
JournalISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Volume6
Issue number4/W1
DOIs
Publication statusPublished - 2020
Event3rd BIM/GIS Integration Workshop and 15th 3D GeoInfo Conference 2020 - London, United Kingdom
Duration: 7 Sep 202011 Sep 2020

Keywords

  • Point Clouds
  • Query
  • SFC
  • Histogram
  • Distribution
  • B+-Tree
  • Oracle
  • Morton Curve

Fingerprint

Dive into the research topics of 'An optimized SFC approach for nD window querying on point clouds'. Together they form a unique fingerprint.

Cite this