@article{Jia2027, 
author = {Lianyin Jia and Jiajun Xu and Jiaman Ding and Suprio Ray and Yinong Chen and Guanqiu Qi},
title = {Efficient Lookup Table Based Z-Order Curve Encoding and Decoding: Algorithms, Parallelization, and Applications},
year = {2027},
journal = {Tsinghua Science and Technology},
volume = {32},
number = {1},
pages = {448-463},
keywords = {Z-order curve, g-order lookup table, Graphics Processing Units (GPU) based coarse-grained Z-order curve encoding, GPU-based coarse-grained Z order curve decoding, value lookup table combing with B+-tree},
url = {https://www.sciopen.com/article/10.26599/TST.2025.9010071},
doi = {10.26599/TST.2025.9010071},
abstract = {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 VLUTg), 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 VLUTg, 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 VLUTg combining with B+-tree (VLUTg-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, VLUTg-B+ can be up to 5.67× faster than R*-tree on spatial range query.}
}