HistSFC is a novel framework for querying nD point clouds considering skewed data distributions. It converts a multidimensional point — using Morton code — to a one-dimensional key. Then, HistSFC organizes and indexes the keys using a B+-tree. To perform a window query or an aribitrary geoemtrical query (e.g., the polytope query), it utilizes an nD-histogram to recursively decompose the data extent to approaximate the query geometry by one-dimensional ranges. Then, it searches the ranges in the B+-tree organized table to retrieve the data. Afterwards, a second filter conductes the decoding and point-wise filtering to derive the accurate result.
Figure 1. Executing a window query on a uniformly distributed 2D point set
Figure 2. The loading and querying procedure of the Morton index-organized table approach
Figure 3. A 2D HistogramTree example, where the threshold is 100; left: point counting in Morton quadrants, middle: pointer structure of HistogramTree, with each node storing a Morton key and number of points, right: structure of a HistTree node
Figure 4. SWEEP algorithm for polytope querying based on HistSFC, with white nodes outside, green nodes inside and red nodes on the boundary
Figure 5. Perspective view resulting from a zoom-in query on AHN2 data
Figure 6. Perspective view resulting from a zoom-out query on AHN2 data, colored by elevation