## 3 Methodology
### Spatial Layer Construction
#### 3.1.2 Trie Tree for Managing Non-Equal Length-Encoding Sets  
The codes generated through the dynamic partitioning strategy are of varying lengths and do not have fixed precision, making them unsuitable for direct calculation by the encoding algorithm. GLMI uses a Trie tree to effectively manage these non-equal length-encoding sets and map data points to their corresponding partitions. The Trie tree [34], also known as a prefix tree or dictionary tree, is used to represent a set of strings over a finite alphabet. Its core idea is to save space and improve query efficiency by sharing common prefixes. A path from the root node to a leaf node in the Trie tree corresponds to a string, with nodes sharing the same parent having a common prefix. The encoding of partitioned areas shares a common prefix, and the partitioning process corresponds to the derivation of new child nodes from leaf nodes. The splitting process increases the encoding length by one, which is reflected in the Trie tree as an increase in branch depth by one. Geohash-Hilbert encodes the longitude range \([-180^{\circ},180^{\circ}]\) and the latitude range \([-90^{\circ},90^{\circ}]\). The data to be indexed generally do not cover such a large range, but are concentrated in a certain research area, resulting in the codes in the code set having a common prefix. In the traditional Trie tree, each node stores a character, resulting in a waste of space for the common prefix and reducing query efficiency. GLMI has improved the nodes of the Trie tree. The data stored in the nodes are no longer limited to characters, but allow the storage of more flexible data structures, such as the entire string. By identifying and merging nodes with common prefixes, the depth of the tree is effectively reduced and query efficiency is improved. The process of managing the non-equal length-encoding set in the Trie tree is as follows:  
(1) Generate the code using a dynamic partitioning strategy and insert the code into the Trie tree. (2) During the split operation, locate the leaf node corresponding to the pre-split code in the Trie tree, and add the newly generated characters from the post-split code as child nodes of that leaf node to complete the partition split. (3) Merge the nodes that represent the common prefix of the Geohash-Hilbert code. After managing the encoding set through the Trie tree, GLMI implements the mapping algorithm from data points to dynamic partitions. First, the Geohash-Hilbert code of the data point is calculated according to the highest precision of the partition, which is the length of the longest string in the encoding set. If the partition precision reaches the highest precision, the code exists in the encoding set; otherwise, it does not. However, the Geohash-Hilbert code must fully contain a code in the encoding set, which corresponds to the actual partition code of the data point in the GLMI dynamic partition. After managing the encoding set through the Trie tree, the time complexity of the mapping process can be controlled within O(\(k\)), where k is the partition code length. Algorithm 1 outlines the point data mapping process under the GLMI dynamic partition strategy. ```
0: p: data point, precision: the highest precision of the partition, Trie: spatial layer;
0: result: leaf node of Trie tree;
1: c \(\leftarrow\) Geohash_Hilbert.encode(p, precision);
2: node \(\leftarrow\) Trie_root, result \(\leftarrow\) null;
3: for char in c, do
4: if char not in node.children then
5: break;
6: else
7: node \(\leftarrow\) node.children[char];
8: end if
9: end for
10: return node. ### Temporal Layer Construction

The construction of the GLMI temporal layer is based on a piecewise linear model. The core idea is to sort the data by timestamp, establish a function mapping from the timestamp to its storage location, and ensure that the error between the predicted and actual positions is controllable.