An optimized SFC approach for nD window querying on point clouds

    Research output: Contribution to journalConference articleScientificpeer-review

    3 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