Efficient Lookup Table Based <i>Z</i>-Order Curve Encoding and Decoding: Algorithms, Parallelization, and Applications

<em>Z</em>-order curve, as an efficient method for reducing spatial dimensionality, has found widespread applications in various fields. Although existing state-of-the-art algorithms design dimensional lookup tables, they suffer from the drawback of high table lookup frequency. To address this issue, we propose a novel and efficient <em>g</em>-order Value LookUp Table (namely VLUT_<em>g</em>), which can directly obtain the corresponding code (or coordinate) through coordinate (or code). Building upon this, we present efficient <em>Z</em>-order curve encoding and decoding algorithms based on VLUT_{<em>g </em>}, and further design the coarse-grained and fine-grained parallel <em>Z</em>-order curve encoding and decoding algorithms based on Graphics Processing Units (GPU), thus significantly enhancing the efficiency of <em>Z</em>-order curve encoding and decoding. We further propose VLUT<em>_g </em>combining with B⁺-tree (VLUT_<em>g</em>-B+) algorithm to extend our algorithms to support spatial range query. Experimental results on multiple datasets demonstrate that our encoding and decoding algorithms perform well when <em>g </em>is set to 8, with encoding 25 million 32-order discrete coordinate data requiring only 6.556 ms, achieving an efficiency improvement of two orders of magnitude compared to the fastest known algorithm. Besides, VLUT_<em>g</em>-B+ can be up to 5.67× faster than R^*-tree on spatial range query.