Comparing the Locality Preservation of Z-order Curves and Hilbert Curves

Abstract

Developing and testing software in the automotive industry and in the research of autonomous vehicles requires the costly querying of multidimensional data recorded from such a vehicle’s various sensors. Through encoding such data using space filling curves, faster queries could be achieved by reducing multiple dimensions into a singular dimension, while exploiting the patterns that emerge in the one-dimensional representation to still get accurate search results. The aim of our study is to systematically compare key behaviors of Hilbert and Morton space-filling curves when applied to realistic automotive sensor data. We applied design science research to develop an experimental environment to investigate the proposed querying method and the comparative results in using either Morton or Hilbert curves with this method. This allowed us to establish some design heuristics for future applications employing this method. We found that asymmetry in data can have a strong deleterious or advantageous effect on event querying, and surprisingly little difference in the True Positive to False Positive ratio of search results between Morton and Hilbert curves. Overall, we prove the viability of this use of both Morton and Hilbert curves for up to eight dimensions of data.