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

Z-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 g-order Value LookUp Table (namely VLUT_g), which can directly obtain the corresponding code (or coordinate) through coordinate (or code). Building upon this, we present efficient Z-order curve encoding and decoding algorithms based on VLUT_g, and further design the coarse-grained and fine-grained parallel Z-order curve encoding and decoding algorithms based on Graphics Processing Units (GPU), thus significantly enhancing the efficiency of Z-order curve encoding and decoding. We further propose VLUT_g combining with B⁺-tree (VLUT_g-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 g 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_g-B⁺ can be up to 5.67× faster than R*-tree on spatial range query.